Algoritmica grafurilor I. Introduceremihai-suciu/graf/curs01.pdf · · 2018-03-06Algoritmica...

Algoritmica grafurilorI. Introducere

Mihai SuciuFacultatea de Matematica și Informatica (UBB)

Departamentul de Informatica

Februarie, 28, 2018

Mihai Suciu (UBB) Algoritmica grafurilor Februarie, 28, 2018 1 / 48

Continut

1 OrganizarePrezentarea cursului

2 Introducere3 Definitii

Multigraf neorientatGraf simpluMultigraf orientatMultigraf ponderatDrumuriGraf conex

4 Reprezentari ale grafurilor5 Matricea distantelor


Organizare Prezentarea cursului

De ce?

Obiective:Obţinerea unei imagini de ansamblu, cunoașterea și inţelegereanoţiunilor, modelelor generale de probleme și algoritmilor de rezolvarea acestoraCunoașterea conceptelor teoretice ale algoritmicii grafurilor șiaplicarea acestora în modelarea și rezolvarea problemelorAnalizarea unui gaf și a problemelor ce ţin de grafuri: conectivitate,cel mai scurt drum, drum minim, flux de date, problemacomis-voiajorului, etc.Cunoașterea implementarii algoritmilor într-un limbaj de programare



Conţinut curs

1 Noţiuni de baza2 Studiu aprofundat al reprezentarii grafurilor. Drumuri

în grafuri.3 Algoritmul lui Bellman-Kalaba, algoritmul lui Ford,

algoritmi matriceali, drum ciclic, drumuri Euleriene,drumuri Hamiltoniene.

4 Conectivitate și probleme de lanţ minim. Parcurgeride graf în laţime și adâncime.

5 Numere fundamentale în teoria grafurilor.6 Arbori și paduri



Conţinut curs (II)

7 Cuplaje în grafuri8 Probleme extremale9 Probleme grele: ciclu Hamiltonian, problema

comis-voiajorului. Probleme de numarare și enumerare.10 Probleme grele: clique, vertex cover, colorare11 Ciclu elementar Eulerian. Grafuri planare.12 Reţele de transport.13 Fluxuri în reţele de transport.14 Probleme de cuplaj.



Bibliografie

Berge C., Graphes et hypergraphes, Dunod, Paris 1970.Berge C., Teoria grafurilor și aplicaţiile ei, Ed. Tehnica, 1972T. Toadere, Grafe. Teorie, algoritmi și aplicaţii, Ed. Albastra, Cluj-N (ed. I, II, III),2002 și 2009KÁSA ZOLTÁN, Combinatorica cu aplicaţii, Presa Universitara Clujeana, 2003.Cormen, Leiserson, Rivest, Introducere în algoritmi, Editura Computer LibrisAgora, 2000.Rosu A., Teoria grafelor, algoritmi, aplicaţii. Ed. Militara, 1974.Ciurea E., Ciupala L., Algoritmi - algoritmii fluxurilor în reţele, Ed. Matrix Rom,2006.CATARANCIUC S., IACOB M.E., TOADERE T., Probleme de teoria grafelor,Lito. Univ. Cluj-Napoca, 1994.

KÁSA Z., TARTIA C., TAMBULEA L.: Culegere de probleme de teoria grafelor,Lito. Univ. Cluj-Napoca 1979.



Bibliografie (II)

TOMESCU I., Probleme de combinatorica si teoria grafurilor. Ed. Did. si Pedag.Bucuresti 1981.Easley David and Kleinberg Jon. 2010. Networks, Crowds, and Markets:Reasoning about a Highly Connected World. Cambridge University Press, NewYork, NY, USA.Mark Newman. 2010. Networks: An Introduction. Oxford University Press, Inc.,New York, NY, USAMatthew O. Jackson. 2008. Social and Economic Networks. Princeton UniversityPress, Princeton, NJ, USA.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.2009. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.

Geir Agnarsson and Raymond Greenlaw. 2006. Graph Theory: Modeling,Applications, and Algorithms. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.



Organizare

curs, seminar, laborator: Mihai Suciu (mihai-suciu [at] cs.ubbcluj.ro)(www.cs.ubbcluj.ro/˜mihai-suciu)laborator:

Asist. drd. COROIU Adriana(http://www.cs.ubbcluj.ro/˜adrianac/)C.d.asociat dr. APATEAN Anca

Pagina web a cursuluiwww.cs.ubbcluj.ro/˜mihai-suciu/graf/


www.cs.ubbcluj.ro/~mihai-suciu

http://www.cs.ubbcluj.ro/~adrianac/

www.cs.ubbcluj.ro/~mihai-suciu/graf/


Structura

Curs: 2 ore / saptamâna

Seminar: 1 ora / saptamâna

Laborator: 1 ora / saptamâna

Orar:http://www.cs.ubbcluj.ro/files/orar/2017-2/disc/MLR5025.html


http://www.cs.ubbcluj.ro/files/orar/2017-2/disc/MLR5025.html


Evaluare şi cerinţe

Colocviu (C) - examen scris

Activitate Laborator (L) - activitate la laborator (3 teste susţinute peparcursul semestrului)Puncte bonus la laborator (B) 1p (0.25p / laborator)

nota finala:

0.67 ∗ C + 0.33 ∗ L + B = 11p

colocviu - nota trebuie sa fie minim 5!!laborator - media testelor trebuie sa fie minim 5!!



Evaluare şi cerinţe (II)

Activitatea de seminar este OBLIGATORIE în proporţie de minim75% −→ maxim 2 absenţeActivitatea de laborator este OBLIGATORIE în proporţie de minim90% −→ maxim 1 absenţe.problemele primite la laborator trebuie rezolvate în C/C++ (ca șiIDE se recomanda Qt - https://www.qt.io/download)Este necesara participarea studenţilor la ambele ore de seminar /laborator pentru a fi luata în considerare prezenţa.Studenţii cu mai mult de 2 absente nemotivate la seminar saulaborator nu vor fi primiţi la examenul din sesiunea normala și nici laexamenul din sesiunea de restanţe (acești studenţi vor trebui sa repeteacest curs în anul universitar urmator). Sunt exceptaţi de la aceastacerinţa cei scutiţi medical care pot dovedi cu acte fiecare absenţa înparte.Mihai Suciu (UBB) Algoritmica grafurilor Februarie, 28, 2018 11 / 48

https://www.qt.io/download

Introducere

Partea II


Introducere

Inceputuri


Introducere

Soluţie

Leonhard Euler (1707-1783)


Introducere

Podurile din Königsberg


Introducere

Podurile din Königsberg (II)


Introducere

Unde suntem acum?


Introducere

Unde suntem acum? (II)


Introducere

Unde suntem acum? (III)


Introducere

Unde suntem acum? (IV)


Definitii Multigraf neorientat

Definiţii

Multigraf neorientatse numește multigraf orice sistem de forma G = (V ,E , g) undeV - mulţimea vârfurilor, V 6= ∅E - mulţimea muchiilor, V ∩ E = ∅g : E → V

⊗V

Se mai poate scrieG = (V (G),E (G), g(G))

Observaţii:1 daca mulţimile V și E sunt finite ⇒ multigraful G este finit2 AxB = {(a, b)|a ∈ A, b ∈ B} - pereche ordonata de elemente3 A

⊗B = {(a, b)|a ∈ A, b ∈ B sau a ∈ B, b ∈ A} - pereche neordonata



Multigraf (n,m)

n = |V | - ordinul multigrafului G

m = |E | - dimensiunea multigrafului G

daca extremitaţile unei muchii coincid, muchia se numește bucla

g(e) = {a, a}

dacag(e1) = g(e2)

atunci muchiile e1 și e2 sunt paralele



Muchii adiacente

setul muchiilor ce leaga vârfurile a și b este

g−1(a, b) = {e ∈ E (G)|g(e) = {a, b}}

Muchii adiacentefie x un vârf din G . NG(x) sau N(X ) este setul muchiilor adiacente lui x:

NG(x) = {y ∈ V (G),∃e ∈ E (G), g(e) = {x , y}}

sauNG(X ) = {y ∈ V (G), g−1(x , y) 6= ∅}



Muchii incidente

Muchii incidenteintr-un multigraf G, setul muchiilor incidente lui x (care nu sunt bucle)este:

IG(x) = {e ∈ E (G),∃y ∈ V (G), y 6= x , g(e) = {x , y}}

Bucle incidentesetul buclelor incidente nodului x este:

LG(x) = {e ∈ E (G), g(e) = {x , x}}



Gradul unui vârf

Gradul unui vârfgradul unui vârf, notat d(x), este numarul muchiilor incidente lui x :

d(x) = card(IG(x)) + 2 ∗ card(LG(x)).

Daca:d(x) = 0, x este un vârf izolatd(x) = 1, x este vârful unei muchii


Definitii Graf simplu

Graf simplu

Graf simpluun multigraf fara bucle și muchii paralele se numește graf simplu. În acestcaz

|g−1(a, b)| ≤ 1,∀a, b ∈ V .

Se poate scrie {a, b} în loc de g(e) = {a, b}.Graful se noteaza G = (V ,E ).

Observaţii:pentru un graf simplu gradul unui nod este:

d(x) = |NG(x)|



Definiţii

graf regulargraf în care toate vârfurile au același grad.Graf k-regular, toate vârfurile au gradul k

d(x) = k, ∀x ∈ V (G).

Graf completun graf pentru care toate perechile de vârfuri sunt adiacente se numeștegraf complet. Un graf complet de ordinul n se noteaza Kn.

Exemple



Definiţii (II)

graful G ′ = (V ′,E ′) este complementul grafului G = (V ,E ), daca V ′ = Vși E ′ = {{a, b}, {a, b} 6∈ E}.

daca G este un graf de ordinul n atunci E (G) ∪ E (G ′) = E (Kn).



Izomorfism

Izomorfism multigrafmultigrafurile G1 și G2 sunt izomorfe daca exista bijecţiile f : V1 → V2 șig : N→ N astfel ca:

(i , j , k) ∈ E1 ⇔ (f (i), f (j), g(k)) ∈ E2.

Izomorfism graf simpludoua grafuri G1 și G2 sunt izomorfe daca exista funcţia bijectivaf : V1 → V2 astfel ca:

(a, b) ∈ E1 ⇔ (f (a), f (b)) ∈ E2.



Izomorfism (II)

Exemplu izomorfism

Teoremărelaţia de izomorfism în mulţimea grafurilor este o relaţie de echivalenţa.



Exemple de grafuri

graf nulgraf liniegraf ciclugraf completgraf bipartit complet



hand-shakingpentru un graf G avem ∑

u∈V (G)dG(u) = 2|E (G)|.

corolarîntr-un graf exista întotdeauna un numar par de vârfuri ce au grad impar

corolarfiecare graf k-regular pe n vârfuri are kn

2 muchii, în particular Kn aren(n−1)

2 muchii.



Subgraf

Definiţiepentru multigraful G1 = (V1,E1, g1) și G = (V ,E , g) spunem ca G1 estesubgraf al lui G dacaV1 ⊆ VE1 ⊆ Eg1(e) = g(e)∀e ∈ E1se noteaza G1 ⊆ G


Definitii Multigraf orientat

Multigraf, graf orientat

Multigraf orientat

se numește multigraf orientat orice sistem de forma ~G = (V ,E , η) undeV este mulţimea vârfurilor, V 6= ∅E este mulţimea arcelor, V ∩ E = ∅η : E → VxV

η(e) = {u, v} arcul este incident spre exterior vârfului u, arcul esteincident spre interior vârfului vη(e) = {u, u} - arc buclaη(e1) = η(e2) - arce paraleleun graf orientat simplu se definește în mod similar unui grafneorientat



Subgrad interior, exterior

Definiţiefie multigraful G = (V ,E , η) și vârful x ∈ V

se numește subgradul interior, se noteaza d−(x), numarul arcelorincidente spre interior vârfului x :

d−(x) = |{e ∈ E |η(e) = {y , x},∀y ∈ V }| = |N in~G (x)|

se numește subgradul exterior, notat d+, numarul arcelor incidentespre exterir nodului x :

d+(x) = |{e ∈ E |η(e) = {x , y},∀y ∈ V }| = |Nout~G (x)|

d(x) = d−(x) + d+(x)



Subgrad interior, exterior (II)

Teoremăpentru un multigraf orientat avem:∑

x∈V (~G)

d−(x) =∑

x∈V (~G)

d+(x) = |E (~G)|


Definitii Multigraf ponderat

Multigraf ponderat

Multigraf ponderatse numește multigraf ponderat orice sistem de forma G = (V ,E , g ,W )V - mulţimea vârfurilor, V 6= ∅E - mulţimea muchiilor, V ∩ E = ∅g : E → V

⊗V

W : E → R - ponderea muchiilor

Multigraf ponderat orientatse numește multigraf ponderat orientat orice sistem de forma~G = (V ,E , η,W ) undeV este mulţimea vârfurilor, V 6= ∅E este mulţimea arcelor, V ∩ E = ∅η : E → V x VW : E → R - ponderea arcelor


Definitii Drumuri

Drumuri în grafuri

Drumfiind dat un graf orientat G = (V ,E ), prin drum în graful G înţelegem osuccesiune de arce cu proprietatea ca extremitatea terminala a unui arc aldrumului coincide cu extremitatea iniţiala a arcului urmator din drum.

drum = o succesiune de vârfuri care sunt extremitaţi ale arcelor cecompun drumulun drum µ este {e1, e2, ..., eq} fie {i0, i1, ..., iq} cu proprietatea caej = (ij−1, ij) ∈ E pentru j = 1, 2, ..., q


Definitii Drumuri

Drumuri în grafuri (II)

Lungimea unui drumlungimea unui drum este numarul arcelor care compun drumul respectiv.

Un drum într-un graf este:simplu daca nu folosește de doua ori un același arccompus daca nu este simpluelementar daca nu contine (trece) de doua ori un același vârfcircuit daca extremitatea iniţiala a drumului coincide cu cea finalaeulerian daca este simplu și trece prin toate arcele grafuluihamiltonian daca este elementar și trece prin toate vârfurile grafului


Definitii Drumuri

Drumuri în grafuri neorientate

corespunzator noţiunilor de drum si circuit în grafurile neorientatesunt noţiunile de lanţ și ciclu

Lanţun lanţ este o succesiune de muchii cu proprietatea ca oricare muchie areo extremitate comuna cu muchia precedenta și cealalta extremitate estecomuna cu muchia urmatoare.

Cicludaca extremitaţile lanţului coincid, atunci lanţul se numește ciclu.


Definitii Drumuri

Exemplu

Lanţ:

1a2c4d3b2c4Lanţ simplu: 2b3d4c2Lanţ elementar: 1a2b3Ciclu simplu: 2b3d4c2


Definitii Drumuri

Exemplu

Lanţ: 1a2c4d3b2c4

Lanţ simplu: 2b3d4c2Lanţ elementar: 1a2b3Ciclu simplu: 2b3d4c2


Definitii Drumuri

Exemplu

Lanţ: 1a2c4d3b2c4Lanţ simplu:

2b3d4c2Lanţ elementar: 1a2b3Ciclu simplu: 2b3d4c2


Definitii Drumuri

Exemplu

Lanţ: 1a2c4d3b2c4Lanţ simplu: 2b3d4c2

Lanţ elementar: 1a2b3Ciclu simplu: 2b3d4c2


Definitii Drumuri

Exemplu

Lanţ: 1a2c4d3b2c4Lanţ simplu: 2b3d4c2Lanţ elementar:

1a2b3Ciclu simplu: 2b3d4c2


Definitii Drumuri

Exemplu

Lanţ: 1a2c4d3b2c4Lanţ simplu: 2b3d4c2Lanţ elementar: 1a2b3

Ciclu simplu: 2b3d4c2


Definitii Drumuri

Exemplu

Lanţ: 1a2c4d3b2c4Lanţ simplu: 2b3d4c2Lanţ elementar: 1a2b3Ciclu simplu:

2b3d4c2


Definitii Drumuri

Exemplu

Lanţ: 1a2c4d3b2c4Lanţ simplu: 2b3d4c2Lanţ elementar: 1a2b3Ciclu simplu: 2b3d4c2


Definitii Graf conex

Graf tare conex, conex

Graf tare conexun graf orientat este tare conex daca între oricare doua vârfuri ale grafuluiexista un drum.

graf tare conex - prin oricare doua vârfuri trece ce puţin un circuit

Graf conexun graf neorientat este conex daca între oricare doua vârfuri ale grafuluiexista un lanţ.


Reprezentari ale grafurilor

Reprezentarea matriceală

Pentru exemplele date grafurile au fost reprezentate grafic, pentru un programscris aceasta reprezentare nu este suficienta.Un graf poate fi reprezentat folosind:

matricea de adiacenţaA = (aij), i , j = 1, 2, ..., n unde

aij ={

1, (i , j) ∈ E0, (i , j) /∈ E

matricea de incidenţa - se atașeaza grafurilor simple a caror mulţime dearce s-a ordonat, linia i corespunde vârfului i iar coloana j corespunde arcului e,matricea este de tipul nxm. Elementele matricii:

bij =

{ 1, ∃j ∈ V |e = (i , j),−1, ∃j ∈ V |e = (j, i), i ∈ V , e ∈ E0, altfel

lista


Reprezentari ale grafurilor

Reprezentarea matriceală

Pentru exemplele date grafurile au fost reprezentate grafic, pentru un programscris aceasta reprezentare nu este suficienta.Un graf poate fi reprezentat folosind:

matricea de adiacenţaA = (aij), i , j = 1, 2, ..., n unde

aij ={

1, (i , j) ∈ E0, (i , j) /∈ E

matricea de incidenţa - se atașeaza grafurilor simple a caror mulţime dearce s-a ordonat, linia i corespunde vârfului i iar coloana j corespunde arcului e,matricea este de tipul nxm. Elementele matricii:

bij =

{ 1, ∃j ∈ V |e = (i , j),−1, ∃j ∈ V |e = (j, i), i ∈ V , e ∈ E0, altfel

listaMihai Suciu (UBB) Algoritmica grafurilor Februarie, 28, 2018 43 / 48

Matricea distantelor

Determinarea matricei distanţelor

algoritmul Warshall

Warshall(D0)1. D := D02. for k := 1 to n do3. for i := 1 to n do4. for j := 1 to n do5. dij := min(dij , dik + dkj)6. return D



Exemplu

Fie graful ponderat

x1

x2 x3

x4

x5

4

3

2 1

2

1



Matricea distanţelor

D0 =

0 2 ∞ ∞ 12 0 4 ∞ 3∞ 4 0 1 ∞∞ ∞ 1 0 21 3 ∞ 2 0

D =

0 2 4 3 12 0 4 5 34 4 0 1 33 5 1 0 21 3 3 2 0



Problema puncte bonus

primele cinci rezolvari corecte (CU EXPLICAŢII) primesc punctebonusrezolvarile trebuie trimise la adresa [email protected]

Problema: Într-o zi Hercule Poirot primește vizita bunului sau prieten capitanulHastings care a fost rugat sa investigheze un furt care a ramas nerezolvat de zeceani.Acum zece ani contesei Vera Rossakoff i-a fost furat faimosul diamant ”diamantulCullinan” din propriul castel. Contesa a dat o petrecere la castel cu câteva zileînainte de furt.Capitanul Hastings a intervievat persoanele care au participat la petrecere (Abe,Oliver, Li Chang, Darrell, Betsy, colonelul Appleby și Sonia), dar dupa zece ani nuși-au adus aminte foarte multe detalii.Detaliile cazului, locaţia diamantului arata ca faptașul cunoștea castelul. Hastingsa întrebat suspecţii de câte ori au fost la castel dar dupa zece ani nu și-au adusaminte.



Suspecţi:Abe, Oliver, Li Chang, Darrell, Betsy, colonelul Appleby și Sonia

Hastings i-a mai întrebat cu cine s-au întâlnit la castel:Abe: Oliver, Li Chang, Betsy și colonelul Appleby.Oliver: Abe, Li Chang, Darrell, Betsy și Sonia.Li Chang; Abe, Oliver și Darrell.Darrell: Oliver, Li Chang și Betsy.Betsy: Abe, Oliver, Darrell și Sonia.colonelul Appleby: Abe și Sonia.Sonia: Oliver, Betsy și colonelul Appleby.

Poirot a desenat ceva pe hârtie și dupa câteva minute a știut cine a furatdiamantul. Cine este hoţul?


Algoritmica grafurilor I. Introduceremihai-suciu/graf/curs01.pdf · · 2018-03-06Algoritmica...

Documents

Transcript of Algoritmica grafurilor I. Introduceremihai-suciu/graf/curs01.pdf · · 2018-03-06Algoritmica...