Grafic orientat aciclic

În teoria graficelor , un grafic aciclic direcționat (în engleză direkt acyclic graph , sau DAG ) este un grafic direcționat care nu are circuite . Un astfel de grafic poate fi văzut ca o ierarhie .

Definiție

Un grafic direcționat aciclic este un grafic direcționat care nu are un circuit .

• Putem găsi întotdeauna un subgraf care acoperă un grafic direcționat aciclic care este un copac (respectiv o pădure).
• Într-un grafic direcționat aciclic, relația de accesibilitate R ( u , v ) definită de „există o cale de la u la v  ” este o relație de ordine parțială. Algoritmul de sortare topologică face posibilă numerotarea vârfurilor unui grafic direcționat aciclic într-un mod compatibil cu această ordine (cu alte cuvinte, dacă există o cale de la u la v în grafic, atunci numărul lui u este mai mic decât acela din v ).
• Această numerotare facilitează reprezentarea pe niveluri. Pentru graficul aciclic direcționat mai sus, vârfurile (7, 5, 3) formează nivelul 1, (11, 8) formează nivelul 2, (2, 9, 10) nivelul 3. Un arc de la 8 la 11 ar introduce 4 niveluri, impuse de cale (3, 8, 11, 2).

Aspecte algoritmice

• Problema căi scurte dintr - o sursă poate fi rezolvată în timp liniar într -un astfel grafic a.
• Este posibil să găsiți o acoperire minimă a căii în timp polinomial, în timp ce este o problemă NP-completă în orice grafic direcționat.
• Având în vedere un grafic direcționat, putem elimina oricând un anumit număr de vârfuri pentru a-l transforma într-un grafic aciclic. Un astfel de ansamblu se numește set de vârfuri de vârfuri ( set de vârfuri de feedback ). Problema algoritmică asociată constă în găsirea unui astfel de set de cardinalități minime.

Utilizări

Noțiunea formalizează un instrument de analiză tradițional , ale cărui exemple pot fi găsite:

• în ceea ce privește programarea proiectelor, organigramele etc.
• în toate modelele în straturi precum modelul OSI , modelul lui Bühler (sau Taber - Nida ) al funcțiilor limbajului , psihologiei sau piramidei nevoilor lui Maslow .
• Tehnologia IOTA de tranzacții sigure are pentru structura de date subiacentă un grafic direcționat aciclic spre deosebire de blockchain- ul mai clasic care are pentru structura de date subiacentă un copac înrădăcinat ( „lanțurile” sunt căile de la rădăcină la frunze). Fiecare tranzacție este un nod al graficului.

În informatică , noțiunea se aplică în special pentru reprezentarea termenilor cu partajarea, pentru organizarea probelor în deducția naturală sau pentru teoria limbajelor de orientare obiect , în ceea ce privește clasificarea tipurilor.

Note și referințe

1. Sylvie Hamel, „  Grafice orientate  ” , la Universitatea din Montreal

Articole similare

• Relația aciclică
• Collider (statistici)