grafuri - concepte de baza. tipuri de grafuri. modalitati...

GrafuriConcepte de baza. Tipuri de grafuri. Modalitati de reprezentare

Mircea Marin

Departamentul of InformaticaUniversitatea de Vest din Timisoara

mircea.marin@e-uvt.ro

9 noiembrie 2018

Marin, M. Grafuri

IntroducereCe este un graf?

Graf: structura de date discreta formata din noduri si muchii delegatura ıntre noduri.

I Utila pentru modelarea unui numar mare de probleme:

legaturi rutiere sau feroviare ıntre localitatirelatii de subordonare ın o organizatierezultatul final al unui turneu. . .

I Notatie matematica G = (V ,E ) unde:

V : multime finita de noduriE : multime finita de muchii

I Probleme diferite pot fi modelate cu tipuri de grafuri diferite:grafuri simple, multigrafuri, pseudografuri, grafuri orientate,etc.

Marin, M. Grafuri

IntroducereCe este un graf?

Graf: structura de date discreta formata din noduri si muchii delegatura ıntre noduri.

I Utila pentru modelarea unui numar mare de probleme:

legaturi rutiere sau feroviare ıntre localitatirelatii de subordonare ın o organizatierezultatul final al unui turneu. . .

I Notatie matematica G = (V ,E ) unde:

V : multime finita de noduriE : multime finita de muchii

I Probleme diferite pot fi modelate cu tipuri de grafuri diferite:grafuri simple, multigrafuri, pseudografuri, grafuri orientate,etc.

Marin, M. Grafuri

IntroducereCe este un graf?

Graf: structura de date discreta formata din noduri si muchii delegatura ıntre noduri.

I Utila pentru modelarea unui numar mare de probleme:

legaturi rutiere sau feroviare ıntre localitatirelatii de subordonare ın o organizatierezultatul final al unui turneu. . .

I Notatie matematica G = (V ,E ) unde:

V : multime finita de noduriE : multime finita de muchii

I Probleme diferite pot fi modelate cu tipuri de grafuri diferite:grafuri simple, multigrafuri, pseudografuri, grafuri orientate,etc.

Marin, M. Grafuri

IntroducereCe este un graf?

Graf: structura de date discreta formata din noduri si muchii delegatura ıntre noduri.

I Utila pentru modelarea unui numar mare de probleme:

legaturi rutiere sau feroviare ıntre localitatirelatii de subordonare ın o organizatierezultatul final al unui turneu. . .

I Notatie matematica G = (V ,E ) unde:

V : multime finita de noduriE : multime finita de muchii

I Probleme diferite pot fi modelate cu tipuri de grafuri diferite:grafuri simple, multigrafuri, pseudografuri, grafuri orientate,etc.

Marin, M. Grafuri

Graf simpluExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Noduri V : locatiile geografice ale calculatoarelor: SanFrancisco (SF), Los Angeles (LA), Denver (Dn), Chicago (C),Detroit (Dt), New York (NY), Washington (W)

Muchii E : legaturile dintre calculatoare; presupunem ca1 Nu exista legaturi de la un nod la el ınsusi.2 Exista cel mult o legatura ıntre calculatoare diferite.

SF Dn

LA

C

Dt NY

W

V={SF,LA,Dn,C,Dt,NY,W}E = {{SF, LA}, {SF, Dn}, {LA, Dn}, {Dn, C},

{C, Dt}, {Dt, NY}, {C, NY}, {C, W}, {W, NY}}

Remarca: Muchiile unui graf simplu sunt specificate ca osubmultime a multimii {{x , y} | x , y ∈ V , x 6= y}.I muchiile sunt neorientate (ordinea nodurilor este irelevanta).

De exemplu: {C, NY} = {NY, C}

Marin, M. Grafuri

Graf simpluExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Noduri V : locatiile geografice ale calculatoarelor: SanFrancisco (SF), Los Angeles (LA), Denver (Dn), Chicago (C),Detroit (Dt), New York (NY), Washington (W)

Muchii E : legaturile dintre calculatoare; presupunem ca1 Nu exista legaturi de la un nod la el ınsusi.2 Exista cel mult o legatura ıntre calculatoare diferite.

SF Dn

LA

C

Dt NY

W

V={SF,LA,Dn,C,Dt,NY,W}E = {{SF, LA}, {SF, Dn}, {LA, Dn}, {Dn, C},

{C, Dt}, {Dt, NY}, {C, NY}, {C, W}, {W, NY}}

Remarca: Muchiile unui graf simplu sunt specificate ca osubmultime a multimii {{x , y} | x , y ∈ V , x 6= y}.I muchiile sunt neorientate (ordinea nodurilor este irelevanta).

De exemplu: {C, NY} = {NY, C}

Marin, M. Grafuri

Graf simpluExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Noduri V : locatiile geografice ale calculatoarelor: SanFrancisco (SF), Los Angeles (LA), Denver (Dn), Chicago (C),Detroit (Dt), New York (NY), Washington (W)

Muchii E : legaturile dintre calculatoare; presupunem ca1 Nu exista legaturi de la un nod la el ınsusi.2 Exista cel mult o legatura ıntre calculatoare diferite.

SF Dn

LA

C

Dt NY

W

V={SF,LA,Dn,C,Dt,NY,W}E = {{SF, LA}, {SF, Dn}, {LA, Dn}, {Dn, C},

{C, Dt}, {Dt, NY}, {C, NY}, {C, W}, {W, NY}}

Remarca: Muchiile unui graf simplu sunt specificate ca osubmultime a multimii {{x , y} | x , y ∈ V , x 6= y}.I muchiile sunt neorientate (ordinea nodurilor este irelevanta).

De exemplu: {C, NY} = {NY, C}Marin, M. Grafuri

MultigrafExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Pentru evitarea supraıncarcarii legaturilor telefonice, calculatoarediferite pot fi conectate cu mai multe linii telefonice:

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13}f : E → {{x , y} | x , y ∈ V , x 6= y},f returneaza capetele fiecarei muchii:

f (e1) = {SF, Dn}, f (e2) = {SF, LA},f (e3) = f (e4) = {LA, Dn}, f (e5) = f (e6) = f (e7) = {Dn, C},f (e8) = {C, Dt}, f (e9) = {Dt, NY}, . . .

Remarca: Un multigraf G este specificat de catre multimile V , Esi o functie f : E → {{x , y} | x , y ∈ V , x 6= y}.

e, e ′ ∈ E sunt paralele daca f (e) = f (e ′).

Marin, M. Grafuri

MultigrafExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Pentru evitarea supraıncarcarii legaturilor telefonice, calculatoarediferite pot fi conectate cu mai multe linii telefonice:

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13}f : E → {{x , y} | x , y ∈ V , x 6= y},f returneaza capetele fiecarei muchii:

f (e1) = {SF, Dn}, f (e2) = {SF, LA},f (e3) = f (e4) = {LA, Dn}, f (e5) = f (e6) = f (e7) = {Dn, C},f (e8) = {C, Dt}, f (e9) = {Dt, NY}, . . .

Remarca: Un multigraf G este specificat de catre multimile V , Esi o functie f : E → {{x , y} | x , y ∈ V , x 6= y}.

e, e ′ ∈ E sunt paralele daca f (e) = f (e ′).

Marin, M. Grafuri

MultigrafExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Pentru evitarea supraıncarcarii legaturilor telefonice, calculatoarediferite pot fi conectate cu mai multe linii telefonice:

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13}f : E → {{x , y} | x , y ∈ V , x 6= y},f returneaza capetele fiecarei muchii:

f (e1) = {SF, Dn}, f (e2) = {SF, LA},f (e3) = f (e4) = {LA, Dn}, f (e5) = f (e6) = f (e7) = {Dn, C},f (e8) = {C, Dt}, f (e9) = {Dt, NY}, . . .

Remarca: Un multigraf G este specificat de catre multimile V , Esi o functie f : E → {{x , y} | x , y ∈ V , x 6= y}.

e, e ′ ∈ E sunt paralele daca f (e) = f (e ′).

Marin, M. Grafuri

PseudografExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Putem considera si legaturi telefonice de la un calculator la elınsusi (de exemplu, pentru diagnosticare):

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13e14

e15

e16

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13, e14, e15, e16}f : E → {{x , y} | x , y ∈ V , x 6= y},f returneaza capetele fiecarei muchii:

f (e1) = {SF, Dn}, f (e2) = {SF, LA},f (e3) = f (e4) = {LA, Dn}, f (e5) = f (e6) = f (e7) = {Dn, C},f (e8) = {C, Dt}, f (e9) = {Dt, NY}, . . . , f (e16) = {NY}

Remarca: Un pseudograf G este specificat de catre multimile V ,E si o functie f : E → {{x , y} | x , y ∈ V }.

e ∈ E este o bucla daca f (e) = {x}, x ∈ V .Exemple: e14, e15, e16 sunt bucle.

Marin, M. Grafuri

PseudografExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Putem considera si legaturi telefonice de la un calculator la elınsusi (de exemplu, pentru diagnosticare):

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13e14

e15

e16

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13, e14, e15, e16}f : E → {{x , y} | x , y ∈ V , x 6= y},f returneaza capetele fiecarei muchii:

f (e1) = {SF, Dn}, f (e2) = {SF, LA},f (e3) = f (e4) = {LA, Dn}, f (e5) = f (e6) = f (e7) = {Dn, C},f (e8) = {C, Dt}, f (e9) = {Dt, NY}, . . . , f (e16) = {NY}

Remarca: Un pseudograf G este specificat de catre multimile V ,E si o functie f : E → {{x , y} | x , y ∈ V }.

e ∈ E este o bucla daca f (e) = {x}, x ∈ V .Exemple: e14, e15, e16 sunt bucle.

Marin, M. Grafuri

PseudografExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Putem considera si legaturi telefonice de la un calculator la elınsusi (de exemplu, pentru diagnosticare):

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13e14

e15

e16

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13, e14, e15, e16}f : E → {{x , y} | x , y ∈ V , x 6= y},f returneaza capetele fiecarei muchii:

f (e1) = {SF, Dn}, f (e2) = {SF, LA},f (e3) = f (e4) = {LA, Dn}, f (e5) = f (e6) = f (e7) = {Dn, C},f (e8) = {C, Dt}, f (e9) = {Dt, NY}, . . . , f (e16) = {NY}

Remarca: Un pseudograf G este specificat de catre multimile V ,E si o functie f : E → {{x , y} | x , y ∈ V }.

e ∈ E este o bucla daca f (e) = {x}, x ∈ V .Exemple: e14, e15, e16 sunt bucle.

Marin, M. Grafuri

Graf orientat (digraf)Exemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Muchiile sunt orientate de la un nod sursa la un nod destinatie

Exista cel mult o legatura de la un calculator la altul.

SF Dn

LA

C

Dt NY

W

V={SF,LA,Dn,C,Dt,NY,W}E = {(SF, SF), (Dn, SF), (Dn, LA), (LA, Dn), (LA, SF),

(Dn, C), (C, Dn), (C, Dt), (Dt, NY), (C, NY),

(C, W), (W, NY), (NY, W), (NY, NY)}

Observatii:

Muchiile unui digraf G = (V ,E ) sunt o submultimeE ⊆ (V × V ).

Daca u 6= v atunci (u, v) 6= (v , u).

Marin, M. Grafuri

Graf orientat (digraf)Exemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Muchiile sunt orientate de la un nod sursa la un nod destinatie

Exista cel mult o legatura de la un calculator la altul.

SF Dn

LA

C

Dt NY

W

V={SF,LA,Dn,C,Dt,NY,W}E = {(SF, SF), (Dn, SF), (Dn, LA), (LA, Dn), (LA, SF),

(Dn, C), (C, Dn), (C, Dt), (Dt, NY), (C, NY),

(C, W), (W, NY), (NY, W), (NY, NY)}

Observatii:

Muchiile unui digraf G = (V ,E ) sunt o submultimeE ⊆ (V × V ).

Daca u 6= v atunci (u, v) 6= (v , u).

Marin, M. Grafuri

Graf orientat (digraf)Exemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Muchiile sunt orientate de la un nod sursa la un nod destinatie

Exista cel mult o legatura de la un calculator la altul.

SF Dn

LA

C

Dt NY

W

V={SF,LA,Dn,C,Dt,NY,W}E = {(SF, SF), (Dn, SF), (Dn, LA), (LA, Dn), (LA, SF),

(Dn, C), (C, Dn), (C, Dt), (Dt, NY), (C, NY),

(C, W), (W, NY), (NY, W), (NY, NY)}

Observatii:

Muchiile unui digraf G = (V ,E ) sunt o submultimeE ⊆ (V × V ).

Daca u 6= v atunci (u, v) 6= (v , u).

Marin, M. Grafuri

Graf orientat (digraf)Exemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Muchiile sunt orientate de la un nod sursa la un nod destinatie

Exista cel mult o legatura de la un calculator la altul.

SF Dn

LA

C

Dt NY

W

V={SF,LA,Dn,C,Dt,NY,W}E = {(SF, SF), (Dn, SF), (Dn, LA), (LA, Dn), (LA, SF),

(Dn, C), (C, Dn), (C, Dt), (Dt, NY), (C, NY),

(C, W), (W, NY), (NY, W), (NY, NY)}

Observatii:

Muchiile unui digraf G = (V ,E ) sunt o submultimeE ⊆ (V × V ).

Daca u 6= v atunci (u, v) 6= (v , u).

Marin, M. Grafuri

Multigraf orientatExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Muchiile sunt orientate de la un nod sursa la un nod destinatie

Putem avea muchii multiple (paralele) de la o sursa la odestinatie.

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13e14

e15

e16

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13, e14, e15, e16}f : E → V × V ,

f returneaza sursa si destinatia fiecarei muchii:

f (e1) = (Dn, SF), f (e2) = (LA, SF), f (e3) = (LA, Dn),

f (e4) = (Dn, LA), f (e5) = f (e6) = (Dn, C), f (e7) = (C, Dn),

f (e8) = (C, Dt), . . . , f (e16) = (NY, NY)

Remarca: Un multigraf orientat G este specificat de catremultimile V , E si o functie f : E → V × V .

Marin, M. Grafuri

Multigraf orientatExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Muchiile sunt orientate de la un nod sursa la un nod destinatie

Putem avea muchii multiple (paralele) de la o sursa la odestinatie.

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13e14

e15

e16

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13, e14, e15, e16}f : E → V × V ,

f returneaza sursa si destinatia fiecarei muchii:

f (e1) = (Dn, SF), f (e2) = (LA, SF), f (e3) = (LA, Dn),

f (e4) = (Dn, LA), f (e5) = f (e6) = (Dn, C), f (e7) = (C, Dn),

f (e8) = (C, Dt), . . . , f (e16) = (NY, NY)

Remarca: Un multigraf orientat G este specificat de catremultimile V , E si o functie f : E → V × V .

Marin, M. Grafuri

Multigraf orientatExemplu: calculatoare din orase diferite conectate prin legaturi telefonice

Muchiile sunt orientate de la un nod sursa la un nod destinatie

Putem avea muchii multiple (paralele) de la o sursa la odestinatie.

SF Dn

LA

C

Dt NY

W

e1

e 3

e 4

e2

e 8

e9

e10

e11e6e5

e7

e 12

e 13e14

e15

e16

V={SF,LA,Dn,C,Dt,NY,W}E = {e1, e2, e3, . . . , e11, e12, e13, e14, e15, e16}f : E → V × V ,

f returneaza sursa si destinatia fiecarei muchii:

f (e1) = (Dn, SF), f (e2) = (LA, SF), f (e3) = (LA, Dn),

f (e4) = (Dn, LA), f (e5) = f (e6) = (Dn, C), f (e7) = (C, Dn),

f (e8) = (C, Dt), . . . , f (e16) = (NY, NY)

Remarca: Un multigraf orientat G este specificat de catremultimile V , E si o functie f : E → V × V .

Marin, M. Grafuri

Graf ponderatExemplu: retea de legaturi feroviare ıntre niste orase

Un graf G = (V ,E ) ımpreuna cu o functie w : E → Y careasociaza o greutate (sau pondere) w(e) fiecarei muchii e ∈ E .

I De obicei, ponderile sunt numere reale (A ⊆ R)

I In acest exemplu, ponderile sunt distantele ın kilometri dintreorase.

Marin, M. Grafuri

Tipuri de grafuriTerminologie

Tip muchii muchii multiple? Bucle?

Graf simplu neorientate nu nuMultigraf neorientate da nuPseudograf neorientate da daGraf orientat orientate nu daMultigraf orientat orientate da da

Marin, M. Grafuri

Modele bazate pe grafuri1. Graf de suprapunere de nisa:

Graf simplu ce modeleaza interactiunea dintre specii diferite deanimale:

fiecare specie este reprezentata de un nodmuchiile sunt ıntre specii ım competitie pentru resursecomune de mancare

raton

oposum

naparca

cioara

ciocanitoare

veverita

soimbufnita

soarece

Marin, M. Grafuri

Modele bazate pe grafuri2. Graf de turneu

Graf orientat (V ,E ) care modeleaza un campionat ın care fiecareechipa joaca o singura data cu fiecare din celelalte echipe:

Fiecare echipa este reprezentata ca nod ın graf

(a, b) ∈ E indica faptul ca echipa a a ınvins echipa b.

Exemplu: turneu de 6 echipe

Echipa 6 Echipa 3

Echipa 2

Echipa 4

Echipa 1

Echipa 5

Marin, M. Grafuri

Modele bazate pe grafuri3. Graf de precedenta

Graf orientat G = (V ,E ) care descrie relatiile de dependentadintre instructiunile unui program P:

Nodurile corespund instructiunilor din programul P

(s, s ′) ∈ E daca instructiunea s ′ nu poate fi executata ınainteainstructiunii s.

Exemplu:

Marin, M. Grafuri

Alte modele bazate pe grafuri

4. Arbore de familie al unei persoane X : graf orientat carereprezinta toti stramosii cunoscuti ai lui X :

Noduri: X si toti stramosii cunoscuti ai lui XMuchii: (a, b) reprezinta faptul ca b este copilul lui a.

Exemplu: arbore de familie al lui JFK:

John F. Kennedy

Joseph P. Kennedy

Rose F. Kennedy

Patrick J. Kennedy

Mary A. Hickey

John F. Fitzgerald

Mary J. Hannon

5. Graful web: WWW poate fi modelat ca un graf orientat

nodurile sunt paginile webo muchie de la A la B indica existenta unui hyperlink dinpagina A la pagina B.

Marin, M. Grafuri

Notiuni de bazaTerminologie pentru grafuri neorientate G = (V ,E) (1)

Nodurile u, v sunt incidente daca e = {u, v} ∈ E .Muchia e este incidenta cu nodul u si cu nodul v .Nodurile u, v sunt capetele muchiei e.u este vecinul lui v , si v este vecinul lui u.

Gradul deg(u) unui nod u este numarul de muchii incidente cuu; buclele contribuie de 2 ori la gradul unui nod.

u este izolat daca deg(u) = 0, si pendant daca deg(u) = 1.

Exemplu

a f e g

b c d a b c

e d

G H

In G : deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d) = 1, deg(e) =3, deg(g) = 0.

In H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.

Marin, M. Grafuri

Notiuni de bazaTerminologie pentru grafuri neorientate G = (V ,E) (1)

Nodurile u, v sunt incidente daca e = {u, v} ∈ E .Muchia e este incidenta cu nodul u si cu nodul v .Nodurile u, v sunt capetele muchiei e.u este vecinul lui v , si v este vecinul lui u.

Gradul deg(u) unui nod u este numarul de muchii incidente cuu; buclele contribuie de 2 ori la gradul unui nod.

u este izolat daca deg(u) = 0, si pendant daca deg(u) = 1.

Exemplu

a f e g

b c d a b c

e d

G H

In G : deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d) = 1, deg(e) =3, deg(g) = 0.

In H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateTerminologie pentru G = (V ,E) (2)

Ordinul lui G este |V |, numarul de noduri.Marimea lui G este |E |, numarul de muchii.Vecinatatea lui x ∈ V este N(x) := {y | y este vecin al lui x}Vecinatatea ınchisa a lui x este N[x ] := N(x) ∪ {x}Gradul minim al lui G este δ(G ) = min{deg(x) | x ∈ V }Gradul maxim al lui G este ∆(G ) = max{deg(x) | x ∈ V }

Exemplu

a

e

b

f

c

g h

d

G = (V ,E ) unde V = {a, b, c , d , e, f }, E = {{a, d}, {a, e},{b, c}, {b, e}, {b, g}, {c , f }, {d , f }, {d , g}, {g , h}}

N(d) = {a, f , g}, N[d ] = {a, d , f , g},∆(G ) = deg(b) = 3, δ(G ) = deg(h) = 1.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateTerminologie pentru G = (V ,E) (2)

Ordinul lui G este |V |, numarul de noduri.Marimea lui G este |E |, numarul de muchii.Vecinatatea lui x ∈ V este N(x) := {y | y este vecin al lui x}Vecinatatea ınchisa a lui x este N[x ] := N(x) ∪ {x}Gradul minim al lui G este δ(G ) = min{deg(x) | x ∈ V }Gradul maxim al lui G este ∆(G ) = max{deg(x) | x ∈ V }

Exemplu

a

e

b

f

c

g h

d

G = (V ,E ) unde V = {a, b, c , d , e, f }, E = {{a, d}, {a, e},{b, c}, {b, e}, {b, g}, {c , f }, {d , f }, {d , g}, {g , h}}

N(d) = {a, f , g}, N[d ] = {a, d , f , g},∆(G ) = deg(b) = 3, δ(G ) = deg(h) = 1.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateConectivitate (3)

Fie G = (V ,E ) un graf neorientat.

Un lant (sau cale) de la v1 la vn este o secventa de nodurid = (v1, v2, . . . , vn) astfel ıncat vi+1 este vecinul lui vi pentruorice 1 ≤ i < n.

I Lungimea lantului d este n − 1.I d este elementar daca nodurile v1, . . . , vn sunt distincte.I d este simplu daca nu contine de mai multe ori aceeasi muchie.I d este ciclu daca este lant simplu de lungime ≥ 3 si, v1 = vn.I Un ciclu d = (v1, . . . , vn, v1) este elementar daca nodurile

v1, . . . , vn sunt distincte.

v si v ′ sunt conectate daca exista un lant de la v la v ′.

G este conex daca orice 2 noduri sunt conectate.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateTerminologie pentru G = (V ,E) (4)

Exemplu

f

c b

g

d e

a • (f ) este lant de lungime 0.

• (a, c, f , c, b, d) este lant de lungime 5.

Acest lant nu este nici simplu nici elementar.

• (b, a, c, b, d , b) este ciclu de lungime 4.

Acest ciclu este simplu si ne-elementar.

• (d , g , b, a, c, f , e) este lant simplu si elementar de lungime 6.

• (g , d , b, c, a, b, g) este ciclu simplu dar ne-elementar.

• (e, d , b, a, c, f , e) este ciclu elementar.

Observatii:

1 Un lant sau ciclu elementar este simplu.

2 Teorema Fundamentala 1:∑

v∈V deg(v) = 2 · |E |.3 Teorema Fundamentala 2: Daca v si v ′ sunt conectate

atunci exista un lant elementar de la v la v ′.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateTerminologie pentru G = (V ,E) (4)

Exemplu

f

c b

g

d e

a • (f ) este lant de lungime 0.

• (a, c, f , c, b, d) este lant de lungime 5.

Acest lant nu este nici simplu nici elementar.

• (b, a, c, b, d , b) este ciclu de lungime 4.

Acest ciclu este simplu si ne-elementar.

• (d , g , b, a, c, f , e) este lant simplu si elementar de lungime 6.

• (g , d , b, c, a, b, g) este ciclu simplu dar ne-elementar.

• (e, d , b, a, c, f , e) este ciclu elementar.

Observatii:

1 Un lant sau ciclu elementar este simplu.

2 Teorema Fundamentala 1:∑

v∈V deg(v) = 2 · |E |.3 Teorema Fundamentala 2: Daca v si v ′ sunt conectate

atunci exista un lant elementar de la v la v ′.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateTerminologie pentru G = (V ,E) (4)

Exemplu

f

c b

g

d e

a • (f ) este lant de lungime 0.

• (a, c, f , c, b, d) este lant de lungime 5.

Acest lant nu este nici simplu nici elementar.

• (b, a, c, b, d , b) este ciclu de lungime 4.

Acest ciclu este simplu si ne-elementar.

• (d , g , b, a, c, f , e) este lant simplu si elementar de lungime 6.

• (g , d , b, c, a, b, g) este ciclu simplu dar ne-elementar.

• (e, d , b, a, c, f , e) este ciclu elementar.

Observatii:

1 Un lant sau ciclu elementar este simplu.

2 Teorema Fundamentala 1:∑

v∈V deg(v) = 2 · |E |.3 Teorema Fundamentala 2: Daca v si v ′ sunt conectate

atunci exista un lant elementar de la v la v ′.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateTerminologie pentru G = (V ,E) (4)

Exemplu

f

c b

g

d e

a • (f ) este lant de lungime 0.

• (a, c, f , c, b, d) este lant de lungime 5.

Acest lant nu este nici simplu nici elementar.

• (b, a, c, b, d , b) este ciclu de lungime 4.

Acest ciclu este simplu si ne-elementar.

• (d , g , b, a, c, f , e) este lant simplu si elementar de lungime 6.

• (g , d , b, c, a, b, g) este ciclu simplu dar ne-elementar.

• (e, d , b, a, c, f , e) este ciclu elementar.

Observatii:

1 Un lant sau ciclu elementar este simplu.

2 Teorema Fundamentala 1:∑

v∈V deg(v) = 2 · |E |.

3 Teorema Fundamentala 2: Daca v si v ′ sunt conectateatunci exista un lant elementar de la v la v ′.

Marin, M. Grafuri

Notiuni de baza pentru grafuri neorientateTerminologie pentru G = (V ,E) (4)

Exemplu

f

c b

g

d e

a • (f ) este lant de lungime 0.

• (a, c, f , c, b, d) este lant de lungime 5.

Acest lant nu este nici simplu nici elementar.

• (b, a, c, b, d , b) este ciclu de lungime 4.

Acest ciclu este simplu si ne-elementar.

• (d , g , b, a, c, f , e) este lant simplu si elementar de lungime 6.

• (g , d , b, c, a, b, g) este ciclu simplu dar ne-elementar.

• (e, d , b, a, c, f , e) este ciclu elementar.

Observatii:

1 Un lant sau ciclu elementar este simplu.

2 Teorema Fundamentala 1:∑

v∈V deg(v) = 2 · |E |.3 Teorema Fundamentala 2: Daca v si v ′ sunt conectate

atunci exista un lant elementar de la v la v ′.

Marin, M. Grafuri

Tipuri speciale de grafuri simple (1)Kn,Cn,En

Grafurile complete Kn

K1 K2K3 K4 K5 K6

Grafurile cale Pn sunt lanturile elementare de n noduri

v1 v2 v3 vn

Grafurile vide En au n noduri, si nu au nici o muchie.

v1 v2 v3 . . . vn

Grafurile ciclice Cn constau din cicluri de lungime n

C3 C4

Marin, M. Grafuri

Tipuri speciale de grafuri simple (2)Grafuri bipartite

G = (V ,E ) este bipartit daca

I V = X ∪ Y unde X 6= ∅ 6= Y si X ∩ Y = ∅I Toate muchiile au un capat ın X si celalalt ın Y .

Exemplu de graf bipartit :

X YUn graf bipartit complet Km,n este un graf bipartit ıntre X si Y cu|X | = m, |Y | = n, astfel ıncat exista o muchie ıntre orice perechede noduri (x , y) ∈ X × Y .

Marin, M. Grafuri

Grafuri bipartite

Exemple de grafuri bipartite complete

K1,4 K3,4 K3,2

Observatii: Alte definitii echivalente pentru ca G sa fie bipartit:

I putem colora nodurile cu 2 culori astfel ıncat orice 2 noduriınvecinate sa aibe culori diferite.

I nu contine cicluri de lungime impara.

Exemple de grafuri bipartite

12

34

5

6=

1

3

5

2

4

6

K3,3

Dan

Ion

Nae

Leo

Ana

Lia

Zoe

Mia

relatii deprietenie

12

34

5

6

C6

=

1

3

5

2

4

6

Marin, M. Grafuri

Notiuni de baza pentru grafuri orientateTerminologie pentru G = (V ,E) (1)

Muchiile lui G se numesc arce. Scriem (u, v) ∈ E daca Econtine un arc cu sursa u si destinatia v .u, v sunt adiacente daca (u, v) ∈ E .Gradul interior al unui nod v estedeg−(v) = |{e ∈ E | e are destinatia v}|.Gradul exterior al unui nod v estedeg+(v) = |{e ∈ E | e are sursa v}|.

Exemplu

a

e

b c

d

f

Nod x deg−(x) deg+(x)a 0 2b 3 1c 1 3d 1 1e 2 2f 2 0

Observatie:∑v∈V

deg−(v) =∑v∈V

deg+(v).

Marin, M. Grafuri

Notiuni de baza pentru grafuri orientateTerminologie pentru G = (V ,E) (1)

Muchiile lui G se numesc arce. Scriem (u, v) ∈ E daca Econtine un arc cu sursa u si destinatia v .u, v sunt adiacente daca (u, v) ∈ E .Gradul interior al unui nod v estedeg−(v) = |{e ∈ E | e are destinatia v}|.Gradul exterior al unui nod v estedeg+(v) = |{e ∈ E | e are sursa v}|.

Exemplu

a

e

b c

d

f

Nod x deg−(x) deg+(x)a 0 2b 3 1c 1 3d 1 1e 2 2f 2 0

Observatie:∑v∈V

deg−(v) =∑v∈V

deg+(v).

Marin, M. Grafuri

Notiuni de baza pentru grafuri orientateConectivitate: Drumuri si circuite (2)

Un drum de la v1 la vn este o secventa de nodurid = (v1, v2, . . . , vn) astfel ıncat (vi , vi−1) ∈ E pentru orice1 ≤ i < n.

I Lungimea drumului d este n − 1.

I d este simplu daca arcele (v1, v2), . . . , (vn−1, vn) sunt distinctedoua cate doua.

I d este elementar daca nodurile v1, . . . , vn sunt distincte.

Observatie: orice drum elementar este simplu.

Un circuit este un drum simplu d = (v1, v2, . . . , vn) cu v1 = vn.

I Circuitul d = (v1, . . . , vn, v1) este elementar daca nodurilev1, . . . , vn sunt distincte.

Marin, M. Grafuri

Grafuri izomorfe

a b

hge f

dc

67

81 2

54

3

Daca putem redenumi si repozitiona nodurile primului graf, cele 2grafuri devin identice.

Grafuri izomorfe

G = (V1,E1) si H = (V2,E2) sunt izomorfe daca exista o functiebijectiva f : V1 → V2 astfel ıncat

{x , y} ∈ E1 daca si numai daca {f (x), f (y)} ∈ E2, sau

(x , y) ∈ E1 daca si numai daca (f (x), f (y)) ∈ E2.

Remarca: Cand 2 grafuri G si H sunt izomorfe, se obisnuieste sa sespuna ca “G este H” si sa se scrie “G = H”.

Marin, M. Grafuri

Grafuri izomorfe

a b

hge f

dc

67

81 2

54

3

Daca putem redenumi si repozitiona nodurile primului graf, cele 2grafuri devin identice.

Grafuri izomorfe

G = (V1,E1) si H = (V2,E2) sunt izomorfe daca exista o functiebijectiva f : V1 → V2 astfel ıncat

{x , y} ∈ E1 daca si numai daca {f (x), f (y)} ∈ E2, sau

(x , y) ∈ E1 daca si numai daca (f (x), f (y)) ∈ E2.

Remarca: Cand 2 grafuri G si H sunt izomorfe, se obisnuieste sa sespuna ca “G este H” si sa se scrie “G = H”.

Marin, M. Grafuri

Grafuri izomorfe

a b

hge f

dc

67

81 2

54

3

Daca putem redenumi si repozitiona nodurile primului graf, cele 2grafuri devin identice.

Grafuri izomorfe

G = (V1,E1) si H = (V2,E2) sunt izomorfe daca exista o functiebijectiva f : V1 → V2 astfel ıncat

{x , y} ∈ E1 daca si numai daca {f (x), f (y)} ∈ E2, sau

(x , y) ∈ E1 daca si numai daca (f (x), f (y)) ∈ E2.

Remarca: Cand 2 grafuri G si H sunt izomorfe, se obisnuieste sa sespuna ca “G este H” si sa se scrie “G = H”.

Marin, M. Grafuri

Grafuri izomorfe

a b

hge f

dc

67

81 2

54

3

Daca putem redenumi si repozitiona nodurile primului graf, cele 2grafuri devin identice.

Grafuri izomorfe

G = (V1,E1) si H = (V2,E2) sunt izomorfe daca exista o functiebijectiva f : V1 → V2 astfel ıncat

{x , y} ∈ E1 daca si numai daca {f (x), f (y)} ∈ E2, sau

(x , y) ∈ E1 daca si numai daca (f (x), f (y)) ∈ E2.

Remarca: Cand 2 grafuri G si H sunt izomorfe, se obisnuieste sa sespuna ca “G este H” si sa se scrie “G = H”.

Marin, M. Grafuri

Modalitati de reprezentare a grafurilor

1 Lista de noduri + lista de muchii

2 Liste de adiacenta

3 Matrice de adiacenta

4 Matrice de incidenta

5 Matrice de ponderi

Marin, M. Grafuri

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

Marin, M. Grafuri

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 ]

Marin, M. Grafuri

Matrice de adiacenta

Presupunem ca G = (V ,E ) este un graf cu |V | = n noduri.Matricea de adiacenta a lui G este AG = (mij) de dimensiunen × n si

mij := numarul de muchii de la al i-lea nod la al j-lea nod.

Observatii

1 Inainte de a construi AG din G , trebuie sa fixam o enumerarea tuturor 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

Marin, M. Grafuri

Matrici de adiacenta pentru grafuri neorientateVizualizarea unui graf neorientat reprezentat de AG

Daca A este o matrice simetrica n × n cu aij ∈ N pentru toti i , j ,un graf neorientat G care are matricea de adiacenta A seconstruieste astfel:

1 Se deseneaza n noduri 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

Marin, M. Grafuri

Matrici de adiacenta pentru grafuri orientate

Graful G :a

b c

d

e are matricea de adiacenta

AG =

0 1 0 0 00 0 0 0 01 1 0 0 01 0 0 0 00 0 1 1 0

pentru enumerarea nodurilor [a, b, c , d , e].

Marin, M. Grafuri

Reprezentarea digrafurilor ponderateMatrici de ponderi

Matricea de ponderi WG = (wij) a unui graf simplu ponderat, saudigraf ponderat G cu n 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.

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

Marin, M. Grafuri

Reprezentarea digrafurilor ponderateMatrici de ponderi

Matricea de ponderi WG = (wij) a unui graf simplu ponderat, saudigraf ponderat G cu n 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.

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

Marin, M. Grafuri

Modalitati de reprezentare a 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 |)

Marin, M. Grafuri

Operatii pe grafuri

Presupunem ca G = (V ,E ) este un graf neorientat, v ∈ V , S ⊆ V ,e ∈ E , T ⊆ E

Stergere de noduri:

G − v este graful care se obtine eliminand din G nodul v sitoate muchiile incidente la v .G − S este graful care se obtine eliminand din G nodurile dinS si toate muchiile incidente la un nod din S .Un subgraf al lui G este orice graf G − S .

Stergere de muchii

G − e este graful care se obtine eliminand din G muchia e.Capetele lui e nu se elimina.G − T este graful care se obtine eliminand din G toatemuchiile din T .

Marin, M. Grafuri

Grafuri partiale si subgrafuri

Fie G ′ = (V ,E ′) si G ′ = (V ′,E ′).

G ′ este un graf partial al lui G daca V ′ ⊆ V si G ′ se obtinedin G prin stergeri succesive de noduri si muchii.

G ′ este un subgraf al lui G daca V ′ ⊆ V si G ′ se obtinestergand din G nodurile din V − V ′.

I G ′ este o componenta a lui G daca este un subgraf maximalcare este conex.

I G ′ este o clica a lui G daca (1) G ′ este subgraf al lui G si(2) G ′ este (izomorf cu) un graf complet Kn, n ≥ 2.

v este un nod de taiere al lui G daca G − v are mai multecomponente decat G .

e este o punte a lui G daca G − e are mai multe componentedecat G .

S este o multime de taiere a unui graf conex G daca

I ∅ 6= S ( V , siI G − S nu este conex.

Marin, M. Grafuri

Grafuri neorientateComponente conexe

Exemple

1 G1 : este conex.a

b

c

d

e

2 G2 : nu este conex. G2 are 3 componente:a

b

c

d

e

fg

G2 − {e, f , g}, G2 − {a, b, c , d , e}, si G3 = G2 − {a, b, c , d , f , g}.

3 G3 : nu este conex. G3 are 2 componente:a

bc

d

e f

G3 − {b, d , f } si G3 − {a, c , e}.

Marin, M. Grafuri

Operatii pe grafuriExemplu: stergere de noduri si muchii

a

b c

e f

g

G−d

a

b c

d

e f

g

G

a

b c

d

e f

g

G−{{c, d}}

a

b c

d

e f

g

G − {{e, g}, {f , g}}

I d este nod de taiere ın G .

I {a, b} este punte ın G .

Marin, M. Grafuri

Operatii pe grafuriExemplu: stergere de noduri si muchii

a

b c

e f

g

G−d

a

b c

d

e f

g

G

a

b c

d

e f

g

G−{{c, d}}

a

b c

d

e f

g

G − {{e, g}, {f , g}}

I d este nod de taiere ın G .

I {a, b} este punte ın G .

Marin, M. Grafuri

Operatii pe grafuriExemplu: stergere de noduri si muchii

a

b c

e f

g

G−d

a

b c

d

e f

g

G

a

b c

d

e f

g

G−{{c, d}}

a

b c

d

e f

g

G − {{e, g}, {f , g}}

I d este nod de taiere ın G .

I {a, b} este punte ın G .

Marin, M. Grafuri

Grafuri partiale si subgrafuri

Fie G , G ′ doua grafuri.

Spunem ca G este liber de G ′, sau G ′-liber, daca G ′ nu estesubgraf al lui G .

Quiz

Se considera grafurile

K1,3 Z1 N

Care din grafurile urmatoare sunt K1,3-libere? Care sunt Z1-libere?Care sunt N-libere?

Marin, M. Grafuri