cursul 8 - tipuri de grafuri. structuri de date pentru grafuri

28
Cursul 8 Tipuri de grafuri. Structuri de date pentru grafuri. Conectivitate: Algoritmul naiv ¸ si algoritmul lui Warshall noiembrie 2016 Cursul 8

Upload: lycong

Post on 28-Jan-2017

308 views

Category:

Documents


12 download

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