grafuri - conectivitate. arbori. cautare. grafuri …mircea.marin/lectures/tgc/...1 c autarea ^ n l...

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

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


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


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.


2.


4.


{x, e}

Raza grafului este

2.


4.

Marin, M. Grafuri


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.


2.


4.


{x, e}

Raza grafului este

2.


4.

Marin, M. Grafuri


Exemplu

x

e

x

e

zr

a cu

v

s


Excentricitatea lui x este 2.Excentricitatea lui z este

4.


{x, e}

Raza grafului este

2.


4.

Marin, M. Grafuri


Exemplu

x

e

x

e

zr

a cu

v

s


Excentricitatea lui x este 2.Excentricitatea lui z este 4.


{x, e}

Raza grafului este

2.


4.

Marin, M. Grafuri


Exemplu

x

e

x

e zr

a cu

v

s



Centrul grafului este {x, e}Raza grafului este

2.


4.

Marin, M. Grafuri


Exemplu

x

e

x

e zr

a cu

v

s



Centrul grafului este {x, e}Raza grafului este 2.


4.

Marin, M. Grafuri


Exemplu

x

e

x

e zr

a cu

v

s



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


π: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


π: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


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


π: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


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


π: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


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


π: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


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


π: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


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


π: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


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


π: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


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



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



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


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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



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


x 7→ [v ]y 7→ [x ]w 7→ [y , z ]u 7→ [v , x ]v 7→ [y ]z 7→ [z ]


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

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


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


Exemplu ilustrat

a

c

e

n

r


c r a x e n


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


Exemplu ilustrat

a

c

e

n

r


c r a x e n


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

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

grafuri - conectivitate. arbori. cautare. grafuri …mircea.marin/lectures/tgc/...1 c autarea ^ n l...

Documents