Algoritmul Roy-Floyd (Roy-Warshall)

Parcurgerea în adâncime a grafurilor orientate

Parcurgerea în adâncime a grafurilor orientate

Se pune conditia de parcurgere a vecinilor oricarui nod, indiferent de sens. Parcurgerea în adâncime se caracterizează prin faptul că se merge „în adâncime” ori de câte ori este posibil. 

 Parcurgerea începe cu vâful iniţal, denumit vâful de start, care este şi vizitat. 
 Se vizitează apoi primul vecin nevizitat al vâfului de start. Vârful y este considerat vecin al vâfului x dacă există arcul (x,y) (pentru graful orientat). 

Se vizitează în continuare primul vecin nevizitat al primului vecin al vâfului de start, şi aşa mai departe, mergând în adâncime, până când ajungem într-un vârf care nu mai are vecini nevizitaţi. Când ajungem într-un astfel de vârf, revenim la vârful său părinte (vârful din care acest nod a fost vizitat). Dacă acest nod mai are vecini nevizitaţ, alegem primul vecin nevizitat al său şi continuă parcurgerea în acelaşi mod. Dacă nici acest vârf nu mai are vecini nevizitaţi, revenim în vârful să păirnte şi continuăm în acelaş mod, până când toate vâfurile accesibile din vârful de start sunt vizitate. 

Arbori

Definitia 1: Se numeste Arbore cu rădacină = graf neorientat conex fără cicluri în care unul din noduri este desemnat ca rădăcină. Nodurile pot fi aşezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.

Rădăcină = Nod special care generează aşezarea unui arbore pe niveluri; Această operaţie se efectuează în funcţie de lungimea lanţurilor prin care celelalte noduri sunt legate de rădăcină.

Descendent = într-un arbore cu rădăcină nodul y este descendentul nodului x dacă este situat pe un nivel mai mare decât nivelul lui x şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Descendent direct /  fiu = într-un arbore cu rădăcină nodul y este fiul (descendentul direct) nodului x dacă este situat pe nivelul imediat următor nivelului lui x şi există muchie între x şi y.

Ascendent = într-un arbore cu rădăcină nodul x este ascendentul nodului y dacă este situat pe un nivel mai mic decât nivelul lui y şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Ascendent direct / părinte = într-un arbore cu rădăcină nodul x este părintele (ascendentul direct) nodului y dacă este situat pe nivelul imediat superior (cu număr de ordine mai mic) nivelului lui y şi există muchie între x şi y.

Fraţi = într-un arbore cu rădăcină nodul x este fratele nodului y dacă au acelaşi părinte.

Frunză =  într-un arbore cu rădăcină nodul x este frunză dacă nu are nici un descendent direct

Arbore cu rădăcină

- Nodul 1 este rădăcină. - Nodurile 5, 6, 7 sunt fii nodului 3. - Nodul 7 este părintele nodurilor 9 şi 10; - Nodul 9 este descendentul lui 3 - Nodul 3 este ascendentul lui 10 - Nodurile 8, 9 şi 10 sunt frunze - Nodurile 5, 6 şi 7 sunt fraţi.

Metode de memorare a arborilor

Cum un arbore este un caz particular de graf neorientat inseamna ca poate fi reprezentat ca un graf. De aici rezulta ca pentru reprezentarea unui arbore se pot utiliza:

1.        Metode specifice grafurilor:

-matricea de adiacenta

-liste de adiacente

2.        Metode specifice arborilor:

-prin legaturi de tip TATA. Arborele se reprezinta sub forma unui vector t cu n componente (n reprezinta numarul de noduri). Daca t[i]=k atunci nodul I este descendent al nodului k. Daca nodul I este varf atunci t[i]=0.

Fie arboreal din figura:

 unde nodul 1 este radacina.  Atunci vectorul de tip tata este:

0

1

1

1

3

3

3

4

7

7

Legatura de tip TATA se mai numeste si legatura cu referinte ascendente.

Legatura de tip TATA este determinata si de modul in care am ales nodul radacina. Spre exemplu daca vom considera nodul 4 ca fiind radacina vom obtine o alta solutie.

Metode de parcurgere:

Metodele de parcurgere sunt cele specifice grafurilor: in adancime si in latime.

grafuri

Definiţie

Se numeşte graf neorientat G=(X,U) o pereche de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri (vârfuri) iar U o mulţime de perechi, formate cu elemente distincte din mulţimea X numite muchii.

Se numesc noduri adiacente orice pereche de noduri între care există o muchie.

ex:muchia (1,2)

Spunem că un nod este incident cu o muchie daca nodul reprezintă o extremitate pentru aceea muchie.

ex:nodul 1 este incident cu muchia (1,2)

Spunem ca 2 muchii sunt incidente daca au un nod comun .

ex: muchia (1,2), (1,3) au nodul 1 comun

Nodurile vecine unui nod sunt toate noduriile adiacente cu nodul respectiv.

Gradul unui nod X al grafului G este egal cu numarul de muchii incidente cu nodul respectiv şi se noteaza cu d(x).

ex:d(3)=5

Un nod care are gradul 1 se numeşte nod terminal.

ex: d(4)=1

Un nod care are gradul 0 se numeşte vârf izolat.

ex: d(7)=0

Numim lanţ o succesiune de noduri cu proprietatea că oricare ar fi 2 noduri successive ele sunt adiacente.

Se numeşte ciclu ,un lanţ în care toate muchiile sunt distincte 2 câte 2 şi între primul şi ultimul nod există o muchie.

Se numeşte lungimea unui lanţ ,numărul de muchii din care este format.

Se numeşte lanţ elementar,un lanţ care conţine doar noduri distincte.

Se numeşte lanţ simplu,un lanţ care conţine doar muchii distincte.

Un lanţ care nu este simplu se numeşte lanţ compus.

Se numeşte un ciclu elementar,ciclul în care toate nodurile sunt distincte 2 câte 2; excepţie primul şi ultimul nod.

Observaţii :
Orice lanţ elementar este un lanţ simplu.

Nu este ciclu lanţul compus deoarece muchiile nu sunt distincte 2 câte 2.

TEOREME :
Numărul total de grafuri neorientate este:
2 la puterea Cn2 = 2 la puterea [n(n-1)]/2
Suma gradelor tuturor noduriilor unui graf neorientat este egală cu dublul nr. de muchii.
Dacă graful G neorientat are n noduri, iar n>2 atunci cel puţin 2 noduri au acelaşi grad.
Pentru orice graf neorientat,numărul noduriilor de grad impar este par.
Numărul minim de muchii pe care trebuie să le conţina un graf neorientat cu n noduri ca să nu existe vârfuri izolate este [(n+1)/2].

Moduri de reprezentare a grafurilor în memorie
a) Matrice de adiacenţă
Matricea de adiacenţă este o matrice patratică cu n linii şi m coloane .
Fiecare element i,j este de forma
aij= 0,dacă nu există muchie între nodul i şi nodul j;
1,dacă există muchie între nodul i şi nodul j.

Observatii :
1) Diagonala principală este întotdeauna egală cu 0.
2) Matricea este simetrică faţă de diagonala principală.

b) Matricea de incidenţă
Are n linii(n=numărul de noduri) şi m coloane (m=numărul de muchii).
! Pe fiecare coloană există 2 valori de 1 care reprezintă extremităţile unei muchii; toate celelalte elemente fiind 0.

Grafuri speciale

Graful G se numeşte nul dacă mulţimea U este vidă (nu are muchii).
Un graf se numeşte complet dacă are proprietatea că oricare 2 noduri ale sale sunt adiacente.
Teoremă: Numărul de muchii ale unui graf complet cu n noduri este
[n(n-1)]/2.
Se numeşte graf parţial al lui G=(X,U) graful Gp=(X,V) unde V este egal sau inclus în U (din graful G eliminăm muchii).
Se numeşte subgraf al lui G=(X,U), Gs=(Y,V) unde Y este egal sau inclus în X şi toate muchiile din mulţimea V aparţin şi mulţimii U,care au ambele extremităţi în mulţimea Y,adică se obţine din graful G prin eliminarea unor noduri şi a tuturor muchilor incidente cu acestea.
Se numeşte graf complementar al lui G,graful Gc care are propritatea că 2 noduri sunt adiacente în graful complementar dacă şi numai dacă nu sunt adiacente în graful G.
Teoremă: Numărul grafurilor parţiale ale unui graf cu m muchii este 2 la puterea m.
Teoremă: Numărul de subgrafuri ale unui graf cu n noduri este 2ⁿ-1.
Conexitate
Definitie:

1) Un graf G se numeşte graf conex dacă are proprietatea că pentru orice pereche de noduri distincte există un lanţ care le leagă.
2) Dacă un graf G nu este conex se numeşte componentă conexă a grafului, un subgraf conex
al său maximal în raport cu această proprietate (conţine numărul maxim de noduri din graful G care au proprietatea că sunt legate de un lanţ).

Teoreme:
1) Numărul minim de muchii necesare pentru ca un graf neorientat să fie conex este: n-1,unde n reprezintă numărul de noduri.
2) Un graf conex cu n noduri şi n-1 muchii este aciclic şi maximal în raport cu această proprietate.
3) Dacă un graf neorientat conex are n noduri şi m muchii, numărul de muchii care trebuie eliminate pentru a obţine un graf parţial conex aciclic este: m-n+1.
4) Dacă un graf are n noduri şi m muchii şi p componente conexe, numărul de muchii care trebuie eliminat pentru a obţine un graf parţial aciclic(arbore) este egal cu: m-n+p.
5) Pentru a obţine dintr-un graf neorientat conex 2 componente conexe numărul minim de muchii care trebuie eliminate este egal cu gradul minim din graf.
6) Numărul maxim de muchii dintr-un graf cu n noduri şi p componente conexe este [(n-p)(n-p+1)]/2.
Grafuri speciale

Un graf G se numeşte graf bipartit dacă există două mulţimi nevide de noduri A si B care au proprietatea: A ∩ B= Ø iar A U B=X şi orice muchie din mulţimea U are o extremitate în mulţimea A şi o altă extremitate în mulţimea B.
Un graf bipartit se numeşte graf bipartit complet dacă pentru oricare nod X care aparţine mulţimii A şi orice nod Y care aparţine mulţimii B există o muchie care le leagă.

Se numeşte lanţ Hamiltonian,lanţul care conţine toate nodurile grafului şi este elementar.
Un graf care conţine un ciclu Hamiltonian se numeşte graf Hamiltonian.
Un ciclu se numeşte eulerian,ciclul elementar ce conţine toate muchiile grafului.
Se numeşte graf eulerian,graful care conţine un ciclu eulerian.

TEOREME

1) Un graf cu mai mult de 2 noduri este Hamiltonian dacă graful fiecărui nod este mai mare sau egal decât n/2.
2) Un graf ce nu conţine vârfuri izolate este eulerian dacă şi numai dacă este conex iar gradele tuturor noduriilor sunt numere pare.
3) Numărul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1)!/2.

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 

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

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