Graficul dirijat

Un grafic direcționat (sau digraf pe scurt ) este un grafic (multi) căruia i se atribuie o direcție muchiilor. Muchiile direcționate sunt numite și arce , iar în unele surse sunt numite pur și simplu margini. Un grafic în care nicio muchie nu i se atribuie o direcție se numește grafic nedirecționat sau non- digraf .

Concepte de bază

Formal, un digraf constă dintr-o mulțime , ale cărei elemente sunt numite vârfuri , și un set de perechi ordonate de vârfuri .

Arcul este incident cu vârfurile și . În acest caz, ei spun că acesta  este vârful inițial al arcului și  este vârful final .

Un digraf obținut dintr -un grafic simplu prin orientarea muchiilor se numește direcționat . Spre deosebire de acesta din urmă, într-un digraf simplu arbitrar, două vârfuri pot fi conectate prin două arce direcționate diferit.

Un grafic complet direcționat se numește turneu .

Conectivitate

Un traseu într-un digraf este o succesiune alternantă de vârfuri și arce , de forma (vârfurile pot fi repetate). Lungimea traseului  este numărul de arce din acesta.

O cale este un traseu într-un digraf fără arce repetate, o cale simplă  este fără vârfuri repetate. Dacă există o cale de la un vârf la altul, atunci al doilea vârf este accesibil de la primul.

Un contur este o cale închisă .

Pentru o jumătate de traseu , restricția asupra direcției arcelor este eliminată, iar o jumătate de traseu și o jumătate de contur sunt definite în mod similar .

Un digraf este puternic conectat , sau pur și simplu puternic , dacă toate vârfurile sale sunt reciproc accesibile ; conectat unidirecțional , sau pur și simplu unidirecțional , dacă pentru oricare două vârfuri cel puțin unul este accesibil de la celălalt; slab conectat , sau pur și simplu slab , dacă se ignoră direcția arcelor, se obține un (multi)graf conectat;

Subgraful puternic maxim se numește componenta puternică ; componenta unilaterală și componenta slabă sunt definite în mod similar.

Condensarea unui digraf este un digraf ale cărui vârfuri sunt componente puternice , iar un arc în arată prezența a cel puțin un arc între vârfurile incluse în componentele corespunzătoare.

Definiții suplimentare

Un graf aciclic direcționat sau un bulgăre este un digraf fără contur.

Un grafic direcționat obținut dintr-unul dat prin schimbarea direcției muchiilor în sens opus se numește invers .

Imaginea și proprietățile tuturor digrafelor cu trei noduri

Legendă: S  este slab, OC  este unilateral, SS  este puternic, H  este un grafic direcționat, G  este un hamac (aciclic), T  este un turneu

Aplicarea digrafelor

Digrafele sunt utilizate pe scară largă în programare ca o modalitate de a descrie sisteme cu conexiuni complexe. De exemplu, una dintre principalele structuri utilizate în dezvoltarea compilatoarelor și în general pentru reprezentarea programelor de calculator este graficul fluxului de date.

Relații binare

O relație binară peste un purtător finit poate fi reprezentată ca un digraf . Relațiile antireflexive pot fi reprezentate printr-un digraf simplu ; în cazul general, este necesar un digraf cu bucle. Dacă relația este simetrică , atunci poate fi reprezentată printr -un graf nedirecționat , iar dacă este antisimetrică, atunci printr-un graf direcționat .

Diverse

Algoritmul lui Suurballe este un algoritm pentru găsirea a două căi care nu se intersectează (fără muchii comune) într-un grafic direcționat cu greutăți nenegative, astfel încât ambele căi să conecteze aceeași pereche de vârfuri și să aibă o lungime comună minimă.

Literatură

• Harari F. Teoria grafurilor. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .
• Ore, Oistin . Teoria grafurilor. — M .: URSS , 2008. — 352 p. - ISBN 978-5-397-00044-4 .
• Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compilatoare : Principii, tehnici și instrumente, ediția a 2-a = Compilatori: principii, tehnici și instrumente. - Ed. a II-a. - M .: „Williams” , 2008. - ISBN 978-5-8459-1349-4 .