Digraf aciclic conectat

În teoria graficelor, un digraf aciclic conectat înseamnă un digraf (grafic orientat) fără cicluri (circuite) și astfel încât graficul obținut prin neglijarea orientării marginilor este puternic conectat . Prin urmare, un astfel de digraf nu are bucle și, având în vedere cele două noduri ale sale, este posibil să treacă de la unul la altul deplasându-se pe arcadele sale în direcția lor sau în direcția opusă.

Proprietate

Notăm prin DAC ansamblul digrafelor aciclice conectate și luăm în considerare următoarele subseturi

Set de arborescențe elementare AE ;
Set DB de digrame bipartite;
Un set de arborescențe (sau copaci cu rădăcini);
Setul DGC de digrame gradate conectate redate intransitive și antireflexive.

Următoarele relații stabilite se mențin

$AE=DB\bigcap A$ ${\ displaystyle AE = DB \ bigcap A}$ ${\ displaystyle AE = DB \ bigcap A}$
$DB,A\subset DGC$ ${\ displaystyle DB, A \ subset DGC}$ ${\ displaystyle DB, A \ subset DGC}$
$DGC\subset DAC$ ${\ displaystyle DGC \ subset DAC}$ ${\ displaystyle DGC \ subset DAC}$

Apoi scurtăm termenul „digraf aciclic conectat” și pluralul său cu dac , astfel încât să putem scrie DAC = {dac} ; în mod similar, suntem de acord că DGC = {dgc} etc.

Dacă p , q și r indică noduri ale unui digraf D în DAC și dacă arcul (p, q) se găsește în astfel de D , spunem că q depinde direct de p ; dacă găsim în D o cale de la p la r spunem că r depinde de p (fără a specifica dacă depinde direct sau indirect).

În DAC - DGC găsim digrame cu triple de noduri distincte (p, q, r) astfel încât atât q cât și r depind direct de p , în timp ce r depinde (direct sau indirect) de q .

În ceea ce privește digrafele gradate, este convenabil să descrieți digrafele aciclice conectate în așa fel încât un nod să fie situat mai jos decât nodurile de care depinde.

Aplicații

Digrafele aciclice s-au conectat în primul rând pentru a reprezenta sisteme de distribuție a mărfurilor cu nodurile din partea de sus care le alimentează nodurile dependente. Aproape echivalent: permit reprezentarea sistemelor de decizie cu nodurile din partea de sus care dau ordine nodurilor lor dependente. ^{[ Ce înseamnă? ]}

Digrafele aciclice conectate permit apoi să schematizeze colecții de mulțimi între care există relații de incluziune compatibile cu relațiile de dependență, în sensul că dacă mulțimea Q depinde de mulțimea P trebuie să fie un subset de P ; printre subseturile lui P doar o parte este reprezentată de noduri ale digrafului, toate acestea sunt dependente de P , dar în general doar o parte din ele depinde direct de P. Seturile care corespund nodurilor digrafului trebuie considerate la fel de privilegiate, deoarece doar pe ele este posibil să se efectueze anumite operații care pot fi configurate ca operațiuni de acces; o relație de dependență corespunzătoare prezenței unui arc (p, q) în digraf spune că se poate conecta operațiunea de acces la q la operația de acces la p . Aceste digrame se referă, așadar, nu numai la subseturile unui mediu dat (pentru aceasta avem un zăbrele boolean , care este practic un digraf gradat), ci și anumite operațiuni de „acces” care le pot fi efectuate prin combinarea lor adecvată.

O aplicație mai bogată decât cea precedentă se referă la schematizarea categoriilor de containere de informații (seturi de șiruri) sau de containere de cunoștințe (seturi de documente). În acest caz, seturile care corespund nodurilor unui digraf aciclic conectat nu sunt considerate doar ca colecții de elemente, ci containere pentru care atribuirea șirurilor sau a documentelor poate fi problematică (entitățile de la care trebuie să începeți construirea digrafului ). Digrafele de acest fel pot fi numite digrame de categorizare .

Într-un digraf aciclic conectat este posibil să se identifice subdigrafele de anumite tipuri: AE, DB, A, DGC etc. Într-un digraf de categorizare, aceste subsisteme de categorii pot viza operațiuni importante de organizare a documentelor (într-o bibliotecă) și organizarea cunoștințelor (într-o enciclopedie). Graficul unui arbore elementar vă poate ajuta să înțelegeți defalcarea unei liste de înotători în subliste de înotători africani, americani, asiatici, europeni și oceanici. Și dacă doriți să faceți distincția între liberaliști, dorsiști, delfini, fluturiști, mistică și așa mai departe. se obține un arbore pe două niveluri. Situațiile de distribuție a informațiilor sau a cunoștințelor în funcție de mai multe puncte de vedere (de exemplu, puncte de vedere ale diferitelor discipline) conduc la digrame care nu pot fi reduse la arborescențe (categoria Termodinamicii poate depinde de categoria fizică și categoria chimică, ... ).

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică