ALGORITMICA GRAFURILOR

09-10

C. Croitoru

săptămâna 4
AGENDA

 Probleme de drum ı̂n (di)grafuri

(ag 09-10 [Link] pag. 68 −→ )

 Problemele pentru seminarul 4

♦♦

1
 Probleme de drum

Parcurgeri

BFS

DFS

Componente conexe, tari conexe !!! (pen-

tru examen; algoritmică uşoară !!!)

2
 Probleme de drum
Drumuri de cost minim

P1 Date G digraf;a : E(G) → R; s, t ∈ V (G),s = t.

∗ ∈ D , astfel ı̂ncı̂t
Să se determine Dst st
a(Dst∗ ) = min{a(D ) | D ∈ D }.
st st st

P2 Date G digraf; a : E(G) → R; s ∈ V (G).

∗ ∈ D ∀i ∈ V (G), a.ı̂.
Să se determine Dsi si
a(Dsi∗ ) = min{a(D ) | D ∈ D }.
si si si

P3 Date G digraf; a : E(G) → R.

∗ ∈ D ∀i, j ∈ V (G), a.ı̂.
Să se determine Dij ij
a(Dij∗ ) = min{a(D ) | D ∈ D }.
ij ij ij

3
 Probleme de drum minim

Rezolvarea problemei P2

Teoremă. 1. Fie G = (V, E) digraf, V =

{1, . . . , n}, s ∈ V şi a : E → R, astfel ı̂ncı̂t

(I) ∀C circuit ı̂n G, a(C) > 0.

Atunci (u1, . . . , un) este o soluţie a sistemu-
lui
⎧
⎪
⎨ us = 0
(∗) ∀i = s.
⎪
⎩ ui = min (uj + aji )
j=i

dacă şi numai dacă

∗ ∈ D
∀i ∈ V , ∃Dsi ∗
si astfel ı̂ncı̂t a(Dsi ) = ui şi
∗ ) = min{a(D) | D ∈ D }.
a(Dsi si

4
 Probleme de drum minim

O numerotare aciclică a (vârfurilor) digrafu-

lui G = (V, E) este un vector ord[v] v ∈ V ,
(cu interpretarea ord[v] = numărul de ordine
al vârfului v) a. ı̂.

∀vw ∈ E ⇒ ord[v] < ord[w].

G este un digraf fără circuite dacă şi numai

dacă admite o numerotare aciclică .

Sortare topologică O(n + m).

Rezolvarea sistemului (∗) prin substituţie.

5
 Probleme de drum minim
Algoritmul lui Dijkstra aij ≥ 0 !!!

1. S ← {s}; us ← 0; ı̂nainte[s] ← 0;
for i ∈ V \ {s} do
{ ui ← asi; ı̂nainte[i] ← s }
// după aceste iniţializări (D) are loc
2. while S = V do
{
determină j ∗ ∈ V \ S : uj ∗ = min{uj | j ∈ V \ S};
S :← S ∪ {j ∗};
for j ∈ V \ S do
if uj > uj ∗ + aj ∗ j then
{ uj ← uj ∗ + aj ∗j ; ı̂nainte[j] ← j ∗ }
}

Complexitatea timp a algoritmului, ı̂n descrierea dată

este O(n2) .
Este posibilă organizarea unor cozi cu prioritate (de
exemplu heap-urile) pentru obţinerea unui algoritm cu
complexitatea O(m log n) (unde m = |E|) Johnson ,1977).

Cea mai bună implementare se obţine utilâzând heap-

uri Fibonacci, ceea ce conduce la o complexitate timp
de O(m + n log n) (Fredman şi Tarjan, 1984).
6
 Probleme de drum minim
Rezolvarea lui P2 ı̂n cazul general.

Algoritmul lui Bellman, Ford, Moore (∼ 1960)

s ← 0; for i ∈ V \ {s} do ui ← asi ;

1. u1 1

// evident (BM) are loc

2. for m := 1 to n − 2 do
for i := 1 to n do
 
m+1
ui ← min ui , minj=i(uj + aji )
m m

Complexitatea O(n3), dacă determinarea min-

imului din pasul 2 necesită O(n) operaţii.

Testarea ı̂n O(n3) a existenţei unui circuit C

de cost negativ ı̂n digraful G !

7
 Problemele pentru seminarul 4

Problema 1. Să se construiască o funcţie care să

recunoască un turneu. La intrare aceasta va primi un
digraf G = ({1, ..., n}, E) reprezentat cu ajutorul listelor
de adiacenţă şi va returna true sau f alse. Stabiliţi com-
plexitatea timp a algoritmului folosit.

Problema 2. Să se construiască o funcţie care prim-

ind la intrare un digraf G = ({1, ..., n}, E) reprezentat cu
ajutorul listelor de adiacenţă să returneze inversul lui G
reprezentat cu ajutorul listelor de adiacenţă. Complexi-
tatea timp a algoritmului folosit trebuie să fie O(n+|E|).

Problema 3. Se consideră un graf G = ({1, ..., n}, E)

reprezentat cu ajutorul matricii de adiacenţă. Mulţimea
de n − 1 muchii A are proprietatea că T = (V, A) este ar-
bore parţial al lui G. Construiţi un algoritm care să
listeze cele m − n + 1 circuite care se formează prin
adăugarea muchiilor din E−A la T (|E| = m). Reprezentarea
lui T trebuie să permită depistarea fiecărui astfel de cir-
cuit ı̂n timpul O(n).

8
Problema 4. Să se construiască o funcţie
care să determine gradul maxim al unui vârf al
unui graf. La intrare aceasta va primi un graf
G = ({1, ..., n}, E) reprezentat cu ajutorul lis-
telor de adiacenţă şi va returna Δ(G). Stabiliţi
complexitatea timp a algoritmului folosit.

Problema 5. Construiţi o funcţie care pri-

mind la intrare graful G = (V, E) reprezen-
tat cu ajutorul listelor de adiacenţă şi k, un
număr ı̂ntreg pozitiv, returnează graful G(k) cu
aceeaşi mulţime de virfuri ca şi G , ı̂n care două
virfuri distincte sunt adiacente dacă şi numai
dacă ı̂n graful iniţial sunt conectate printr-un
drum de lungime cel mult k. Care este com-
plexitatea timp a construcţiei ?

Problema 6. Pentru graful conex G = (V, E)

cu n vârfuri şi m muchii, se dispune de o repre-
zentare cu ajutorul listelor de adiacenţă. Descrieţi
un algoritm, cu complexitatea timp O(n + m),
pentru construcţia listelor de adiacenţă ale unui
arbore parţial al lui G.
9
Problema 7. Fie G = (V, E) un graf cu ordinul |V | ≥ 2
şi T = (V, ET ) un arbore parţial al lui G, reprezentat
cu ajutorul tabloului (p[v])v∈V , unde p[v] este părintele
lui v ı̂n T : vârful dinaintea lui v de pe drumul unic
de la o rădăcină fixată r, la v, ı̂n T ( pentru r avem
p[r] = r). Descrieţi un algoritm care să determine, ı̂n
timpul O(|V |), un vârf v0 pendant (frunză) ı̂n T şi apoi
demonstraţi că G − v0 este conex.

Problema 8. Fie G = (V, E) un digraf reprezentat cu

ajutorul listelor de adiacenţă. Descrieţi un algoritm de
complexitate timp O(|V | + |E|) care să decidă dacă se
pot ordona vârfurile sale: vi1 , . . . , vi|V | , astfel ı̂ncât dacă
vij apare ı̂n lista de adiacenţă a lui vik atunci k < j.

Problema 9. Fie T = (V, ET ) un arbore cu mulţimea

vârfurilor V = {1, . . . , n} (n ≥ 2), reprezentat cu ajutorul
tabloului (p[v])v∈V , unde p[v] este părintele lui v ı̂n T :
vârful dinaintea lui v de pe drumul unic de la o rădăcină
fixată r, la v, ı̂n T ( pentru r avem p[r] = r). Descrieţi
un algoritm care să construiască , ı̂n timpul O(n), listele
de adiacenţă ale lui T .

10
Problema 10. Se consideră un graf G = (V, E) (V =
{1, . . . , n}), izomorf cu graful circuit (cu cel puţin 3
vârfuri), G = ∼ Cn. Fiecare muchie e ∈ E are asociat
un cost real c(e). Aceste informaţii sunt disponibile ı̂n
tablourile dreapta şi cost de dimensiune n cu semnificaţia:
dreapta[v] = vecinul din dreapta al lui v, iar costul muchiei
{v, dreapta(v)} este cost[v]. Descrieţi un algoritm cât mai
eficient pentru aflarea unui arbore parţial al lui G de cost
minim.

Problema 11. Se consideră un graf G = (V, E) (V =

{1, . . . , n}), reprezentat cu ajutorul listelor de adiacenţă.
Se ştie că graful are gradul minim δ(G) mărginit de o
constantă c ∈ N. Descrieţi un algoritm cu complexitatea
timp O(n) pentru determinarea lui δ(G) şi a unui vârf
v0 ∈ V cu gradul ı̂n G egal cu δ(G).

Problema 12. Se consideră un grafurile G1 şi G2 (

Gi = (Vi , Ei) , Vi = {1, . . . , ni}, (i=1,2)) reprezentate
cu ajutorul matricilor de adiacenţă A1 şi A2. Scrieţi (ı̂n
pseudocod) un algoritm pentru construirea listelor de
adiacenţă ale grafului G1 × G2 .

11
 Problemele pentru seminarul special 4

• Problema 1, Setul 3”
– Aceasta e o problemă foarte interesantă pentru că oferă
o caracterizare algoritmică a unei clase de grafuri. Utilă
pentru ı̂nţelegerea df s.

• Problema 3, Setul 4
– Exerciţiu util. Tripartiţia evidenţiată la a) poate fi con-
struită algoritmic ! Rezultatul de la b) e util ı̂n recunoaşterea
grafurilor cordale.

12