Grafuri Orientate Def, Teoreme, Cod [PDF]

Zitiervorschau

Definiţii Se numeşte graf orientat sau digraf o pereche de mulţimi (X, U), unde X este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U este o mulţime de perechi ordonateformate cu elemente distincte din mulţimea X, numite arce. Mulţimea arcelor care ies dintr-un nod: ω + Mulţimea arcelor care intră într-un nod: ω-

În graful G=(X,U) avem: X = 1, 2, 3, 4, 5. U={ (5,3), (1, 2), (1, 3), (1,4), (1,5), (2,3), (2,4), (2, 5), (3,4), (4, 5)} Numim vârfuri adiacente orice pereche de vârfuri care formează un arc. Două vârfuri spunem că sunt incidente cu arcul pe care îl formează. Pentru arcul (x, y) spunem că x este extremitatea iniţială şi y este extremitatea finală. Spunem că doua arce sunt incidente dacă au o extremitate comună. Se numeşte succesor al vârfului x orice vârf la care ajunge un arc care iese din x. Mulţimea succesorilor se notează: Γ+. Se numeşte predecesor al vârfului x orice vârf de la care intră un arc în vârful x. Mulţimea predecesorilor se notează: Γ-. Gradul intern al unui nod este egal cu numărul arcelor care intră în nod şi se notează d-(x). Gradul extern al unui nod este egal cu numărul arcelor care ies din nod şi se notează d+(x).

Teoreme Teorema 1: Numărul total de grafuri orientate cu n noduri este n(n-1)/2; Teorema 2: Într-un graf orientat cu n noduri suma gradelor interne este egală cu suma gradelor externe şi este egală cu numărul arcelor.

Aplicaţii ale definiţiilor

Mulţimea arcelor care intră în nodul 2: ω +(2)= {(2, 5), (2, 3), (2, 4)}; Mulţimea arcelor care ies din nodul 2: ω- (2)={(1, 2)}; Nodurile 2 si 4 sunt adiacente. Pentru arcul (2, 3) spunem ca 2 este extremitatea iniţială şi 3 este extremitatea finală. Arcele (2, 3) şi (3, 4) sunt incidente. Nodul 4 este succesor al nodului 2. Nodul 2 este predecesor al nodului 4. Mulţimea succesorilor nodului 2: Γ+2= {3, 4, 5}; Mulţimea predecesorilor nodului 2: Γ-2={1}; Gradul extern al nodului 2: 3 Grad intern al nodului 2: 1 Graf

parţial

Fie graful G=(X,U). Se numeşte graf parţial al lui G, un graf G1=(X,V), cu V inclus în U. Altfel spus, un graf parţial al lui G este chiar G, sau se obţine din G, păstrând toate vârfurile şi suprimând nişte arce. Se consideră graful G=(X, U), în care X={1, 2, 3, 4, 5, 6} şi U={(2,1), (1, 3), (4, 3), (3, 5), (6,4), (5, 6). Graful parţial al lui G este G1=(X, V), în care X={1, 2, 3, 4, 5, 6} şi V={(2, 1), (3, 2), (4, 3), (6, 4), (5, 6)}.

Subgraf Fie graful G=(X, U). Un subgraf al lui G este un graf G2=(Y, V), unde Y inclus in U, iar V va conţine toate arcele din U, care au ambele extremităţi în Y. Altfel spus, un subgraf al unui graf se obţine eliminând nişte noduri şi arcele incidente acestor noduri. Se consideră graful G=(X, U), în care X={1, 2, 3, 4, 5, 6} şi U={ (2, 1), (1, 3), (3, 2), (4, 3), (3, 5), (6, 4), (5, 6). Subgraful lui G este G2=(Y, V), în care Y={3, 4, 5, 6} şi V={(4, 3), (3, 5), (6, 4), (5, 6).

Matricea de adiacenţă Matricea de adiacenţă este o matrice pătratică cu n linii şi n coloane, iar a[i][j] = 0, dacă nu există arc de la i la j sau a[i][j]=1, dacă există arc de la i la j.

Matricea de incidenţă Matricea de incidenţă este o matrice cu n linii şi m coloane. Pe fiecare coloană vom avea o valoare de 1 care corespunde extremităţii iniţiale a unui arc, o valoare de -1 care corespunde extremităţii finale a unui arc, toate celelalte fiind 0.

Lista arcelor Este formată din m elemente care conţin fiecare, câte o pereche de noduri, x şi y care formează un arc.

Lista vecinilor În lista vecinilor pentru fiecare nod se specifică succesorii.

Numim drum o succesiune de noduri care au proprietatea că oricare ar fi două noduri succesive acestea sunt legate printr-un arc. Numim circuit un drum în care toate arcele sunt distincte două câte două şi există un arc de la ultimul nod la primul (numărul minin de noduri este 3).

   

 

 

Un drum poate fi: Elementar - un drum care conţine doar noduri distincte. Neelementar - un drum care nu conţine doar noduri distincte. Simplu - un drum care conţine doar muchii distincte. Compus - un drum care nu conţine doar muchii distincte. Un circuit poate fi: Elementar - un circuit care conţine doar noduri distincte (cu excepţia primului şi a ultimului, care coincid). Neelementar - un circuit care nu conţine doar noduri distincte (cu excepţia primului şi a ultimului, care coincid). Observaţii! Noţiunea de lanţ/ciclu este valabilă şi în cazul grafurilor orientate (nu are importanţă sensul arcelor). La drumuri/circuite toate arcele trebuie să aibă aceeaşi orientare. Exemple de drumuri şi circuite



Drum elementar



Drum neelementar



Circuit elementar



Circuit neelementar

Un graf G se numeşte graf tare conex dacă are proprietatea că pentru oricare pereche de noduri diferite între ele există un drum. Dacă un graf orientat G nu este tare conex, se numeşte componentă tare conexă a grafului un subgraf tare conex al său maximal în raport cu această proprietate, adică conţine numărul maxim de noduri din G care au proprietatea că sunt legate printr-un drum. Un subgraf tare conex are o singură componentă tare conexă. Componenta tare conexă din care face parte un nod este dată de intersecţia dintre subgraful

predecesorilor şi subgraful succesorilor acelui nod. Graful componentelor tare conexe ale unui graf care nu este tare conex se obţine prin reducerea fiecărei componente conexe la un nod.

Graful G1 este tare conex, iar graful G2 nu este tare conex. Graful G2 are 3 componente conexe.

Graf tare conex Un graf G se numeşte graf tare conex dacă are proprietatea că pentru oricare pereche de noduri diferite între ele există un drum. Dacă un graf orientat G nu este tare conex, se numeşte componentă tare conexă a grafului un subgraf tare conex al său maximal în raport cu această proprietate, adică conţine numărul maxim de noduri din G care au proprietatea că sunt legate printr-un drum. Un subgraf tare conex are o singură componentă tare conexă. Componenta tare conexă din care face parte un nod este dată de intersecţia dintre subgraful predecesorilor şi subgraful succesorilor acelui nod. Graful componentelor tare conexe ale unui graf care nu este tare conex se obţine prin reducerea fiecărei componente conexe la un nod.

Graful G1 este tare conex, iar graful G2 nu este tare conex. Graful G2 are 3 componente conexe.