Acyklický orientovaný graf
V teorii grafů je směrovaný acyklický graf (v angličtině zaměřený acyklický graf nebo DAG ) směrovaný graf, který nemá žádné obvody . Takový graf lze chápat jako hierarchii .
Definice
Acyklický směrovaný graf je směrovaný graf, který nemá obvod .
- Vždy najdeme podgraf pokrývající acyklický směrovaný graf, který je stromem (nebo lesem).
- V acyklicky orientovaném grafu je relace přístupnosti R ( u , v ) definovaná „existuje cesta od u do v “ relací částečného řádu . Algoritmus topologického třídění umožňuje číslovat vrcholy acyklického směrovaného grafu způsobem kompatibilním s tímto řádem (jinými slovy, pokud v grafu existuje cesta od u do v , pak je počet u menší než to o V ).
- Toto číslování usnadňuje reprezentaci podle úrovní. Pro směrovaný acyklický graf výše tvoří vrcholy (7, 5, 3) úroveň 1, (11, 8) úroveň 2, (2, 9, 10) úroveň 3. Oblouk od 8 do 11 by zavedl 4 úrovně, uložené cestou (3, 8, 11, 2).
Algoritmické aspekty
- Problém nejkratší cesty ze zdroje může být řešen v lineárním čase takovým grafu.
- Je možné najít minimální pokrytí cesty v polynomiálním čase, zatímco v jakémkoli orientovaném grafu je to NP-úplný problém .
- Vzhledem k orientovanému grafu můžeme vždy odebrat určitý počet vrcholů a transformovat jej na acyklický graf. Taková sestava se nazývá vrcholová sada vrcholů ( zpětnovazebná vrcholová sada ). Spojená algoritmické Problém spočívá v nalezení takového souboru minimálních mohutnosti.
Použití
Pojem formalizuje tradiční analytický nástroj , jehož příklady najdeme:
- pokud jde o plánování projektu, organizační schémata atd.
- Ve všech modelech ve vrstvách jako OSI modelu , modelu Bühler (nebo Taber - Nida ) z funkce jazyka , psychologie nebo pyramidy potřeb z Maslow .
- Technologie bezpečných transakcí IOTA má pro podkladovou datovou strukturu acyklický směrovaný graf na rozdíl od klasičtějšího blockchainu, který má pro podkladovou datovou strukturu kořenový strom ( „řetězce“ jsou cesty od kořene k listům). Každá transakce je uzlem grafu.
V počítačové vědě se pojem vztahuje zejména na reprezentaci termínů se sdílením, na organizaci důkazů v přirozené dedukci nebo na teorii jazyků objektové orientace s ohledem na klasifikaci typů.
Poznámky a odkazy
-
Sylvie Hamel, „ Oriented graphs “ , na University of Montreal
Související články