Grupa 2 :"Grafuri orientate"

Panda Patricia, Pantiru Dan, Giurgiu Ovidiu, Ile Bogdan



Într-un grup sunt n elevi, băieţi şi fete, pe care-i numerotăm 1, 2, ..., n. Fiecare elev cunoaşte o parte din ceilalţi elevi. Relaţia de cunoştinţă nu este neaparat reciprocă (dacă x îl cunoaşte pe z, nu înseamnă că şi y trebuie să-l cunoască pe x). Unul dintre elevi are un CD foarte valoros, cu multe jocuri demonstrative, pe care toţi membrii grupului vor să-l aibe fie şi pentru scurt timp, pentru a şi-l copia pe calculatorul propriu. CD-ul circulă printre membrii grupului în felul următor: fiecare elev după ce l-a primit de la altcineva îl dă mai departe, dar numai unui elev pe care îl cunoaşte, pentru că nu doreşte să ajungă în mâna unor persoane în care nu poate avea încredere.

Determinaţi o modalitate (dacă există) prin care CD-ul să circule pe la fiecare elev o singură dată, transmiterea lui făcându-se numai către o cunoştinţă, iar în final CD-ul să ajungă din nou la proprietarul său.

Indicaţie: Pentru a rezolva cerinţa trebuie să construiţi un circuit elementar care să cuprindă toţi elevii grupului, pornind de la elevul care are CD-ul valoros.




Răspuns posibil: Mihai - Ionuţ - Ioana - Sanda - Ştefan - Andreea - Mihai.


Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt arcele în graf, iar intersecţiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraş” este neorientat.

Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă.

Alte exemple ar fi: circulaţia sângelui în organism (sângele circulă prin artere de la inimă în corp, şi prin vene din corp spre inimă), cunoştinţele (există persoane pe care le cunoaştem, dar ele nu ne cunosc pe noi, sau persoane care ne cunosc, dar noi nu le cunoaştem, sau persoane care ne cunosc şi le cunoaştem).


Nodul 2 nu are grad extern si pentru a se forma circuit din nodul 2 trebuie sa mai existe inca 2 arce, unul din nodul 2 in nodul 3 si unul din nodul 3 in nodul 4. Astfel se poate forma un circuit din fiecare nod.








De la vârful 4 avem arc in varful 5 apoi in varful 1 apoi in varful 2 si apoi in varful 6.
Sunt 4 arce din nodul 4 pana la nodul 6 si nu exista drum mai lung.








Din nodul 1 pleaca 3 arce si intra 1, iar din nodul 4 pleaca un arc si nu intra niciunul.

Restu nodurilor au gradul intern mai mare decat cel extern.

În concluzie sunt 2 noduri care au gradul extern mai mare decat cel intern.






Există arc de la nodurile 5 la 4, de la 4 la 2, de la 2 la 1, de la 1 la 6, de la 6 la 3 si de la 3 la 2.
În concluzie, lungimea drumului este 6.







Folosim teorema 4 la puterea n(n-1)/2.
Inlocuim pe n cu numarul de noduri si rezultatul este 4 la puterea a 6-a.





Parcurgere în lăţime



Parcurgere în adâncime

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.


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





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.









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).




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 ordonate formate 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



Copyright 2009 - Grupa 2 :"Grafuri orientate"

Blogspot Theme designed by: Ray Creations, Ray Hosting.