Post on 26-Jul-2020
transcript
GrafuriConectivitate. Arbori. Cautare. Grafuri bipartite.
Arbori de acoperire
Mircea Marin
29 noiembrie 2019
Marin, M. Grafuri
Cuprins
Conectivitate
Arbori de acoperire
Cautare
algoritmi de parcurgere ın latime si adancime
aplicatii: sortare topologica,determinarea componentelor conexe, etc.
cautarea ın grafuri bipartite
algoritmul lui Dijkstra
Grafuri bipartite si cuplaje
Arbori minimi de acoperire
algoritmul lui Kruskal
Marin, M. Grafuri
Conectivitate
Fie G = (V ,E ) un graf si x , y ∈ V . x este conectat cu y daca
cazul 1: G este neorientat si contine un lant (engl. chain) de la x la y :
x y
cazul 2: G este orientat si contine un drum (engl. walk) de la x la y :
x y
G este conex daca orice doua noduri sunt conectate.
Exemplu: grafuri conexe si grafuri neconexe
G1 G2 G3 G4
G1,G2
sunt conexe. G3, G4 nu sunt conexe.
Marin, M. Grafuri
Conectivitate
Fie G = (V ,E ) un graf si x , y ∈ V . x este conectat cu y daca
cazul 1: G este neorientat si contine un lant (engl. chain) de la x la y :
x y
cazul 2: G este orientat si contine un drum (engl. walk) de la x la y :
x y
G este conex daca orice doua noduri sunt conectate.
Exemplu: grafuri conexe si grafuri neconexe
G1 G2 G3 G4
G1,G2
sunt conexe. G3, G4 nu sunt conexe.
Marin, M. Grafuri
Conectivitate
Fie G = (V ,E ) un graf si x , y ∈ V . x este conectat cu y daca
cazul 1: G este neorientat si contine un lant (engl. chain) de la x la y :
x y
cazul 2: G este orientat si contine un drum (engl. walk) de la x la y :
x y
G este conex daca orice doua noduri sunt conectate.
Exemplu: grafuri conexe si grafuri neconexe
G1 G2 G3 G4
G1,G2
sunt conexe. G3, G4 nu sunt conexe.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Fie G = (V ,E ) un graf si x , y ∈ V a.ı. x este conectat cu y .
Distanta d(x , y) de la x la y este1 lungimea celui mai scurt lant de la x la y , daca G este
neorientat, sau2 lungimea celui mai scurt drum de la x la y daca G este
orientat.
Daca G este conex, atunci:
Excentricitatea lui x ın G este distanta cea mai mare de la xla un nod ın G : e(x) := max{d(x , y) | y ∈ V }Centrul lui G este multimea de noduri cu excentricitateminima: u ∈ V este ın centru daca e(u) = min{e(x) | x ∈ V }.Raza lui G este excentricitatea unui nod din centrul lui G .Diametrul lui G este excentricitatea maxima a unui nod din G :diam(G ) := max{e(x) | x ∈ V }
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e
zr
a cu
v
s
Distanta de la x la c este
2.
Distanta de la r la z este
4.
Excentricitatea lui x este
2.
Excentricitatea lui z este
4.
Centrul grafului este
{x, e}
Raza grafului este
2.
Diametrul grafului este
4.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e
zr
a cu
v
s
Distanta de la x la c este 2.Distanta de la r la z este
4.
Excentricitatea lui x este
2.
Excentricitatea lui z este
4.
Centrul grafului este
{x, e}
Raza grafului este
2.
Diametrul grafului este
4.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e
zr
a cu
v
s
Distanta de la x la c este 2.Distanta de la r la z este 4.
Excentricitatea lui x este
2.
Excentricitatea lui z este
4.
Centrul grafului este
{x, e}
Raza grafului este
2.
Diametrul grafului este
4.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e
zr
a cu
v
s
Distanta de la x la c este 2.Distanta de la r la z este 4.
Excentricitatea lui x este 2.Excentricitatea lui z este
4.
Centrul grafului este
{x, e}
Raza grafului este
2.
Diametrul grafului este
4.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e
zr
a cu
v
s
Distanta de la x la c este 2.Distanta de la r la z este 4.
Excentricitatea lui x este 2.Excentricitatea lui z este 4.
Centrul grafului este
{x, e}
Raza grafului este
2.
Diametrul grafului este
4.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e zr
a cu
v
s
Distanta de la x la c este 2.Distanta de la r la z este 4.
Excentricitatea lui x este 2.Excentricitatea lui z este 4.
Centrul grafului este {x, e}Raza grafului este
2.
Diametrul grafului este
4.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e zr
a cu
v
s
Distanta de la x la c este 2.Distanta de la r la z este 4.
Excentricitatea lui x este 2.Excentricitatea lui z este 4.
Centrul grafului este {x, e}Raza grafului este 2.
Diametrul grafului este
4.
Marin, M. Grafuri
Distante si conectivitatedistanta, excentricitate, centru, raza, diametru
Exemplu
x
e
x
e zr
a cu
v
s
Distanta de la x la c este 2.Distanta de la r la z este 4.
Excentricitatea lui x este 2.Excentricitatea lui z este 4.
Centrul grafului este {x, e}Raza grafului este 2.
Diametrul grafului este 4.
Marin, M. Grafuri
Arbori
Arbore = graf simplu conectat si fara cicluri.
Exemple
I Sunt arbori:
G1 G2 G3
I Nu sunt arbori:
H1 H2 H3
Remarca: Orice arbore poate fi redesenat ın mod uzual: cu unnod radacina r conectat cu vecinii lui desenati sub r , si
orice nod x 6= r are un vecin deasupra lui (parintele lui x)
toti ceilalti vecini sunt sub x (copiii lui x)
Marin, M. Grafuri
Arbori
Arbore = graf simplu conectat si fara cicluri.
Exemple
I Sunt arbori:
G1 G2 G3
I Nu sunt arbori:
H1 H2 H3
Remarca: Orice arbore poate fi redesenat ın mod uzual: cu unnod radacina r conectat cu vecinii lui desenati sub r , si
orice nod x 6= r are un vecin deasupra lui (parintele lui x)
toti ceilalti vecini sunt sub x (copiii lui x)
Marin, M. Grafuri
Arbori si paduri
I Exemple de redesenari uzuale ale arboreluix a
z
u
v
:
x a z
u
v
saux
a z
u
v
saua
x z
u
v
sau
xa
z
u v sau
xa
z
u
v
I O padure este un arbore ale carui componente sunt arbori.
Observatii
1 Un graf simplu este padure daca si numai daca nu are cicluri.
2 Orice arbore cu n noduri are n − 1 muchii.
3 Orice padure cu n noduri si k arbori are n − k muchii. Deexemplu, padurea
.
. . .
. .
.
. .
.. .
.
.
. .
are 16 noduri, 3 arbori, si 16-3=13 muchii.
Marin, M. Grafuri
Arbori si paduri
I Exemple de redesenari uzuale ale arboreluix a
z
u
v
:
x a z
u
v
saux
a z
u
v
saua
x z
u
v
sau
xa
z
u v sau
xa
z
u
v
I O padure este un arbore ale carui componente sunt arbori.
Observatii
1 Un graf simplu este padure daca si numai daca nu are cicluri.
2 Orice arbore cu n noduri are n − 1 muchii.
3 Orice padure cu n noduri si k arbori are n − k muchii. Deexemplu, padurea
.
. . .
. .
.
. .
.. .
.
.
. .
are 16 noduri, 3 arbori, si 16-3=13 muchii.
Marin, M. Grafuri
Arbori si paduri
I Exemple de redesenari uzuale ale arboreluix a
z
u
v
:
x a z
u
v
saux
a z
u
v
saua
x z
u
v
sau
xa
z
u v sau
xa
z
u
v
I O padure este un arbore ale carui componente sunt arbori.
Observatii
1 Un graf simplu este padure daca si numai daca nu are cicluri.
2 Orice arbore cu n noduri are n − 1 muchii.
3 Orice padure cu n noduri si k arbori are n − k muchii. Deexemplu, padurea
.
. . .
. .
.
. .
.. .
.
.
. .
are 16 noduri, 3 arbori, si 16-3=13 muchii.
Marin, M. Grafuri
Arbori de acoperire
Fie G = (V ,E ) un graf simplu conex. T este un arbore deacoperire al lui G daca:
1 T este arbore
2 T se obtine din G stergand doar muchii.
Observatii
1 Orice arbore de acoperire al unui graf simplu conex G se poateobtine repetand pasul urmator pana cand G nu mai are cicluri:
Se cauta un ciclu C ın G si se sterge o muchie a lui C din G
2 Daca G este graf simplu (posibil neconex), putem obtine o padurede acoperire a lui G repetand pasul urmator pana cand G nu maiare cicluri:
Se cauta un ciclu C ın G si se sterge o muchie a lui C din G
Marin, M. Grafuri
ConectivitateObservatii preliminare
Vom considera 2 tipuri de grafuri simple G = (V ,E ):
Grafuri neorientate: nu contin bucle, iar ıntre doua noduri existacel mult o muchie.
Grafuri orientate: nu contin bucle, iar de la un nod la altul existacel mult o muchie.
I Spunem ca se poate ajunge de la un nod s la un nod x ın Gdaca exista un lant (daca G este neorientat) sau un drum(daca G este orientat) de la s la x .
I Descoperirea tuturor nodurilor la care se poate ajunge de laun nod sursa s se poate face cu un algoritm de cautare.
I Cei mai cunoscuti algoritmi de cautare sunt:1 cautarea ın latime (BFS, breadth-first search)2 cautarea ın adancime (DFS, depth-first search)
Marin, M. Grafuri
ConectivitateCautarea ın latime (Breadth First Search)
Exploreaza sistematic muchiile lui G pt. a gasi toate nodurile lacare se poate ajunge de la un nod sursa s.
Caracteristici ale cautarii ın latime
Pentru fiecare nod x la care se poate ajunge din s, calculeazadistanta d [x ] (cel mai mic nr. de muchii) de la s la x .
Construieste un arbore Gπ cu radacina s cu urmatoareleproprietati:
1 contine toate nodurile la care se poate ajunge din s.2 pentru orice nod x din Gπ, ramura lui Gπ de la s la x este una
din cele mai scurte cai de la s la x ın G .
Algoritmul este incremental: pentru fiecare distanta posibilak > 0, alg. descopera mai ıntai toate nodurile la distanta k des ınainte de a descoperi nodurile la distanta k + 1 de s.
Marin, M. Grafuri
Cautarea ın latime (BFS)Cum se calculeaza arborele Gπ si distantele d [x ]?
Presupunem ca G = (V ,E) este reprezentat cu liste de adiacenta.
Fiecarui nod x al lui G i se atribuie (1) o culoare c[x] care este alb (a), gri (g)
sau negru (n) si (2) un predecesor π[x] ın arborele Gπ . Initial
c[x ] = a pentru toti x ∈ V − {s}, c[s] = g.d [x ] =∞ pentru toti x ∈ V − {s}, d [s] = 0.π[x ] =Nil pentru toti x ∈ V .
Un nod devine descoperit cand cautarea ajunge prima oara la el.
Un nod x se coloreaza gri atunci cand devine descoperit, si negru imediat dupace toti vecinii lui devin descoperiti.
Lista nodurilor gri existente la un moment dat se retine ın o coada Q first-in,
first-out (FIFO), ın ordinea descoperirii lor.
Initial, Q = [s].
Pt. fiecare nod gri y ∈ Q, se scaneaza nodurile adiacente la y . Pentru fiecare
vecin alb x al lui y :
x se coloreaza gri (pt. ca devine descoperit), se adauga la Q,si d [x ] := d [y ] + 1, π[x ] := y
Apoi, y se coloreaza negru.
Marin, M. Grafuri
Cautarea ın latime (BFS)Pseudocod
BFS(G , s)1. for fiecare nod u ∈ V − {s} do2. c[u] := w
3. d [u] :=∞4. π[u] :=Nil5. c[u] := g
6. d [s] := 07. π[s] :=Nil8. Q := [s]9. while Q 6= [] do10. u :=Dequeue(Q)11. for fiecare vecin v al lui u do12. if c[v ] == w then13. c[v ] := g
14. d [v ] := d [u] + 115. π[v ] := u16. Enqueue(Q, v)17. c[u] := n
Timp de executie: O(|V |+ |E |)
Marin, M. Grafuri
Cautarea ın latime (BFS)Afisarea unei cai cu nr. minim de muchii de la nodul sursa s la un nod x (pseudocod)
AfiseazaCale(G , s, x)1 if x == s then print s2 else3 if π[x] == Nil then4 print ”nu exista cale de la ” s ” la ” x5 else6 AfiseazaCale(G , s, π[x])7 print x
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
v
v w
π:w
d :2
π:w
d :2
t
x
t
xv
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:
Q = [r, w]Q = [w, v]Q = [v, t, x]Q = [t, x]Q = [x, u]Q = [u, y]Q = [y]Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
r
r
π:r
d :2
v
v w
π:w
d :2
π:w
d :2
t
x
t
xv
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:Q = [r, w]
Q = [w, v]Q = [v, t, x]Q = [t, x]Q = [x, u]Q = [u, y]Q = [y]Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
v
v
w
π:w
d :2
π:w
d :2
t
x
t
xv
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:
Q = [r, w]
Q = [w, v]
Q = [v, t, x]Q = [t, x]Q = [x, u]Q = [u, y]Q = [y]Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
v
v w
π:w
d :2
π:w
d :2
t
x
t
x
v
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:
Q = [r, w]Q = [w, v]
Q = [v, t, x]
Q = [t, x]Q = [x, u]Q = [u, y]Q = [y]Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
vv
w
π:w
d :2
π:w
d :2
t
x
t
xv
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:
Q = [r, w]Q = [w, v]Q = [v, t, x]
Q = [t, x]
Q = [x, u]Q = [u, y]Q = [y]Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
vv
w
π:w
d :2
π:w
d :2
t
x
t
xv
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:
Q = [r, w]Q = [w, v]Q = [v, t, x]Q = [t, x]
Q = [x, u]
Q = [u, y]Q = [y]Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
vv
w
π:w
d :2
π:w
d :2
t
x
t
xv
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:
Q = [r, w]Q = [w, v]Q = [v, t, x]Q = [t, x]Q = [x, u]
Q = [u, y]
Q = [y]Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
vv
w
π:w
d :2
π:w
d :2
t
x
t
x
v
t
π:t
d :3
u
u
xπ:x
d :3
y
y
u
y
Continutul listei curente:
Q = [r, w]Q = [w, v]Q = [v, t, x]Q = [t, x]Q = [x, u]Q = [u, y]
Q = [y]
Q = [ ]
Marin, M. Grafuri
Cautarea ın latime (BFS)Exemplu ilustrat: cautare pornind de la sursa s
π:Nil
d :0
s
Q = [s]
w
r
Q = [s]
s
π:s
d :1
π:s
d :1
w
r
w
rr
π:r
d :2
vv
w
π:w
d :2
π:w
d :2
t
x
t
x
v
t
π:t
d :3
uu
xπ:x
d :3
yy
u
y
Continutul listei curente:
Q = [r, w]Q = [w, v]Q = [v, t, x]Q = [t, x]Q = [x, u]Q = [u, y]Q = [y]
Q = [ ]
Marin, M. Grafuri
Cautarea ın latimeProprietati
Algorimul BFS construieste arborele predecesor Gπ = (Vπ ,Eπ) al lui G = (V ,E) unde
Vπ := {s} ∪ {v ∈ V | π[v ] 6= Nil},Eπ := (π[v ], v) | v ∈ Vπ − {s}}.
Proprietati:
1 Vπ este mt. tuturor nodurilor la care se poate ajunge din s.
2 Fiecare ramura de la s la un nod x ın Gπ este o cale cu nr. minim de muchii dela s la x ın G .
Remarca: Gπ pentru graful din exemplul ilustrat estes
r w
vt x
u y
Nivel 1: noduri la distanta 1 de sursa s
Nivel 2: noduri la distanta 2 de sursa s
Nivel 3: noduri la distanta 3 de sursa s
Marin, M. Grafuri
Cautarea ın adancime (Depth First Search)Comparatie cu cautarea ın latime (BFS)
Gaseste toate nodurile la care putem ajunge de la un nod sursa s cu ometoda de explorare a muchiilor grafului diferita de cea a BFS:
Se cauta mai ıntai noduri nedescoperite ınvecinate cu cel mai recentnod descoperit.
Daca ultimul nod descoperit nu are vecini nedescoperiti, se revine cucautarea la nodul descoperit anterior (engl. backtracking)
Asemanari cu DFS:
Retine predecesorii nodurilor x de-a lungul cailor gasite ıntr-untablou π[x ]
Pe durata cautarii, distinge 3 tipuri de noduri:
albe (a): nodurile nedescoperite ıncagri (g): nodurile descoperitenegre (n): nodurile descoperite, cu toti vecinii descoperiti
De regula, presupunem ca G este reprezentat cu liste de adiacenta.
Marin, M. Grafuri
Cautarea ın adancime (DFS)Caracteristici ale cautarii ın adancime
Pentru fiecare nod x la care se poate ajunge din s, retine douavalori temporale (numere ıntregi):
d [x ]: momentul descoperirii nodului xf [x ]: momentul finalizarii examinarii nodului x (cand noduldevine negru)
Construieste o padure Gπ = (V ,Eπ) undeE = {(π[v ], v) | v ∈ V − {s}}.Gπ are urmatoarele proprietati:
1 Fiecare arbore contine toate nodurile la care se poate ajungede la radacina lui.
2 Unul din arbori are radacina s.
Diferenta esentiala dintre DFS si BFS este ca
DFS retine ıntr-o stiva S nodurile gri care urmeaza sa fiefinalizate.BFS le retine ıntr-o lista FIFO Q.
Marin, M. Grafuri
Cautarea ın adancime (DFS)Pseudocod (versiunea iterativa)
DFS(G , s)1. for fiecare nod u ∈ V do2. c[u] := a
3. π[u] :=Nil4. timp := 05. S := []6. for fiecare nod u ∈ V , ıncepand cu s do7. if c[u] == a then8. timp := timp + 1; c[u] := g; d [u] := timp9. Push(S , u)10. while S 6= [] do11. v :=Pop()12. for fiecare vecin x al lui v do13. if c[x] == a then14. timp := timp + 1; c[x] := g; d [x] := timp; π[x] := v15. Push(S, x)16. timp := timp + 1; c[v ] := n; f [v ] := timp
Timp de executie O(|V |+ |E |)
Marin, M. Grafuri
Cautarea ın adancime (DFS)Pseudocod (versiunea recursiva)
DFS(G , s)1. for fiecare nod u ∈ V do2. c[u] := a
3. π[u] :=Nil4. timp := 05. S := []6. for fiecare nod u ∈ V , ıncepand cu s do7. if c[u] == a then8. DFS Visit(u)
1. DFS Visit(u)2. timp := timp + 1; c[u] := g; d [u] := timp3 for fiecare vecin v al lui u do4. if c[v ] == a then5. π[v ] := u6. DFS Visit(v)7. timp := timp + 1; c[u] := n; f [u] := timp
Remarca: In aceasta versiune, utilizarea unei stive este implicita.
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
zy
x
v
x
y
π:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:S = [u]
S = [u]S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
zy
x
v
x
y
π:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]
S = [v, u]
S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
z
y
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]
S = [y, v, u]
S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
z
y
x
v
x
y
π:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]
S = [x, y, v, u]
S = [ ]S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
z
y
x
v
x
y
π:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]S = [y, v, u]
S = [y, v, u]
S = [x, y, v, u]S = [ ]S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
z
y
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]
S = [v, u]
S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
z
y
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]
S = [u]
S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
z
y
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]
S = [ ]
S = [ ]S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
z
y
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]
S = [w]
S = [w]S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
zy
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
zπ:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]S = [w]S = [w]
S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
zy
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
z
π:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]S = [ ]S = [w]
S = [w]
S = [z, w]
Marin, M. Grafuri
Cautarea ın adancime (dfs)Exemplu ilustrat
Digraf G = (V ,E ) cu nodul sursa u ilustrat mai jos:π :Nil
d :1
v
π:Nil
d :
x
v
π:u
d :2
π:Nil
d :
y
π:v
d :3
u
v
w
y z
zy
x
v
x
yπ:Nil
d :
π:y
d :4
x
f :
f :5
x
f :
y
f :6
f :
vf :7
f :
uf :
uf :8
π:Nil
d :
w
π:Nil
d :9
w
zzπ:Nil
d :
z
π:w
d :10
f :
f :11
z
f :
wf :12
Reprezentarea lui G culiste de adiacenta
x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]
Continutul stivei curente:
S = [u]S = [u]S = [v, u]S = [v, u]S = [y, v, u]S = [y, v, u]S = [x, y, v, u]S = [ ]
S = [ ]
S = [w]S = [w]S = [z, w]
Marin, M. Grafuri
Aplicatii ale algoritmilor de cautare
Ambii algoritmi construiesc un arbore de acoperire pentrusubgraful lui G ce contine toate nodurile la care se poateajunge din nodul sursa.
Daca G este conex, Gπ este un arbore de acoperire al lui G .
Aplicatii ale cautarii ın latime (BFS):
Gaseste caile cele mai scurte de la s la nodurile la care sepoate ajunge din s
I Cautarea ın adancime nu garanteaza aceasta proprietate.
Aplicatii ale cautarii ın adancime (DFS):
1 Calculul tuturor componentelor conexe ale lui G .
2 Detectia ciclurilor ın grafuri orientate (vezi mai departe)
3 Sortarea topologica a grafurilor orientate fara cicluri (vezi maideparte)
Marin, M. Grafuri
Sortare topologica
Terminologie:
Un graf orientat aciclic (engl. dag) este un graf orientat fara cicluri.
O sursa a unui dag este un nod s cu deg−(s) = 0. O destinatie aunui dag este un nod t cu deg+(t) = 0.
O sortare (sau numerotare) topologica a unui dag G = (V ,E )atribuie un ıntreg distinct I[x ] fiecarui nod x , astfel ıncat
I[u] < I[v ] pentru fiecare arc ue−→ v ∈ E .
Remarca: Orice dag poate fi desenat ıncat toate arcele sa fie orientateın jos. Aceasta reprezentare permite calculul unei sortari topologice adag-ului respectiv.
Exemplu
a
x
u v
n
z
I[a] = 1
I[n] = 2 I[x] = 3
I[u] = 4, I[v] = 5
I[z] = 6
a este sursa a dag-ului.
z este destinatie a dag-ului.
Marin, M. Grafuri
Sortare topologica
Terminologie:
Un graf orientat aciclic (engl. dag) este un graf orientat fara cicluri.
O sursa a unui dag este un nod s cu deg−(s) = 0. O destinatie aunui dag este un nod t cu deg+(t) = 0.
O sortare (sau numerotare) topologica a unui dag G = (V ,E )atribuie un ıntreg distinct I[x ] fiecarui nod x , astfel ıncat
I[u] < I[v ] pentru fiecare arc ue−→ v ∈ E .
Remarca: Orice dag poate fi desenat ıncat toate arcele sa fie orientateın jos. Aceasta reprezentare permite calculul unei sortari topologice adag-ului respectiv.
Exemplu
a
x
u v
n
z
I[a] = 1
I[n] = 2 I[x] = 3
I[u] = 4, I[v] = 5
I[z] = 6
a este sursa a dag-ului.
z este destinatie a dag-ului.
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime (DFS)1. Detectia ciclurilor si sortarea topologica
Cautarea ın adancime (DFS) ne permite ca pentru un graf orientatG = (V ,E )
1 Sa detectam daca G are cicluri sau nu.
G are un ciclu daca si numai daca are o muchie (u, v) cud [v ] < d [u] < f [u] < f [v ].(Vezi Cormen et al.: Introduction to Algorithms, cap. 22)
⇒ putem verifica ın timp O(|V |+ |E |) daca G este dag sau nu.
2 Daca G este dag (adica nu are cicluri), sa calculam o sortaretopologica pentru G :
I[x ] := 2 · |V | − f [x ] pentru toti x ∈ V
o sortare topologica se poate gasi ın timp O(|V |+ |E |)
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Input: un dag G = (V ,E ) cu n noduri, si s ∈ VOutput: lungimile maxime L[v ] de drumuri simple de la s1. se calculeaza o numerotare topologica {I[v ] | v ∈ V }
ın timp O(|V |+ |E |)2. Fie [v1, . . . , vn] nodurile lui V ın ordine topologica crescatoare
si k indexul pentru care s = vk3. L[vk ] := 0;4. for i := k + 1 to n do L[vi ] := −∞;5. for i := k + 1 to n6. for fiecare (vi ,w) ∈ E do7. if L[w ] < L[vi ] + 1 then L[w ] = L[vi ] + 1;8. endfor9. endfor
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Exemplu ilustrat
a
c
e
n
r
xare sortarea topologica
c r a x e n
Lungimi maximede la nodul c: 0 −∞ −∞ −∞ −∞ −∞
c r a
1 1 −∞ −∞ −∞
r a x
2 2 −∞ −∞
a x e n
3 3 3
x e n
4 4
e n
5
Observatii
Pentru grafuri arbitrare, calculul celor mai lungi drumurisimple de la un nod este o problema dificila (NP-completa)Pentru dag-uri, calculul celor mai lungi drumuri simple sepoate face ın timp liniar O(|V |+ |E |).
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Exemplu ilustrat
a
c
e
n
r
xare sortarea topologica
c r a x e n
Lungimi maximede la nodul c: 0 −∞ −∞ −∞ −∞ −∞
c r a
1 1 −∞ −∞ −∞
r a x
2 2 −∞ −∞
a x e n
3 3 3
x e n
4 4
e n
5
Observatii
Pentru grafuri arbitrare, calculul celor mai lungi drumurisimple de la un nod este o problema dificila (NP-completa)
Pentru dag-uri, calculul celor mai lungi drumuri simple sepoate face ın timp liniar O(|V |+ |E |).
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Exemplu ilustrat
a
c
e
n
r
xare sortarea topologica
c r a x e n
Lungimi maximede la nodul c: 0 −∞ −∞ −∞ −∞ −∞
c r a
1 1 −∞ −∞ −∞
r a x
2 2 −∞ −∞
a x e n
3 3 3
x e n
4 4
e n
5
Observatii
Pentru grafuri arbitrare, calculul celor mai lungi drumurisimple de la un nod este o problema dificila (NP-completa)Pentru dag-uri, calculul celor mai lungi drumuri simple sepoate face ın timp liniar O(|V |+ |E |).
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Exemplu ilustrat
a
c
e
n
r
xare sortarea topologica
c r a x e n
Lungimi maximede la nodul c: 0 −∞ −∞ −∞ −∞ −∞
c r a
1 1 −∞ −∞ −∞
r a x
2 2 −∞ −∞
a x e n
3 3 3
x e n
4 4
e n
5
Observatii
Pentru grafuri arbitrare, calculul celor mai lungi drumurisimple de la un nod este o problema dificila (NP-completa)Pentru dag-uri, calculul celor mai lungi drumuri simple sepoate face ın timp liniar O(|V |+ |E |).
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Exemplu ilustrat
a
c
e
n
r
xare sortarea topologica
c r a x e n
Lungimi maximede la nodul c: 0 −∞ −∞ −∞ −∞ −∞
c r a
1 1 −∞ −∞ −∞
r a x
2 2 −∞ −∞
a x e n
3 3 3
x e n
4 4
e n
5
Observatii
Pentru grafuri arbitrare, calculul celor mai lungi drumurisimple de la un nod este o problema dificila (NP-completa)Pentru dag-uri, calculul celor mai lungi drumuri simple sepoate face ın timp liniar O(|V |+ |E |).
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Exemplu ilustrat
a
c
e
n
r
xare sortarea topologica
c r a x e n
Lungimi maximede la nodul c: 0 −∞ −∞ −∞ −∞ −∞
c r a
1 1 −∞ −∞ −∞
r a x
2 2 −∞ −∞
a x e n
3 3 3
x e n
4 4
e n
5
Observatii
Pentru grafuri arbitrare, calculul celor mai lungi drumurisimple de la un nod este o problema dificila (NP-completa)Pentru dag-uri, calculul celor mai lungi drumuri simple sepoate face ın timp liniar O(|V |+ |E |).
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime2. Calculul lungimilor maxime de drumuri simple de la un nod s ıntr-un dag
Exemplu ilustrat
a
c
e
n
r
xare sortarea topologica
c r a x e n
Lungimi maximede la nodul c: 0 −∞ −∞ −∞ −∞ −∞
c r a
1 1 −∞ −∞ −∞
r a x
2 2 −∞ −∞
a x e n
3 3 3
x e n
4 4
e n
5
Observatii
Pentru grafuri arbitrare, calculul celor mai lungi drumurisimple de la un nod este o problema dificila (NP-completa)Pentru dag-uri, calculul celor mai lungi drumuri simple sepoate face ın timp liniar O(|V |+ |E |).
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime3. Determinarea componentelor conexe ale unui graf neorientat
Daca G este graf neorientat, atunci padurea Gπ calculata de DFSeste formata din arbori de acoperire pentru componentele conexeale lui G .
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime4. Determinarea componentelor conexe ale unui graf orientat
Orice graf orientat poate fi descompus ın mod unic ıncomponente distincte.
Daca G contine un ciclu Cn, atunci Cn este continut ıntr-ocomponenta conexa a lui G .
Daca G contine un nod v cu deg+(v) = 0 atunci {v} este ocomponenta conexa a lui G .
Exemplu
1 7
2 34
5 6 8
9
1 7
2 34
5 6 8
9
Componentele conexe sunt:
C1 = {7} (nod pendant)C2 = {1, 2, 3, 4, 5}C3 = {6, 8, 9}
Marin, M. Grafuri
Aplicatii ale cautarii ın adancime4. Determinarea componentelor conexe ale unui graf orientat
Orice graf orientat poate fi descompus ın mod unic ıncomponente distincte.
Daca G contine un ciclu Cn, atunci Cn este continut ıntr-ocomponenta conexa a lui G .
Daca G contine un nod v cu deg+(v) = 0 atunci {v} este ocomponenta conexa a lui G .
Exemplu
1 7
2 34
5 6 8
9
1 7
2 34
5 6 8
9
Componentele conexe sunt:
C1 = {7} (nod pendant)C2 = {1, 2, 3, 4, 5}C3 = {6, 8, 9}
Marin, M. Grafuri
Determinarea componentelor conexe ale unui graf orientatContractia unei multimi de noduri ıntr-un graf orientat
Fie G = (V ,E ) un graf orientat si S ⊆ V .Contractia lui S ın G este graful construit astfel:
I se elimina nodurile lui S din G ⇒ graful G1 = G − S
I se adauga la G1 un nod nou x etichetat cu S , si se adauga:
cate o muchie ue−→ x pentru fiecare muchie u
e−→ v ∈ E cuv ∈ S .cate o muchie x
e−→ w pentru fiecare muchie ve−→ w ∈ E cu
v ∈ S .
Exemplu
Contractia lui {x, y} ın
a z
x c
vs
este graful orientat
a z
{x, c}
vs
Marin, M. Grafuri
Determinarea componentelor conexe ale unui graf orientatPseudocod
Input: graf orientat G = (V ,E )Output: componentele conexe ale lui G1. while E 6= ∅ do2. Se construieste cu dfs un drum P pana se detecteaza
un ciclu C sau un nod destinatie t;3. if t a fost gasit then
Se retine ca {t} este componenta conexa a lui G ;Se elimina t din G si P;
endif4. if C a fost gasit
Se contracta nodurile lui C ın G ;endif
5. endwhile
Marin, M. Grafuri
Determinarea componentelor conexe ale unui graf orientatExemplu ilustrat
1 7
2 34
5 6 8
9
Consider ciclul (1,2,3,1)
⇒
{1, 2, 3} 7
4
5 6 8
9
Consider ciclul
({1, 2, 3}, 5, 4, {1, 2, 3})
⇒
{1, 2, 3, 4, 5} 7
6 8
9
Consider drumul bfs
({1, 2, 3, 4, 5}, 7)
{1, 2, 3, 4, 5} {7}
6 8
9
Am gasit componenta {7}Consider drumul dfs
(6, {1, 2, 3, 4, 5})
⇒
{1, 2, 3, 4, 5} {7}
6 8
9
Am gasit componenta
{1, 2, 3, 4, 5}Consider ciclul (9,6,8,9)
⇒
{1, 2, 3, 4, 5} {7}
{6, 8, 9}
Marin, M. Grafuri