Objednaný graf - Ordered graph - Wikipedia

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Březen 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

An uspořádaný graf je graf s celková objednávka přes jeho uzly.

V uspořádaném grafu jsou rodiči uzlu uzly, které s ním sousedí a předcházejí jej v pořadí.^[1] Přesněji, ${ displaystyle n}$ je rodičem ${ displaystyle m}$ v uspořádaném grafu ${ displaystyle langle N, E, < rangle}$ -li ${ displaystyle (n, m) v E}$ a ${ displaystyle n$. Šířka uzlu je počet jeho rodičů a šířka uspořádaného grafu je maximální šířka jeho uzlů.

The indukovaný graf uspořádaného grafu se získá přidáním některých hran k objednávkovému grafu pomocí níže uvedené metody. The indukovaná šířka uspořádaného grafu je šířka jeho indukovaného grafu.^[2]

Vzhledem k uspořádanému grafu je jeho indukovaný graf dalším uspořádaným grafem získaným spojením několika párů uzlů, které jsou oba rodiči jiného uzlu. Zejména uzly jsou považovány postupně podle pořadí, od posledního po první. Pro každý uzel, pokud dva z jeho rodičů nejsou spojeny hranou, je tato hrana přidána. Jinými slovy, když uvažujeme o uzlu ${ displaystyle n}$, pokud obojí ${ displaystyle m}$ a ${ displaystyle l}$ jsou jeho rodiče a nejsou spojeni hranou, hranou ${ displaystyle (m, l)}$ je přidán do grafu. Protože rodiče uzlu jsou vždy navzájem propojeni, indukovaný graf je vždy akordický.

Jako příklad se vypočítá indukovaný graf uspořádaného grafu. Pořadí je reprezentováno polohou jeho uzlů na obrázcích: a je poslední uzel ad je první.

Původní graf.	Edge přidán s ohledem na rodiče ${ displaystyle a}$	Edge přidán s ohledem na rodiče ${ displaystyle b}$

Uzel ${ displaystyle a}$ je považován za první. Jeho rodiče jsou ${ displaystyle b}$ a ${ displaystyle c}$, protože jsou oba spojeni ${ displaystyle a}$ a obě předcházejí ${ displaystyle a}$ v objednávce. Protože nejsou spojeny hranou, přidá se jedna.

Uzel ${ displaystyle b}$ je považován za druhý. Zatímco tento uzel má pouze ${ displaystyle d}$ jako rodič v původním grafu také má ${ displaystyle c}$ jako rodič v částečně vytvořeném indukovaném grafu. Vskutku, ${ displaystyle c}$ je připojen k ${ displaystyle b}$ a také předcházet ${ displaystyle b}$ v objednávce. Výsledkem je spojení hran ${ displaystyle c}$ a ${ displaystyle d}$ je přidáno.

S ohledem na ${ displaystyle d}$ neprodukuje žádné změny, protože tento uzel nemá žádné rodiče.

Zpracování uzlů v pořadí záleží, protože zavedené hrany mohou vytvořit nové rodiče, které jsou pak relevantní pro zavedení nových hran. Následující příklad ukazuje, že různé pořadí vytváří odlišný indukovaný graf stejného původního grafu. Objednávka je stejná jako výše, ale ${ displaystyle b}$ a ${ displaystyle c}$ jsou vyměněny.

Stejný graf, ale pořadí ${ displaystyle b}$ a ${ displaystyle c}$ je vyměněn	Graf po zvážení ${ displaystyle a}$

Stejně jako v předchozím případě obojí ${ displaystyle b}$ a ${ displaystyle c}$ jsou rodiče ${ displaystyle a}$. Proto je přidána hrana mezi nimi. Podle nového pořadí je považován druhý uzel ${ displaystyle c}$. Tento uzel má pouze jednoho rodiče (${ displaystyle b}$). Proto není přidán žádný nový okraj. Třetím uvažovaným uzlem je ${ displaystyle b}$. Je to jediný rodič ${ displaystyle d}$. Vskutku, ${ displaystyle b}$ a ${ displaystyle c}$ nejsou tentokrát připojeni. Výsledkem je, že není zavedena žádná nová hrana. Od té doby ${ displaystyle d}$ nemá ani rodiče, konečný indukovaný graf je ten výše. Tento indukovaný graf se liší od grafu vytvořeného předchozím uspořádáním.

Viz také

• Směrovaný graf
• Místní konzistence

Reference

• Dechter, Rina (2003). Zpracování omezení. Morgan Kaufmann. ISBN  1-55860-890-7