Aciklus orientált grafikon
A gráfelméletben az irányított aciklusos gráf (angolul irányított aciklusos gráf vagy DAG ) egy olyan irányított gráf, amelynek nincs áramköre . Egy ilyen grafikon hierarchiának tekinthető .
Meghatározás
Az aciklusos irányított gráf olyan irányított gráf, amelynek nincs áramköre .
- Mindig találunk egy algráfot, amely egy aciklusos irányított gráfot takar, amely egy fa (vagy egy erdő).
- Az aciklikusan irányított gráfban az R ( u , v ) hozzáférhetőségi reláció , amelyet „létezik egy út U- tól V-ig ” részparancssori összefüggés . A topológiai rendezési algoritmus lehetővé teszi az aciklikusan irányított gráf csúcsainak számozását ezzel a sorrenddel kompatibilis módon (más szavakkal, ha van egy út u- tól v -ig a grafikonon, akkor az u száma ennél kisebb a v ) pontból .
- Ez a számozás megkönnyíti a szintek szerinti ábrázolást. A fenti irányított aciklusos gráfhoz a (7, 5, 3) csúcsok alkotják az 1. szintet, (11, 8) a 2. szintet, (2, 9, 10) a 3. szintet alkotják. Egy 8 és 11 közötti ív vezetne be 4 szint, amelyet az út szab ki (3, 8, 11, 2).
Algoritmikus szempontok
- A forrásból származó legrövidebb utak problémája lineáris időben megoldható egy ilyen grafikonon.
- Minimális útfedést lehet találni polinomiális időben, míg ez NP-teljes probléma bármely irányított gráfban.
- Irányított gráf esetén mindig eltávolíthatunk bizonyos számú csúcsot, hogy azt aciklusos gráffá alakítsuk. Az ilyen összeállítást csúcscsúcs-csúcsnak ( visszacsatoló csúcs-halmaznak ) nevezzük . A kapcsolódó algoritmikus probléma abban áll, hogy megtalálja a minimális kardinalitások ilyen halmazát.
Használ
A fogalom formalizálja a hagyományos elemzési eszközt , amelyre példák találhatók:
- a projekt ütemezése, a szervezeti diagramok stb.
- Minden modell rétegekben , mint a OSI modell , a modell Bühler (vagy Taber - Nida ) a nyelvi funkciók , a pszichológia vagy a piramis igényeinek a Maslow .
- A biztonságos tranzakciók IOTA technológiája az alapul szolgáló adatstruktúrához egy aciklikusan irányított gráfot mutat, ellentétben a klasszikusabb blokklánccal, amely az alapul szolgáló adatstruktúrához gyökeres fát tartalmaz (a "láncok" a gyökértől a levelekig vezető utak). Minden tranzakció a gráf csomópontja.
A számítástechnika , az elképzelés, különösen vonatkozik a képviselet az értelemben a megosztás, a szervezet az igazolások a természetes levonás vagy az elmélet nyelvén objektumorientáltság , tekintettel a besorolás a típusokat.
Megjegyzések és hivatkozások
-
Sylvie Hamel, " Orientált grafikonok " , a Montreali Egyetemen
Kapcsolódó cikkek