cursul 8 - tipuri de grafuri. structuri de date pentru grafuri
Post on 28-Jan-2017
311 Views
Preview:
TRANSCRIPT
Cursul 8Tipuri de grafuri. Structuri de date pentru grafuri.
Conectivitate: Algoritmul naiv si algoritmul lui Warshall
noiembrie 2016
Cursul 8
Reamintim ca:
Graf = structura matematica G = (V ,E ) unde
V : multime de noduri (sau varfuri)
E : multime de muchii incidente la doua noduri, sau la 1 nod
Tipuri de grafuri, ın functie de tipul muchiilor e ∈ E :
I Neorientate: Fiecare muchie are 2 capete
Reprezenare grafica:a b sau a (bucla)e
e
I Orientate (sau digrafuri): Fiecare muchie e ∈ E are o sursa (saustart) si o destinatie (sau end)
Reprezentare grafica:a b sau a (bucla)e
e
Muchiile orientate se numesc si arce (singular: arc).
Graf simplu: graf neorientat sau orientat, care are cel mult un arc ıntreorice doua noduri si nu are nici o bucla.
Cursul 8
Tipuri de grafuri frecvent ıntalniteTaxonomie
G = (V ,E )
e1, e2 ∈ E sunt muchii paralele daca sunt incidente la aceleasinoduri si
Daca G este orientat, atunci start(e1) = start(e2) siend(e1) = end(e2)
I Multigraf orientat sau neorientat: nu are bucle, iar dacagraful este
neorientat: poate avea muchii paraleleorientat: pooate avea arce paralele
I Pseudograf: graf neorientat care poate avea muchii paralelesi bucle.
I Graf ponderat: fiecare muchie e ∈ E are o pondere (saugreutate) w(E ); de obicei w(e) ∈ R.
Cursul 8
Reprezentari grafice ale grafurilorExemple
I Grafuri simple: se traseaza linii sau sageti ıntre nodurileconectate
Graf simplu neorientat:a
b c
d
e
Graf simplu orientat:a
b c
d
e
I Grafuri simple ponderate: se indica ponderea ın dreptulconexiunilor
a
e
b c
d
f
2
7
1
5
12
14
9
3
Cursul 8
Reprezentari grafice ale grafurilorExemple (continuare)
Multigrafuri sau pseudografuri: daca au muchii paralele pe carevrem sa le distingem, se etichetam muchiile:
multigraf:
a
b
c d
e2
e3
e4
e5e6
e1
pseudograf:
a
b
c d
e2
e3
e4
e5e6
e1
e9
e7
e8
Cursul 8
Reprezentari concrete ale grafurilor simple
1 Lista de noduri + lista de muchii
2 Liste de adiacenta
3 Matrice de adiacenta
4 Matrice de incidenta
5 Matrice de ponderi
Cursul 8
Grafuri simpleReprezentarea cu lista de noduri + lista de muchii
Exemplu
a
b c
d
e
Lista de noduri V = [a, b, c, d , e]Lista de muchii E = [{a, b}, {a, c}, {a, d}, {b, c}, {c, e}, {d , e}]Observatii: {a, b} = {b, a}, {a, c} = {c, a}, etc.
muchie ↔ multimea de noduri adiacente la muchie
a
b c
d
e
Lista de noduri V = [a, b, c, d , e]Lista de arce E = [(a, b), (c, a), (c, b), (d , a), (e, c), (e, d)]Observatii: (a, b) 6= (b, a), (a, c) 6= (c, a), etc.
muchie ↔ pereche (start,end)
Remarca
Daca nu exista noduri izolate (cu 0 vecini), nu este necesar sa fieretinuta lista de noduri V :
I V se poate calcula din E
Cursul 8
Grafuri simpleReprezentarea cu liste de adiacenta
Pentru fiecare nod u ∈ V se retine lista de noduri adiacente la u
I Daca G este neorientat, v este adiacent la u daca exista omuchie cu capetele u si v .
In grafuri neorientate, relatia de adiacenta este simetrica.
I Daca G este orientat, v este adiacent la u daca exista un arce ∈ E de la u la v , adica start(e) = u si end(e) = v .
Exemplu
a
b c
d
e
a 7→ [b, c, d ]b 7→ [a, c]c 7→ [a, b, e]
d 7→ [a, e]e 7→ [c, d ]
a
b c
d
e
a 7→ [b]b 7→ []c 7→ [a, b]
d 7→ [a]e 7→ [c, d ]
Cursul 8
GrafuriReprezentarea cu matrice de adiacenta AG
Daca G are n noduri, AG = (mij) are dimensiunea n × n si
mij := numarul de muchii de la al i-lea nod la al j-lea nod.
Observatii
1 Inainte de a construi MG din G , trebuie fixata o enumerare atuturor nodurilor: [v1, v2, . . . , vn]
2 Daca G este neorientat, AG este matrice simetrica
3 Daca G este graf simplu, AG contine doar 0 si 1
Cursul 8
Grafuri neorientateMatricea de adiacenta AG a unui graf neorientat G
Matricea de adiacenta a grafului neorientat
G :a
b c
d
e
pentru enumerarea de noduri [a, b, c , d , e] este
AG =
0 1 1 1 01 0 1 0 01 1 0 0 11 0 0 0 10 0 1 1 0
Observatie: AG este matrice simetrica.
Cursul 8
GrafuriDigraful corespunzator unei matrici simetrice de adiacenta
Daca A este o matrice simetrica n× n cu aij ∈ N pentru toti i , j , undigraf G care are matricea de adiacenta A se construieste astfel:
1 Se deseneaza n puncte v1, . . . , vn ın plan
2 Pentru orice i , j ∈ {1, . . . , n} , se traseaza aij muchii distincteıntre vi si vj
Exemplu
A =
0 1 0 21 0 1 00 1 0 12 0 1 0
⇒ G :
v1
v2 v3
v4
Cursul 8
DigrafuriMatricea de adiacenta AG a unui digraf G
Matricea de adiacenta a grafului orientat
G :a
b c
d
e
pentru enumerarea de noduri [a, b, c , d , e] este
AG =
0 1 0 0 00 0 0 0 01 1 0 0 01 0 0 0 00 0 1 1 0
Cursul 8
DigrafuriDigraful corespunzator unei matrici de adiacenta
Daca A este o matrice n× n cu aij ∈ N pentru toti i , j , un digraf Gcare are matricea de adiacenta A se construieste astfel:
1 Se deseneaza n puncte v1, . . . , vn ın plan
2 Pentru orice i , j ∈ {1, . . . , n} , se traseaza aij arce distincte dela vi la vj
Exemplu
A =
0 1 0 20 0 1 00 1 1 11 0 0 0
⇒ G :
v1
v2 v3
v4
Cursul 8
Digrafuri cu muchii etichetateReprezentarea cu matrice de incidenta
Presupunem date doua liste (sau enumerari):
V = [v1, . . . , vn] a nodurilor lui G
L = [e1, . . . , ep] a etichetelor de muchii din G
Matricea de incidenta MG = (mij) are dimensiunea n × p si
mij =
−1 daca start(ej) = vi1 daca end(ej) = vi0 ın toate celelalte cazuri.
Exemplu
Daca V = [a, b, c , d , e], L = [e1, e2, e3, e4, e5, e6, e7, e8] si
MG =
−1 0 0 −1 1 0 0 −11 −1 0 0 0 1 0 00 1 −1 1 −1 0 0 00 0 1 0 0 0 1 10 0 0 0 0 −1 −1 0
⇒e d
c
b
a
e 1e2
e 3
e4
e5e 6
e8
e7
Cursul 8
Grafuri simple ponderateReprezentarea cu matrice de ponderi
Matricea de ponderi WG = (wij) a unui graf simplu ponderat G cun noduri [v1, . . . , vn] are dimensiunea n × n si
B wii = 0 pentru toti 1 ≤ i ≤ n.
B wij = w({vi , vj}) pentru orice muchie {vi , vj} ∈ E , daca Geste neorientat.
B wij = w((vi , vj)) pentru orice arc (vi , vj) ∈ E , daca G esteorientat.
B wij =∞ ın toate celelalte cazuri.
Exemplu (Digraf ponderat cu enumerare de noduri [a, b, c , d , e, f ])
G : a
e
b c
d
f
2
7
1
5
12
1
4
9
3
⇒WG =
0 3 ∞ ∞ 4 ∞∞ 0 2 ∞ ∞ ∞∞ 9 0 ∞ 1 12∞ ∞ ∞ 0 ∞ 7∞ 5 ∞ 1 0 ∞∞ ∞ ∞ ∞ ∞ 0
Cursul 8
Reprezentarea grafurilorStudiu comparativ
I Reprezentarea cu lista de muchii
Adecvata pentru reprezentarea grafurilor simple fara noduriizolate, cu |E | � |V |Complexitate spatiala (memorie ocupata): O(|E |)
I Reprezentarea cu liste de adiacenta
Permite enumerarea rapida a vecinilor unui nodComplexitate spatiala (memorie ocupata): O(|V |+ |E |)
I Reprezentarea cu matrice de adiacenta AG = (aij) sau cumatrice de ponderi WG = (wij)
Test rapid de conectivitate directa ıntre 2 noduri: O(1)
@(vi , vj) ∈ E daca aij = 0 sau daca wij = ∞Complexitate spatiala (memorie ocupata): O(|V |2)
- reprezentare neadecvata cand |E | � |V |2
Reprezentare cu matrice de incidenta MG
I Complexitate temporala: O(|V | · |E |)
Cursul 8
Digrafuri simpleProprietati ale matricii de adiacenta AG
Presupunem ca G este (di)graf simplu cu n noduri si matricea deadiacenta AG = (aij)
aij = 0 (sau false) daca @ arc vi → vjaij = 1 (sau true) daca ∃ arc vi → vj
Definim:
In : matricea identitate n × n
Operatiile booleene � (conjunctie) si ⊕ (disjunctie):� 0 1
0 0 01 0 1
⊕ 0 1
0 0 11 1 1
Observatii:a� b = min(a, b)a⊕ b = max(a, b)
Daca U = (uij), V = (vij) sunt matrici n × n cu elemente 0sau 1, definim
U ⊕ V = (cij) daca cij = uij ⊕ vij pentru toti i , jU � V = (dij) daca dij = (ui1 � v1j)⊕ . . .⊕ (uin � vnj)Uk = U � . . .� U︸ ︷︷ ︸
k ori
pentru orice k > 0
Cursul 8
Digrafuri simpleProprietati ale matricii de adiacenta AG (continuare)
Proprietati
1 Daca AkG = (a
(k)ij ) pentru k ≥ 1 atunci a
(k)ij = 1 daca si numai
daca exista o cale cu lungimea k de la nodul vi la vj .
2 Fie A∗G = In ⊕ AG ⊕ A2G ⊕ . . .⊕ An−1
G = (aij). Atunci
aij = 1 daca si numai daca exista o cale de lungimej ∈ {1, . . . , n − 1} de la nodul vi la vj .A∗G se poate calcula ın O(n4).
A∗G se numeste ınchidere reflexiva si tranzitiva a lui AG .
3 vi si vj sunt conectate ⇔ ∃ o cale simpla vi vj ⇔ aij = 1.
4 In ⊕ AG ⊕ A2G ⊕ . . .⊕ Ak+1
G = In ⊕ (In ⊕ AG ⊕ A2G ⊕ . . .⊕ Ak
G )�AG
⇒ A∗ se poate calcula ın O(n4).
Corolar
Conectivitatea ıntr-un digraf simplu se poate detecta ın O(n4).
Cursul 8
Digrafuri simpleProprietati ale matricii de adiacenta AG (continuare)
Proprietati
1 Daca AkG = (a
(k)ij ) pentru k ≥ 1 atunci a
(k)ij = 1 daca si numai
daca exista o cale cu lungimea k de la nodul vi la vj .
2 Fie A∗G = In ⊕ AG ⊕ A2G ⊕ . . .⊕ An−1
G = (aij). Atunci
aij = 1 daca si numai daca exista o cale de lungimej ∈ {1, . . . , n − 1} de la nodul vi la vj .A∗G se poate calcula ın O(n4).
A∗G se numeste ınchidere reflexiva si tranzitiva a lui AG .
3 vi si vj sunt conectate ⇔ ∃ o cale simpla vi vj ⇔ aij = 1.
4 In ⊕ AG ⊕ A2G ⊕ . . .⊕ Ak+1
G = In ⊕ (In ⊕ AG ⊕ A2G ⊕ . . .⊕ Ak
G )�AG
⇒ A∗ se poate calcula ın O(n4).
Corolar
Conectivitatea ıntr-un digraf simplu se poate detecta ın O(n4).
Cursul 8
Digrafuri simpleMetode mai eficiente de calcul al lui A∗
G
Algoritmul lui Warshall calculeaza A∗G ın O(n3).
Idee de baza a lui Warshall
Daca V = [v1, . . . , vn] este o enumerare a nodurilor lui G sivk ∈ V , atunci orice cale simpla π : vi vj are una dinurmatoarele forme:
1 vk nu apare ın π ca nod intermediar ıntre vi si vj
vi vj
vk
2 vk apare exact o data ın π ca nod intermediar ıntre vi si vj
vi vj
vk
Cursul 8
Digrafuri simpleAlgoritmul lui Warshall de calcul al lui A∗
G
Presupunem ca AG = (aij) are dimensiune n × n
I Se calculeaza recursiv C [n] = (c[n]ij ) unde
c[k]ij :=
{aij daca k = 0
c[k−1]ij ⊕ (c
[k−1]ik � c
[k−1]kj ) daca k ≥ 1
Proprietati
1 C [0] = AG
2 c[k]ij = 1 daca si numai daca exista o cale π : vi vj ın care
toate nodurile intermediare sunt din submultimea {v1, . . . , vk}3 C [n] = A∗G4 C [n] se calculeaza ın O(n3).
Cursul 8
Digrafuri simple ponderateCele cea mai usoare cai
Se considera digraful simplu G = (V ,E ) cu V = {1, . . . , n} sifunctia de greutate w : E → R+
I In G , greutatea unei cai π : v1 → v2 → . . .→ vp este
w(π) =∑p−1
i=1 w((vi , vi+1))(se aduna greutatile tuturor arcelor din π)
I Pentru orice pereche de noduri (i , j) din V , se doreste gasirea
celei mai usoare cai de la nodul i la nodul j(pot fi mai multe cai cele mai usoare)greutatea celei mai usoare cai
Reamintim ca matricea de ponderi a lui G este WG = (wij) unde
wij =
0 daca j = i ,w((i , j)) daca(i , j) ∈ E ,∞ daca (i , j) 6∈ E
Cursul 8
Cele mai usoare cai ıntr-un digraf simplu ponderatAlgoritmul lui Warshall: Idee de baza
Generalizare a ideii de calcul a celor mai mai scurte cai: Fiek ∈ V = {1, . . . , n}, si π : i j o cale cea mai usoara de la i la j .Distingem doua cazuri:
1 π nu trece prin nodul k
2 π trece prin k . Atunci π = iπ1 k
π2 j si w(π) = w(π1) + w(π2).
Structura de date auxiliara de calcul:
Matrice de cai usoare P [k] = (p[k]ij ) ın care fiecare
p[k]ij :=
• valoare speciala: @ cale i j prin noduri
intermediare din submultimea {1, . . . , k}π o cea mai usoara cale de la i la j prin noduri
intermediare din submultimea {1, . . . , k}
Cursul 8
Cele mai usoare cai ıntr-un digraf simplu ponderatAlgoritmul lui Warshall: Idee de baza
Generalizare a ideii de calcul a celor mai mai scurte cai: Fiek ∈ V = {1, . . . , n}, si π : i j o cale cea mai usoara de la i la j .Distingem doua cazuri:
1 π nu trece prin nodul k
2 π trece prin k . Atunci π = iπ1 k
π2 j si w(π) = w(π1) + w(π2).
Structura de date auxiliara de calcul:
Matrice de cai usoare P [k] = (p[k]ij ) ın care fiecare
p[k]ij :=
• valoare speciala: @ cale i j prin noduri
intermediare din submultimea {1, . . . , k}π o cea mai usoara cale de la i la j prin noduri
intermediare din submultimea {1, . . . , k}
Cursul 8
Cele mai usoare cai ıntr-un digraf simplu ponderatAlgoritmul lui Warshall: Notiuni auxiliare
Presupunem ca matricea de ponderi a lui G este WG = (wij).Pentru orice 0 ≤ k ≤ n se calculeaza recursiv, ıncepand de lak = 0, urmatoarele valori:
I p[k]ij : o cale cea mai usoara p : i j , ın care toate nodurile
intermediare sunt din multimea {1, 2, . . . , k}.I w
[k]ij : greutatea caii p
[k]ij
Observatii:
Daca nu exista o astfel de cale de la i al j , definim p[k]ij = • si
w[k]ij =∞.
w[0]ij := wij si
p[0]ij :=
[i ] daca i = j (ın acest caz, wij = wii = 0)[i , j ] daca i 6= j si wij <∞• daca wij =∞
Cursul 8
Cele mai usoare cai ıntr-un digraf simplu ponderatAlgoritmul lui Warshall: Formule de calcul recursiv
Pentru 0 < k ≤ n :
p[k]ij :=
{p
[k−1]ij daca w
[k−1]ij ≤ w
[k−1]ik + w
[k−1]kj
p[k−1]ik � p
[k−1]kj ın caz contrar
unde p[k−1]ik � p
[k−1]kj denota concatenarea cailor p
[k−1]ik si p
[k−1]kj .
w[k]ij :=
{w
[k−1]ij daca w
[k−1]ij ≤ w
[k−1]ik + w
[k−1]kj
w[k−1]ik + w
[k−1]kj ın caz contrar
Observatii
I Pentru orice 1 ≤ i , j ≤ n, daca p[n]ij 6= • atunci p
[n]ij este o cea
mai usoara cale de la i la j , iar w(p[n]ij ) = w
[n]ij .
I Calculul matricilor W [n] si P [n] se efectueaza ın O(n3).
Cursul 8
Cele mai scurte cai ıntr-un digraf simplu
Lungimea unei cai p = [x1, . . . , xn] este n − 1, adica numarulde arce ce la x1 la xn de-a lungul caii p.
Daca presupunem ca fiecare arc are greutatea 1, atuncilungimea unei cai coincide cu greutatea ei.
⇒ cele mai scurte cai dintre orice pereche de noduri pot ficalculate cu algoritmul lui Warshall (vezi slide-ul urmator.)
Cursul 8
Cele mai scurte cai ıntr-un digraf simpluAlgoritmul lui Warshall ilustrat
v5 v4
v3
v2
v1
11
11
11
PW[0]G =
[v1]0 • [v1, v3]1 • •
[v2, v1]1 [v2]0 • • •• • [v3]0 • [v3, v5]1
• • [v4, v3]1 [v4]0 •[v5, v1]1 • • [v5, v4]1 [v5]0
,
PW[1]G =
[v1]0 • [v1, v3]1 • •
[v2, v1]1 [v2]0 [v2, v1, v3]2 • •• • [v3]0 • [v3, v5]1
• • [v4, v3]1 [v4]0 •[v5, v1] • [v5, v1, v3]2 [v5, v4]1 [v5]0
,
PW[2]G = PW
[1]G , PW
[3]G =
[v1]0 • [v1, v3]1 • [v1, v3, v5]2
[v2, v1]1 [v2]0 [v2, v1, v3]2 • [v2, v1, v3, v5]3
• • [v3]0 • [v3, v5]1
• • [v4, v3]1 [v4]0 [v4, v3, v5]2
[v5, v1]1 • [v5, v1, v3]2 [v5, v4]1 [v5]0
, PW[4]G = PW
[3]G ,
PW[5]G =
[v1]0 • [v1, v3] [v1, v3, v5, v4]3 [v1, v3, v5]2
[v2, v1]1 [v2]0 [v2, v1, v3]2 [v2, v1, v3, v5, v4]4 [v2, v1, v3, v5]3
[v3, v5, v1]2 • [v3]0 • [v3, v5]1
[v4, v3, v5, v1]3 • [v4, v3]1 [v4]0 [v4, v3, v5]2
[v5, v1]1 • [v5, v1, v3]2 [v5, v4]1 [v5]0
Cursul 8
top related