Acyklisk orienteret graf
I grafteori er en rettet acyklisk graf (på engelsk rettet acyklisk graf eller DAG ) en rettet graf, der ikke har nogen kredsløb . En sådan graf kan ses som et hierarki .
Definition
En acyklisk rettet graf er en rettet graf , der ikke har et kredsløb .
- Vi kan altid finde en undergraf, der dækker en acyklisk rettet graf, som er et træ (hhv. En skov).
- I et acyklisk orienteret graf, den tilgængelighed forhold R ( u , v ) defineret af ”findes der en sti fra u til v ” er en partiel orden forhold . Den topologiske sorteringsalgoritme gør det muligt at nummerere hjørnerne i en acyklisk rettet graf på en måde, der er kompatibel med denne rækkefølge (med andre ord, hvis der er en sti fra u til v i grafen, så er antallet af u mindre end det af v ).
- Denne nummerering letter repræsentationen efter niveauer. For den rettede acykliske graf ovenfor udgør hjørnerne (7, 5, 3) niveauet 1, (11, 8) danner niveauet 2, (2, 9, 10) niveauet 3. En bue fra 8 til 11 ville introducere 4 niveauer, pålagt af stien (3, 8, 11, 2).
Algoritmiske aspekter
- Den Problemet med korteste veje fra en kilde kan løses på lineær tid på en sådan graf.
- Det er muligt at finde minimal stigdækning i polynomisk tid, hvorimod det er et NP-komplet problem i en hvilken som helst rettet graf.
- Givet en rettet graf, kan vi altid fjerne et bestemt antal hjørner for at omdanne det til en acyklisk graf. En sådan samling kaldes vertex sæt af hjørner ( feedback vertex sæt ). Det tilknyttede algoritmiske problem består i at finde et sådant sæt minimumskardinaliteter.
Anvendelser
Begrebet formaliserer et traditionelt analyseværktøj , hvis eksempler kan findes:
- med hensyn til projektplanlægning, organisationskort osv.
- i alle modeller i lag som OSI-modellen , modellen til Bühler (eller Taber - Nida ) af sprogets funktioner , psykologi eller behovspyramide af Maslow .
- IOTA- teknologien til sikre transaktioner har for underliggende datastruktur en acyklisk rettet graf i modsætning til den mere klassiske blockchain, som for underliggende datastruktur har et rodfæstet træ ( "kæderne" er stierne fra roden til bladene). Hver transaktion er en node i grafen.
Inden for datalogi gælder begrebet især for repræsentation af vilkår med deling, til organisering af bevis i naturlig deduktion eller for teorien om sprog med objektorientering med hensyn til klassificering af typer.
Noter og referencer
-
Sylvie Hamel, " Orienterede grafer " , om University of Montreal
Relaterede artikler