Algoritmica Grafurilor [PDF]

Zitiervorschau

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 1 C. Croitoru [email protected] FII

October 1, 2012

1 / 43

OUTLINE

1

Descrierea cursului

2

Interesul penru grafuri ˆın Informatic˘ a

3

Elemente introductive de complexitate

4

Problemele pentru seminarul 1

2 / 43

DESCRIEREA CURSULUI Pagina cursului http://thor.info.uaic.ro/˜ croitoru/ag/

3 / 43

DESCRIEREA CURSULUI Pagina cursului http://thor.info.uaic.ro/˜ croitoru/ag/ Obiective Student¸ii vor fi familiarizat¸i cu not¸iunile ¸si rezultatele de baz˘a ale Teoriei Algoritmice a Grafurilor, care vor fi aplicate ˆın proiectarea de algoritmi eficient¸i pentru diverse probleme de optimizare combinatoric˘a.

4 / 43

DESCRIEREA CURSULUI Pagina cursului http://thor.info.uaic.ro/˜ croitoru/ag/ Obiective Student¸ii vor fi familiarizat¸i cu not¸iunile ¸si rezultatele de baz˘a ale Teoriei Algoritmice a Grafurilor, care vor fi aplicate ˆın proiectarea de algoritmi eficient¸i pentru diverse probleme de optimizare combinatoric˘a.

Tematic˘ a General˘ a Clase de Complexitate, Vocabular al Teoriei Grafurilor, Probleme de drum(parcurgeri, drumuri minime, conexiune), Arbori part¸iali de cost minim (union-find, complexitate amortizat˘a), Cuplaje, Fluxuri, Reduceri polinomiale pentru probleme de decizie pe grafuri, Abord˘ari ale problemelor NP-dificile, Grafuri Planare.

5 / 43

DESCRIEREA CURSULUI Competent¸e acumulate Utilizarea grafurilor ca limbaj de modelare formal˘a. Cunoa¸sterea algoritmilor de baz˘a pentru problemele clasice pe grafuri. Recunoa¸sterea complexit˘a¸tii de calcul pentru probleme de optimizare.

6 / 43

DESCRIEREA CURSULUI Competent¸e acumulate Utilizarea grafurilor ca limbaj de modelare formal˘a. Cunoa¸sterea algoritmilor de baz˘a pentru problemele clasice pe grafuri. Recunoa¸sterea complexit˘a¸tii de calcul pentru probleme de optimizare. Metode de predare Prezentari video ale slide-urilor (cont¸inˆand notele de curs) disponibile in format pdf la inceputul semestrului.

http://thor.info.uaic.ro/˜ croitoru/ag/ag 12-13 allinone.pdf

7 / 43

DESCRIEREA CURSULUI Competent¸e acumulate Utilizarea grafurilor ca limbaj de modelare formal˘a. Cunoa¸sterea algoritmilor de baz˘a pentru problemele clasice pe grafuri. Recunoa¸sterea complexit˘a¸tii de calcul pentru probleme de optimizare. Metode de predare Prezentari video ale slide-urilor (cont¸inˆand notele de curs) disponibile in format pdf la inceputul semestrului.

http://thor.info.uaic.ro/˜ croitoru/ag/ag 12-13 allinone.pdf Tematica seminariilor Fiecare seminar dezbate cˆateva probleme (unele dintre ele dificile !) pentru a aprofunda subiectele introduse la curs. Toate problemele sunt postate la ˆınceputul semestrului astfel ˆıncˆat student¸ii interesat¸i s˘a caute solut¸ii originale sau s˘a studieze probleme similare ˆın bibliografia ˆınrudit˘a. 8 / 43

DESCRIEREA CURSULUI Bibliografie CROITORU C., Tehnici de baz˘a ˆın optimizarea combinatorie, Editura Univ. Al. I. Cuza Iasi, Iasi,1992. CROITORU C., Introducere in proiectarea algoritmilor paraleli, Editura Matrix Rom, Bucuresti, 2002. TOMESCU I., Probleme de combinatoric˘a ¸si teoria grafurilor, Editura did. ¸si ped., Bucuresti,1981. DIESTEL R., Graph Theory, Electronic Edition. CORMEN T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms,MIT Press 2001.

9 / 43

DESCRIEREA CURSULUI Bibliografie CROITORU C., Tehnici de baz˘a ˆın optimizarea combinatorie, Editura Univ. Al. I. Cuza Iasi, Iasi,1992. CROITORU C., Introducere in proiectarea algoritmilor paraleli, Editura Matrix Rom, Bucuresti, 2002. TOMESCU I., Probleme de combinatoric˘a ¸si teoria grafurilor, Editura did. ¸si ped., Bucuresti,1981. DIESTEL R., Graph Theory, Electronic Edition. CORMEN T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms,MIT Press 2001. Suplimentar http://thor.info.uaic.ro/˜ croitoru/ag/resurse bibliografice (optionale)

10 / 43

DESCRIEREA CURSULUI EVALUARE

Punctajul minim de promovare: 50 puncte.

11 / 43

DESCRIEREA CURSULUI EVALUARE

Punctajul minim de promovare: 50 puncte. FORME: Activitatea de la seminar (prezent¸a, participare la dezbateri): 0-18 puncte. Teme pentru acas˘a (3 teme, ˆın s˘apt˘amˆanile 5, 9,13), maxim 14 puncte fiecare: 0-42 puncte. Testul final scris (open books): 0-60 puncte.

12 / 43

DESCRIEREA CURSULUI EVALUARE

Punctajul minim de promovare: 50 puncte. FORME: Activitatea de la seminar (prezent¸a, participare la dezbateri): 0-18 puncte. Teme pentru acas˘a (3 teme, ˆın s˘apt˘amˆanile 5, 9,13), maxim 14 puncte fiecare: 0-42 puncte. Testul final scris (open books): 0-60 puncte. Nota final˘ a Student¸ii care au obt¸inut minim 50 puncte, sunt sortat¸i descresc˘ator dupa punctajul final ¸si clasificat¸i dupa regulile ETCS cu adapt˘arile precizate de FII. Bonus: Seminar Special. 13 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

A nice visualization by Akshay Java of network analysis of Twitter. 14 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Interest in scale-free networks started in 1999 with work by Albert-L´aszl´o Barab´asi and colleagues at the University of Notre Dame.

15 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

World.png A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps. 16 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Konfidi – Trust Networks with PGP and RDF. 17 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Graph-based knowledge representation formalisms: Bayesian Networks (BNs), Semantic Networks (SNs), Conceptual Graphs (CGs), Formal Concept Analysis (FCA), CP-nets, GAI-nets, etc.

18 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Argumentation Frameworks. 19 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Environmental Sensor Networks (ESN), Object Sensor Networks (OSN) or Body Sensor Network (BSN) operate a variety of different protocols for the specific application environment. 20 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Shot.png Graph-based Data Basis. 21 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Visualization systems. 22 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Madrid-Metro. 23 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

A set of such triples is called an RDF graph. 24 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Utilizing ASP for Generating and Visualizing Argumentation Frameworks. 25 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

b

a

26 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

b

? a

27 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

b

NO a

28 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

b

a

29 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

b

? a

30 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

b

YES a

31 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

d

b

a

e

c

f

32 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

d

b

? a

e

c

f

33 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

d

b

YES a

e

c

EXTENSION f

34 / 43

˘ INTERESUL PENTRU GRAFURI ˆIN INFORMATICA

Visualizing a FCA lattice. 35 / 43

ELEMENTE INTRODUCTIVE DE COMPLEXTATE (ag 12-13 allinone.pdf, primul capitol)

P: Clasa problemelor (de decizie) pentru care exista algoritmi determini¸sti cu timp polinomial de rezolvare.

NP: Clasa problemelor (de decizie) pentru care exista algoritmi nedetermini¸sti cu timp polinomial de rezolvare.

P ⊆ NP (Incluziune strict˘a ?) 36 / 43

ELEMENTE INTRODUCTIVE DE COMPLEXTATE Problema P se reduce polinomial la problema Q, dac˘a orice intrare a problemei P se poate transforma ˆın timp polinomial ˆıntr-o intrare a problemei Q, astfel ˆıncˆat rezolvˆand Q pe aceast˘a intrare se obt¸ine r˘aspunsul (corect) pentru P. Definit¸ie Problema de decizie P se nume¸ste NP-dificil˘a (NP-hard) dac˘a orice problem˘a din NP se reduce polinomial la P.

Definit¸ie Problema de decizie P se nume¸ste NP-complet˘a dac˘a este NP-dificil˘a ¸si ˆın plus apart¸ine la NP.

37 / 43

PROBLEMELE PENTRU SEMINARUL 1 1 Fie a, b ∈ N. Demonstrat¸i c˘a na = O(nb ) dac˘a ¸si numai dac˘a a ≤ b. Demonstrat¸i c˘a na = O(e n ) ¸si c˘a nu are loc e n = O(na ) (e este baza logaritmului natural). 2 Argumentat¸i o evaluare de tipul T (n) = Θ(.) pentru timpul de executie a algoritmului: Sum˘a Tripl˘a (n) s←0 for i = 1, n do for j = i, n do for k = j, n do s ←s +1 38 / 43

PROBLEMELE PENTRU SEMINARUL 1

3 Consider˘am urm˘atoarele dou˘a funct¸ii: F(n) if (n = 1) return true else return G (n − 1) G(n) if (n = 1) return false else return F (n − 1) Stabilit¸i ¸si argumentat¸i valorile F (2012) ¸si G (2013).

39 / 43

PROBLEMELE PENTRU SEMINARUL 1 4 Pentru ˆınmult¸irea a dou˘a numere ˆıntregi se poate folosi algoritmul descris mai jos prin dou˘a exemple. Se observ˘a c˘a operat¸iile efectuate sunt doar ˆınmult¸irea cu doi, ˆımp˘art¸irea ˆıntreag˘a la doi ¸si adunarea numerelor ˆıntregi. 48 × 17 29 × 135 48 17 29 135 24 34 14 270 12 68 7 540 6 136 3 1080 3 272 1 2160 1 544 ========== ============== 3915 816 (se adun˘a numerele de pe coloana 2 care au pe coloana 1 numere impare) Scriet¸i o funct¸ie recursiv˘a pentru produsul a dou˘a numere ˆıntregi care s˘a corespund˘a acestui algoritm ¸si demonstrat¸i-i corectitudinea. Stabilit¸i complexitatea timp T (n) pentru aceast˘a funct¸ie (n este num˘arul bit¸ilor necesari reprezent˘arii binare a fiec˘aruia dintre cei doi factori). 40 / 43

PROBLEMELE PENTRU SEMINARUL 1

5 a) ˆInf˘a¸sur˘atoarea convex˘a a n puncte Pi (xi , yi ), i = 1, n din plan, este cel mai mic poligon convex (ˆın raport cu incluziunea) care cont¸ine toate cele n puncte. Demonstrat¸i c˘a dac˘a dispunem de un algoritm care s˘a determine vˆarfurile ˆınf˘a¸sur˘atoarei convexe a n puncte date cu complexitatea timp T (n) atunci putem sorta un vector ˆıntreg n-dimensional ˆın timpul T (n). b) Dat¸i dou˘a exemple de algoritmi de sortare. Ce complexitate au ?

41 / 43

PROBLEMELE PENTRU SEMINARUL 1 6 Numim pin un arbore cu m˘acar trei noduri cu proprietatea c˘a unicul vecin al oric˘arei frunze (nod cu un singur vecin) are exact doi vecini. Pentru un arbore T cu cel put¸in trei noduri, not˘am cu pin(T ) subarborele lui T care este pin ¸si are num˘ar maxim de noduri. Descriet¸i un algoritm care, pentru T dat, construie¸ste pin(T ).

Arborele T Arborele T

Un pin

Pin(T) Pin(T)

42 / 43

ˆINTREBARI ˘ ? Mult¸umesc!

43 / 43

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 2 C. Croitoru [email protected] FII

October 8, 2012

1 / 10

OUTLINE

1

Vocabular al teoriei grafurilor (ag 12-13 allinone.pdf pag. 17 −→ )

2

Problemele pentru seminarul 2

2 / 10

Vocabular-Definit¸ia unui graf Mult¸imi stabile SM

Intrare: Intrebare:

G un graf, k ∈ N. Exist˘a S mult¸ime stabil˘a ˆın G , cu |S| ≥ k?

NP-complet˘a (Karp, 1972).

3 / 10

Vocabular-Definit¸ia unui graf Mult¸imi stabile SM

Intrare: Intrebare:

G un graf, k ∈ N. Exist˘a S mult¸ime stabil˘a ˆın G , cu |S| ≥ k?

NP-complet˘a (Karp, 1972). Cuplaje P2

Intrare: G un graf. Ie¸sire: ν(G ) ¸si un ”martor”: M cuplaj ˆın G , cu |M| = ν(G ).

Polinomial rezolvabil˘a ( Edmonds, 1965). 4 / 10

Vocabular-Definit¸ia unui graf Colorarea vˆarfurilor COL

Intrare: Intrebare:

G un graf, k ∈ N. Admite G o k-colorare?

Este NP-complet˘a chiar pentru k = 3.

5 / 10

Vocabular-Definit¸ia unui graf Colorarea vˆarfurilor COL

Intrare: Intrebare:

G un graf, k ∈ N. Admite G o k-colorare?

Este NP-complet˘a chiar pentru k = 3. Colorarea muchiilor P4

Intrare: G un graf. Ie¸sire: χ0 (G ) ¸si un ”martor”: o χ0 (G )-colorare a muchiilor lui G .

Este NP-complet˘a chiar dac˘a e u¸sor aproximabil˘a. 6 / 10

Vocabular-Definit¸ia unui graf Izomorfism ISO

Intrare: Intrebare:

G , H grafuri. G∼ = H?

Nu se ¸stie dac˘a e din P dar nici nu s-a ar˘atat c˘a e NP-complet˘a.

7 / 10

Vocabular-Definit¸ia unui graf Izomorfism ISO

Intrare: Intrebare:

G , H grafuri. G∼ = H?

Nu se ¸stie dac˘a e din P dar nici nu s-a ar˘atat c˘a e NP-complet˘a. Izomorfism SISO

Intrare: Intrebare:

G , H grafuri. Are G un subgraf G 0 astfel ca G 0 ∼ = H?

Este NP-complet˘a.

8 / 10

Vocabular

1 2 3 4 5 6 7 8 9

Variat¸ii ˆın definit¸ia unui graf Grade Subgrafuri Operat¸ii cu grafuri Clase de grafuri Drumuri ¸si circuite Conexiune Matrici asociate Structuri de date

9 / 10

Problemele pentru seminarul 2

Se vor discuta (cel put¸in) patru probleme dintre urm˘atoarele: 1 2 3 4 5 6

Problema Problema Problema Problema Problema Problema

1, 2, 4, 4, 2, 1,

Setul Setul Setul Setul Setul Setul

1 1 1 7” 3” 8’

10 / 10

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 3 C. Croitoru [email protected] FII

October 15, 2012

1 / 11

OUTLINE

1

Vocabular al teoriei grafurilor (ag 12-13 allinone.pdf pag. 50 −→ 67)

2

Probleme de drum ˆın (di)grafuri (ag 12-13 allinone.pdf pag. 68 −→ 72 )

3

Problemele pentru seminarul 3

2 / 11

Vocabular

1 2 3 4 5 6 7 8 9

Variat¸ii ˆın definit¸ia unui graf Grade Subgrafuri Operat¸ii cu grafuri Clase de grafuri Drumuri ¸si circuite Conexiune Matrici asociate Structuri de date

3 / 11

Probleme de drum

1

Parcurgeri sistematice BFS

DFS

Componente conexe, tari conexe !!! (pentru examen; algoritmic˘a u¸soar˘a !!!)

4 / 11

Problemele pentru seminarul 3 Acesta este un seminar special, cu probleme foarte u¸soare, avˆand ca singur scop fixarea unor not¸iuni.

1 Fie G1 , G2 , G3 trei grafuri. Se ¸stie c˘a G1 ∼ 6 G2 ¸si c˘a G2 ∼ 6 G3 . = = ∼ Rezult˘a c˘a G1 = 6 G3 ? (justificare) 2 Sunt cele dou˘a grafuri desenate mai jos izomorfe ? (justificare)

5 / 11

Problemele pentru seminarul 3 3 Demonstrat¸i c˘a dac˘a un graf conex G are exact un circuit atunci |G | = |E (G )|. 4 Determinat¸i num˘arul de stabilitate al grafului desenat mai jos. (justificare)

5 Fie G un graf conex cu |G | > 1 si f˘ar˘a vˆırfuri de grad 1. Demonstrat¸i c˘a |E (G )| ≥ n. 6 / 11

Problemele pentru seminarul 3 6 Fie G = (V , E ) un graf conex cu |G | ≥ 2. Demonstrat¸i c˘a exist˘a un vˆarf v0 ∈ V astfel ˆıncˆat G − v0 este conex. 7 Este posibil ca num˘arul arborilor part¸iali ai unui graf s˘a fie 1? Dar 2 ? (justificare) 8 S˘a se determine L(L(G )), unde graful G este:

7 / 11

Problemele pentru seminarul 3 9 Dac˘a G este graful desenat mai jos, este L(G ) –graful reprezentativ al muchiilor sale– hamiltonian? (justificare)

10 Precizat¸i num˘arul cromatic (argumentare) al complementarului grafului de mai sus. 11 Precizat¸i num˘arul de conexiune (argumentare) al grafului de la problema 9. 8 / 11

Problemele pentru seminarul 3 12 Este graful urm˘ator autocomplementar ? (argumentare)

13 Are graful de mai sus doi arbori part¸iali f˘ar˘a muchii comune? (argumentare) 14 Stabilit¸i num˘arul arborilor part¸iali ai complementarului grafului de la problema 12. (argumentare) 9 / 11

Problemele pentru seminarul 3 15 Stabilit¸i cardinalul maxim al unei multimi stabile din graful K2 × G , unde G este tot graful de la problema 12. 16 Dac˘a G este graful desenat mai jos, este L(G ) –graful reprezentativ al muchiilor sale– hamiltonian? (justificare)

17 Pentru graful G desenat mai sus s˘a se determine num˘arul cromatic χ(G ) (argumentare). 10 / 11

Problemele pentru seminarul 3 18 Este graful de la problema 16 izomorf cu complementarul s˘au ? (justificare) 19 Determinat¸i num˘arul de conexiune al grafului de la problema 16. (justificare) 20 Determinat¸i diametrul grafului de la problema 16. (justificare) 21 Determinat¸i χ 0 (G ), indicele cromatic al grafului de la problema 16. (justificare) 11 / 11

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 4 C. Croitoru [email protected] FII

October 22, 2012

1 / 13

OUTLINE

1

Probleme de drum ˆın (di)grafuri (ag 12-13 allinone.pdf pag. 73 −→ . . . )

2

Problemele pentru seminarul 4

2 / 13

Probleme de drum Drumuri de cost minim P1 Date G digraf;a : E (G ) → R; s, t ∈ V (G ),s 6= t. ∗ ∈ D , astfel ˆ S˘a se determine Dst ıncˆıt st ∗ a(Dst ) = min{a(Dst ) | Dst ∈ Dst }.

P2 Date G digraf; a : E (G ) → R; s ∈ V (G ). S˘a se determine Dsi∗ ∈ Dsi ∀i ∈ V (G ), a.ˆı. a(Dsi∗ ) = min{a(Dsi ) | Dsi ∈ Dsi }.

P3 Date G digraf; a : E (G ) → R. S˘a se determine Dij∗ ∈ Dij ∀i, j ∈ V (G ), a.ˆı. a(Dij∗ ) = min{a(Dij ) | Dij ∈ Dij }. 3 / 13

Drumuri de cost minim Rezolvarea problemei P2 Teorema 1. Fie G = (V , E ) digraf, V = {1, . . . , n}, s ∈ V ¸si a : E → R, astfel ˆıncˆıt ∀C circuit ˆın G , a(C ) > 0.

(I )

Atunci (u1 , . . . , un ) este o solut¸ie a sistemului ( (∗)

us = 0 ui = min(uj + aji ) j6=i

∀i 6= s.

dac˘ a ¸si numai dac˘ a ∗ ∀i ∈ V , ∃Dsi ∈ Dsi astfel ˆıncˆıt a(Dsi∗ ) = ui ¸si a(Dsi∗ ) = min{a(D) | D ∈ Dsi }. 4 / 13

Drumuri de cost minim Rezolvarea problemei P2 dac˘a G este digraf f˘ar˘a circuite O numerotare aciclic˘ a a (vˆarfurilor) digrafului G = (V , E ) este un vector ord[v ] v ∈ V , (cu interpretarea ord[v ] = num˘arul de ordine al vˆarfului v ) a. ˆı. ∀vw ∈ E ⇒ ord[v ] < ord[w ].

G este un digraf f˘ar˘a circuite dac˘a ¸si numai dac˘a admite o numerotare aciclic˘a . Sortare topologic˘a O(n + m). Rezolvarea sistemului (∗) prin substitut¸ie.

5 / 13

Drumuri de cost minim Rezolvarea problemei P2 dac˘a ∀ij ∈ E (G ) avem aij ≥ 0 !!! Algoritmul lui Dijkstra 1. S ← {s}; us ← 0; ˆınainte[s] ← 0; for i ∈ V \ {s} do { ui ← asi ; ˆınainte[i] ← s } // dup˘a aceste init¸ializ˘ari (D) are loc

2. while S 6= V do { determin˘a 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˘a este O(n2 ) . 6 / 13

Drumuri de cost minim

Algoritmul lui Dijkstra Este posibil˘a organizarea unor cozi cu prioritate (de exemplu heap-urile) pentru obt¸inerea unui algoritm cu complexitatea O(m log n) (unde m = |E |) Johnson ,1977). Cea mai bun˘a implementare se obt¸ine utilizˆand heap-uri Fibonacci, ceea ce conduce la o complexitate timp de O(m + n log n) (Fredman ¸si Tarjan, 1984).

7 / 13

Drumuri de cost minim Rezolvarea problemei P2 ˆın cazul general. Algoritmul lui Bellman, Ford, Moore (∼ 1960) 1. us1 ← 0; for i ∈ V \ {s} do ui1 ← asi ; // evident (BM) are loc 2. for m := 1 to n − 2 do for i := 1 to n do
uim+1 ← min uim , minj6=i (ujm + aji ) Complexitatea O(n3 ), dac˘a determinarea minimului din pasul 2 necesit˘a O(n) operat¸ii. Testarea ˆın O(n3 ) a existent¸ei unui circuit C de cost negativ ˆın digraful G ! 8 / 13

Problemele pentru seminarul 4

1 2 3

Problema 1, Setul 3” Problema 3, Setul 6 3-4 probleme din lista urm˘ atoare :)

9 / 13

Probleme pentru seminarul 4 1 S˘a se construiasc˘a o funct¸ie care s˘a recunoasc˘a un turneu. La intrare aceasta va primi un digraf G = ({1, ..., n}, E ) reprezentat cu ajutorul listelor de adiacent¸˘a ¸si va returna true sau false. Complexitatea timp?.

2 S˘a se construiasc˘a o funct¸ie care primind la intrare un digraf G = ({1, ..., n}, E ) reprezentat cu ajutorul listelor de adiacent¸˘a s˘a returneze inversul lui G reprezentat cu ajutorul listelor de adiacent¸˘a. Complexitatea timp trebuie s˘a fie O(n + |E |).

3 Se consider˘a un graf G = ({1, ..., n}, E ) reprezentat cu ajutorul matricii de adiacent¸˘a. Mult¸imea de n − 1 muchii A este astfel ca T = (V , A) este arbore part¸ial al lui G . Construit¸i un algoritm care s˘a listeze circuitele care se formeaz˘a prin ad˘augarea muchiilor din E − A la T . Reprezentarea lui T trebuie s˘a permit˘a depistarea fiec˘arui astfel de circuit ˆın timpul O(n). 10 / 13

Probleme pentru seminarul 4 4 S˘a se construiasc˘a o funct¸ie care s˘a determine gradul maxim al unui vˆarf al unui graf. La intrare aceasta va primi un graf G = ({1, ..., n}, E ) reprezentat cu ajutorul listelor de adiacent¸˘a ¸si va returna ∆(G ). Stabilit¸i complexitatea timp a algoritmului folosit.

5 Construit¸i o funct¸ie care primind la intrare graful G = (V , E ) reprezentat cu ajutorul listelor de adiacent¸˘a ¸si k, un num˘ar ˆıntreg pozitiv, returneaz˘a graful G (k) cu aceea¸si mult¸ime de virfuri ca ¸si G , ˆın care dou˘a virfuri distincte sunt adiacente dac˘a ¸si numai dac˘a ˆın graful init¸ial sunt conectate printr-un drum de lungime cel mult k. Care este complexitatea timp?

6 Graful conex G = (V , E ) cu n vˆarfuri ¸si m muchii, este reprezentat cu ajutorul listelor de adiacent¸˘a. Dat¸i un algoritm care s˘a construiasc˘a ˆın timpul O(n + m) listele de adiacent¸˘a ale unui arbore part¸ial al lui G . 11 / 13

Probleme pentru seminarul 4 7 Fie G = (V , E ) un graf cu ordinul |V | ≥ 2 ¸si T = (V , ET ) un arbore part¸ial al lui G , dat de tabloul (p[v ])v ∈V , unde p[v ] este p˘arintele lui v ˆın T : vˆarful dinaintea lui v de pe drumul unic de la o r˘ad˘acin˘a fixat˘a r , la v , ˆın T (p[r ] = r ). Dat¸i un algoritm care s˘a determine, ˆın timpul O(|V |), un vˆarf v0 pendant (frunz˘a) ˆın T ¸si apoi demonstrat¸i c˘a G − v0 este conex.

8 Digraful G = (V , E ) este dat prin listele de adiacent¸˘a. S˘a se decid˘a ˆın O(|V | + |E |) dac˘a se pot ordona vˆarfurile sale: vi1 , . . . , vi|V | , astfel ˆıncˆat dac˘a vij apare ˆın lista de adiacent¸˘a a lui vik atunci k < j.

9 Fie T = ({1, . . . , n}, ET ) un arbore (n ≥ 2), dat de tabloul (p[v ])v ∈V , unde p[v ] este p˘arintele lui v ˆın T : vˆarful dinaintea lui v de pe drumul unic de la o r˘ad˘acin˘a fixat˘a r , la v , ˆın T (p[r ] = r ). Descriet¸i un algoritm care s˘a construiasc˘a , ˆın timpul O(n), listele de adiacent¸˘a ale lui T . 12 / 13

Probleme pentru seminarul 4 10 Se consider˘a un graf G = (V , E ) (V = {1, . . . , n}), izomorf cu graful circuit (cu cel put¸in 3 vˆarfuri), G ∼ = Cn . Fiecare muchie e ∈ E are asociat un cost real c(e). Aceste informat¸ii sunt disponibile ˆın tablourile dreapta ¸si cost de dimensiune n cu semnificat¸ia: dreapta[v ] = vecinul din dreapta al lui v , iar costul muchiei {v , dreapta(v )} este cost[v ]. Descriet¸i un algoritm cˆat mai eficient pentru aflarea unui arbore part¸ial al lui G de cost minim.

11 Se consider˘a un graf G = (V , E ) (V = {1, . . . , n}), reprezentat cu ajutorul listelor de adiacent¸˘a. Se ¸stie c˘a graful are gradul minim δ(G ) m˘arginit de o constant˘a c ∈ N. Descriet¸i un algoritm cu complexitatea timp O(n) pentru determinarea lui δ(G ) ¸si a unui vˆarf v0 ∈ V cu gradul ˆın G egal cu δ(G ). 13 / 13

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 5 C. Croitoru [email protected] FII

October 29, 2012

1 / 14

OUTLINE

1

Probleme de drum minim (ag 12-13 allinone.pdf pag. 117 −→ 124 )

2

Probleme de conexiune (ag 12-13 allinone.pdf pag. 124 −→ 149 )

3

Problemele pentru seminarul 5

4

Prezentarea temei pentru acas˘ a

2 / 14

Probleme de drum minim Rezolvarea problemei P3 P3 Date G digraf; a : E (G ) → R. S˘a se determine Dij∗ ∈ Dij ∀i, j ∈ V (G ), a.ˆı. a(Dij∗ ) = min{a(Dij ) | Dij ∈ Dij }.

3 / 14

Probleme de drum minim Rezolvarea problemei P3 P3 Date G digraf; a : E (G ) → R. S˘a se determine Dij∗ ∈ Dij ∀i, j ∈ V (G ), a.ˆı. a(Dij∗ ) = min{a(Dij ) | Dij ∈ Dij }. O(n4 ) Iterarea algoritmului lui Bellman-Ford pentru s = 1, n

4 / 14

Probleme de drum minim Rezolvarea problemei P3 P3 Date G digraf; a : E (G ) → R. S˘a se determine Dij∗ ∈ Dij ∀i, j ∈ V (G ), a.ˆı. a(Dij∗ ) = min{a(Dij ) | Dij ∈ Dij }. O(n4 ) Iterarea algoritmului lui Bellman-Ford pentru s = 1, n O(n3 ) Iterarea algoritmului lui Dijkstra, dup˘a preprocesare!

5 / 14

Probleme de drum minim Rezolvarea problemei P3 P3 Date G digraf; a : E (G ) → R. S˘a se determine Dij∗ ∈ Dij ∀i, j ∈ V (G ), a.ˆı. a(Dij∗ ) = min{a(Dij ) | Dij ∈ Dij }. O(n4 ) Iterarea algoritmului lui Bellman-Ford pentru s = 1, n O(n3 ) Iterarea algoritmului lui Dijkstra, dup˘a preprocesare! O(n3 log n) ˆInmult¸iri matriciale!

6 / 14

Probleme de drum minim Rezolvarea problemei P3 P3 Date G digraf; a : E (G ) → R. S˘a se determine Dij∗ ∈ Dij ∀i, j ∈ V (G ), a.ˆı. a(Dij∗ ) = min{a(Dij ) | Dij ∈ Dij }. O(n4 ) Iterarea algoritmului lui Bellman-Ford pentru s = 1, n O(n3 ) Iterarea algoritmului lui Dijkstra, dup˘a preprocesare! O(n3 log n) ˆInmult¸iri matriciale! O(n3 ) Algoritmul lui Floyd-Warshal

7 / 14

Rezolvarea problemei P3 Algoritmul lui Floyd-Warshal 1: for i := 1 to n do for j := 1 to n do { ˆınainte(i, j) ← i; if i = j then { aii ← 0;ˆınainte(i, i) ← 0 } } 2: for m := 1 to n do for i := 1 to n do for j := 1 to n do if aij > aim + amj then { aij ← aim + amj ; ˆınainte(i, j) ←ˆınainte(m, j) if (i = j ∧ aij < 0) then return ”circuit negativ“ } 8 / 14

Probleme de conexiune

Teorema lui Menger Fie G = (V , E ) (di)graf ¸si X , Y ⊆ V . Atunci num˘arul maxim de XY -drumuri disjuncte este egal cu cardinalul minim al unei mult¸imi XY -separatoare.

Fie G = (V , E ) un (di)graf ¸si s, t ∈ V , astfel ˆıncˆıt s 6= t, st ∈ / E. Exist˘a k drumuri intern disjuncte de la s la t ˆın G dac˘a ¸si numai dac˘a ˆındep˘artˆınd mai put¸in de k vˆırfuri diferite de s ¸si t, ˆın (di)graful r˘amas exist˘a un drum de la s la t.

9 / 14

Probleme de conexiune

Consecint¸˘ a Un graf G este p-conex dac˘a G = Kp sau ∀st ∈ E (G ) exist˘a p drumuri intern disjuncte de la s la t ˆın G . Determinarea num˘arului k(G ) de conexiune a grafului G (cea mai mare valoare a lui p pentru care G este p-conex) se reduce la determinarea lui min p({s}, {t}; G ) st∈E (G )

(care se poate obt¸ine ˆın timp polinomial.)

10 / 14

Probleme de conexiune

Teorema lui K¨ onig Dac˘a G = (S, R; E ) este un graf bipartit, atunci cardinalul maxim al unui cuplaj este egal cu cardinalul minim al unei mult¸imi de vˆırfuri incidente cu toate muchiile grafului.

Consecint¸˘ a: Dac˘a G e graf bipartit, atunci :

ν(G ) = |G | − α(G ).

11 / 14

Probleme de conexiune Teorema lui Hall Dac˘a A = (Ai ; i ∈ I ) este o familie de submult¸imi ale lui S, o funct¸ie rA : I → S cu proprietatea c˘a rA (i) ∈ Ai , ∀i ∈ I se nume¸ste funct¸ie de reprezentare pentru familia A. ˆIn acest caz, (rA (i); i ∈ I ) formeaz˘a un sistem de reprezentant¸i ai familiei A. Dac˘a funct¸ia de reprezentare rA este injectiv˘a atunci rA (I ) ⊆ S se nume¸ste sistem de reprezentant¸i distinct¸i ai familiei A, sau transversal˘a. Teorema lui Hall Familia A = (Ai ; i ∈ I ) de submult¸imi ale lui S admite o transversal˘a dac˘a ¸si numai dac˘a (H)

|A(J)| ≥ |J|

∀J ⊆ I .

12 / 14

Probleme de conexiune

Structura grafurilor p-conexe

Teorema lui Dirac Dac˘a G = (V , E ) este un graf p-conex p ≥ 2, atunci prin orice p vˆırfuri ale sale trece un circuit.

Teorema lui Erd¨os ¸si Chvatal Fie G un graf p-conex. Dac˘a α(G ) ≤ p atunci G este hamiltonian.

13 / 14

Problemele pentru seminarul 5

Se vor discuta (cel put¸in) patru probleme dintre urm˘atoarele: 1 2 3 4 5 6

Problema Problema Problema Problema Problema Problema

4, 2, 3, 1, 4, 1,

Setul Setul Setul Setul Setul Setul

3” 4 5 4’ 4’ 6

14 / 14

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 6 C. Croitoru [email protected] FII

November 5, 2012

1 / 12

OUTLINE

1

Arbori (ag 12-13 allinone.pdf pag. 150 −→ 182 )

2

Problemele pentru seminarul 6

2 / 12

Arbori Teoreme de caracterizare Teorem˘ a. Fie G = (V , E ) un graf. Urm˘atoarele afirmat¸ii sˆınt echivalente: (i) G este arbore (este conex ¸si f˘ar˘a circuite). (ii) G este conex ¸si este minimal cu aceast˘a proprietate. (iii) G este f˘ar˘a circuite ¸si este maximal cu aceast˘a proprietate. Teorem˘ a. Urm˘atoarele afirmat¸ii sˆınt echivalente pentru un graf G = (V , E ) cu n vˆırfuri: (i) G este arbore. (ii) G este conex ¸si are n − 1 muchii. (iii) G este far˘a circuite ¸si are n − 1 muchii. (iv) G = Kn pentru n = 1, 2 ¸si G 6= Kn pentru n ≥ 3 ¸si ad˘augarea unei muchii la G produce exact un circuit.

3 / 12

Arbori Generarea arborilor part¸iali ai unui graf generare-arbori-part¸iali(int i); // se genereaz˘a tot¸i arborii part¸iali ai lui G avˆınd drept prime i − 1 muchii,elementele T (1), . . . , T (i − 1) ale tabloului E (ordonate cresc˘ator). variabile locale:

j ∈ {1, . . . m}; S, list˘a de vˆırfuri; x ∈ V ; if i = n then // {T (1), . . . , T (n − 1)} formeaz˘a un arbore part¸ial ; prelucreaz˘a T ( listeaz˘a, memoreaz˘a etc.)

4 / 12

Arbori Generarea arborilor part¸iali ai unui graf (continuare) else if i = 1 then for j := 1 to dG (v0 ) do { T [i] ← j; A: generare-arbori-part¸iali(i + 1); B: } else for j := T [i − 1] + 1 to m − (n − 1) + i do

 if {T [1], . . . , T [i − 1]} ∪ {j} G nu are circuite then { T [i] ← j; A: generare-arbori-part¸iali(i + 1); B: } 5 / 12

Arbori Num˘ararea arborilor part¸iali ai unui graf Fie G = (V , E ) un multigraf cu V = {1, 2, . . . , n}. Cosider˘am A = (aij )n×n matricea de adiacent¸˘a a lui G (aij = multiplicitatea muchiei ij dac˘a ij ∈ E , altfel 0). Fie D = diag (dG (1), dG (2), ..., dG (n)). Matricea L[G ] = D − A se nume¸ste matricea de admitant¸˘ aa multigrafului G sau matricea Laplace a lui G . Teorem˘ a (Kirchoff-Trent; Matrix Tree Theorem) Dac˘a G este un multigraf cu mult¸imea de vˆırfuri {1, . . . , n} ¸si L[G ] matricea Laplace, atunci |TG | = det(L[G ]ii ) ∀i ∈ {1, . . . , n}. L[G ]ij noteaz˘a minorul lui L[G ] obt¸inut prin ˆındep˘artarea liniei i ¸si coloanei j. Corolar TKn = nn−2 (Cayley).

6 / 12

Arbori Arbori part¸iali de cost minim. (P1) Date G = (V , E ) graf ¸si c : E → R (c(e) – costul muchiei e), s˘a se determine T ∗ ∈ TG astfel ˆıncˆıt c(T ∗ ) = min{c(T ) | T ∈ TG }, P unde c(T ) = e∈E (T ) c(e).

Algoritm generic Init¸ial, T 0 = (T10 , T20 , . . . , Tn0 ), Ti0 = ({i}, ∅), i = 1, n ( V = {1, 2, . . . , n}). ˆIn pasul k ( k = 0, n − 2), din familia T k = (T k , T k , . . . , T k ) de n − k 1 2 n−k arbori a.ˆı V (Tik )i=1,n−k este partit¸ie a lui V , se construie¸ste T k+1 : - se alege Tsk unul din arborii familiei T k . - dintre muchiile lui G cu o extremitate ˆın Tsk ¸si cealalt˘a ˆın V − V (Tsk ), se alege una de cost minim, e ∗ = vs vj ∗ unde vj ∗ ∈ V (Tjk∗ ). - T k+1 = (T k \ {Tsk , Tjk∗ }) ∪ T , unde T este arborele obt¸inut din Tsk ¸si Tjk∗ la care ad˘aug˘am muchia e ∗ . Teorem˘ a. Dac˘a G = (V , E ) este un graf conex cu V = {1, 2, . . . , n} atunci T1n−1 construit de algoritmul descris mai sus este arbore part¸ial de cost minim. 7 / 12

Arbori Algoritmul lui Prim (implementare Dijkstra ) Arborele Tsk va fi ˆıntotdeauna arborele cu cele mai multe vˆırfuri dintre arborii familiei curente. La fiecare pas k > 0 avem un arbore Ts = (Vs , Es ) cu k + 1 vˆırfuri, ceilalt¸i n − k − 1 avˆınd cˆıte un singur vˆırf. Fie α[1..n] cu componente din V ¸si β[1..n] cu componente reale a.ˆı. :  ∀j ∈ V − Vs , β j = c(α[j]j) = min{c(ij) | i ∈ Vs , ij ∈ E } 1. Vs :← {s}; (s ∈ V , oarecare ) Es ← ∅; for v ∈ V \ {s} do { α[v ] := s; β[v ] := c(sv )}; 2. while Vs 6= V do { determin˘a j ∗ ∈ V \ Vs a.ˆı. β[j ∗ ] = min{β[j] | j ∈ V − Vs } ; Vs ← Vs ∪ {j ∗ }; Es := Es ∪ {α[j ∗ ]j ∗ }; for j ∈ V − Vs do if β[j] > c[j ∗ j] then { β[j] ← c[j ∗ j]; α[j] :← j ∗ } }

8 / 12

Arbori Algoritmul lui Kruskal ˆIn metoda general˘a se va alege la fiecare pas drept arbore Tsk unul din cei doi arbori cu proprietatea c˘ a sˆınt ”unit¸i” printr-o muchie de cost minim printre toate muchiile cu extremit˘ a¸tile pe arbori diferit¸i. Dac˘a not˘am cu T = E (T k ), atunci algoritmul poate fi descris astfel: 1. Sorteaz˘a E = (e1 , e2 , . . . , em ) astfel ˆıncˆıt: c(e1 ) ≤ c(e2 ) ≤ . . . ≤ c(em ). 1.2 T ← ∅; i ← 1; 2. while i ≤ m do { if hT ∪ {ei }iG nu are circuite then T ← T ∪ {ei } ; i ++ } Pasul 1 necesit˘a O(m log n) operat¸ii. Pentru realizarea eficient˘a a testului din pasul 2 va fi necesar s˘a reprezent˘am la fiecare pas k, V (T1k ), V (T2k ), . . . , V (Tnk ) ¸si s˘a test˘am dac˘a muchia ei curent˘a are ambele extremit˘a¸ti ˆın aceea¸si mult¸ime. Se vor folosi pentru reprezentarea acestor mult¸imi, arbori (care nu sˆınt ˆın general subarbori ai lui G ). 9 / 12

Arbori Union-Find - Tarjan pred[1..n]: pred[v ]= vˆırful dinaintea lui v de pe drumul la v de la r˘ ad˘ acina arborelui care memoreaz˘ a mult¸imea la care apart¸ine v ; pred[v ] = 0 ⇔ v este r˘ ad˘ acina arborelui; pred[v ] < 0 ⇔ v este r˘ ad˘ acin˘ a a unui arbore ¸si −pred[v ] este cardinalul mult¸imii memorate ˆın el”. Ad˘aug˘am ˆın pasul 1 init¸ializarea 1.3 ¸si modific˘am pasul 2 al algoritmului astfel: 1.3 for v ∈ V do pred[v ] ← −1; 2. while i ≤ m do { fie ei = vw ; x ← find(v ); y ← find(w ); if x 6= y then { union(x, y ); T ← T ∪ {ei } } i ++ } 10 / 12

Arbori Union-Find - Tarjan Procedura union ¸si funct¸ia find sunt: procedure union(v , w : V ); //v ¸si w sunt r˘ad˘acini, variabila local˘a ˆıntreag˘a t t ← pred[v ] + pred[w ]; if pred[v ] > pred[w ] then { pred[v ] ← w ; pred[w ] ← t } else { pred[w ] ← v ; pred[v ] ← t } function find(v : V ); //variabile ˆıntregi locale i, j, k; i ← v; while pred[i] > 0 do i ← pred[i]; j ← v; while pred[j] > 0 do { k ← pred[j]; pred[j] ← i; j ← k; } return i

Complexitatea pasului 2 este O(m· α(m, n)), unde α(m, n) este inversa funct¸iei lui Ackermann. 11 / 12

Problemele pentru seminarul 6

Se vor discuta (cel put¸in) patru probleme dintre urm˘atoarele: 1 2 3 4

Problema 1, Setul 13 Problemmele 1,2,4 Setul 5 Problema 1, Setul 7 Problemele 1,2 Setul 17

12 / 12

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 7 C. Croitoru [email protected] FII

November 12, 2012

1/9

OUTLINE

1

Cuplaje (ag 12-13 allinone.pdf pag. 183 −→ 211 )

2

Problemele pentru seminarul 7

2/9

Cuplaje Problema cuplajului maxim Fie G = (V , E ) un (multi)graf. Dac˘a A ⊆ E ¸si v ∈ V , vom nota gradul vˆırfului v ˆın graful part¸ial < A >G .

dA (v )

Se nume¸ste cuplaj (sau mult¸ime independent˘ a de muchii) al grafului G , orice mult¸ime M de muchii cu proprietatea c˘a dM (v ) ≤ 1, ∀v ∈ V . Notat¸ie: MG = {M | M ⊆ E , M cuplaj ˆın G }. M ∈ MG , v ∈ V : Dac˘a dM (v ) = 1, atunci v se nume¸ste saturat de cuplajul M. S(M): mult¸imea vˆırfurilor saturate de cuplajul M ˆın graful G . Dac˘a dM (v ) = 0, atunci v se nume¸ste expus fat¸˘a de cuplajul M. E(M): mult¸imea vˆırfurilor expuse fat¸˘ a de cuplajul M. Problema ”cuplajului maxim”: P1 Dat G = (V , E ) un graf, s˘a se determine M ∗ ∈ MG astfel ˆıncˆıt |M ∗ | = max{|M| | M ∈ MG }. Vom nota ν(G ) = max{|M| | M ∈ MG }. 3/9

Cuplaje Problema cuplajului maxim Definit¸ie. Se nume¸ste acoperire (a vˆırfurilor cu muchii) ˆın graful G orice mult¸ime F ⊆ E de muchii cu proprietatea c˘a dF (v ) ≥ 1 ∀v ∈ V . FG = {F | F ⊆ E , F acoperire ˆın G } noteaz˘a familia acoperirilor grafului G . FG 6= ∅ ⇔ G nu are vˆırfuri izolate (atunci, m˘acar E este o acoperire). Problema acoperirii minime este: P2 Dat G = (V , E ) un graf, s˘a se determine F ∗ ∈ FG astfel ˆıncˆıt |F ∗ | = min{|F | | F ∈ FG }. Teorema 1. (Norman-Rabin 1959)Fie G = (V , E ) un graf f˘ar˘a vˆırfuri izolate, de ordin n. Dac˘a M ∗ este un cuplaj de cardinal maxim ˆın G , iar F ∗ o acoperire de cardinal minim ˆın G , atunci |M ∗ | + |F ∗ | = n. Dem. P1 echivalent˘a polinomial cu P2 4/9

Cuplaje Grafuri bipartite Teorem˘ a. (Hall, 1935) Fie G = (R, S; E ) un graf bipartit. Exist˘a un cuplaj care satureaz˘a vˆarfurile lui R dac˘a ¸si numai dac˘a |NG (A)| ≥ |A|

∀A ⊆ R.

Teorem˘ a. (Konig,1930) Fie G = (R, S; E ) un graf bipartit. Cardinalul maxim al unui cuplaj este egal cu num˘arul minim de vˆarfuri prin ˆındep˘artarea c˘arora se obt¸ine graful nul: ν(G ) = n − α(G )

5/9

Cuplaje Cuplaje perfecte Un cuplaj M ˆın graful G astfel ˆıncˆat S(M) = V (G ) se nume¸ste cuplaj perfect sau 1-factor. Pentru un graf oarecare H not˘am cu q(H) num˘arul componentelor conexe de ordin impar ale lui H. Teorem˘ a. (Tutte, 1947) Un graf G = (V , E ) are un cuplaj perfect dac˘a ¸si numai dac˘a (T )

q(G − S) ≤ |S|

∀S ⊆ V .

Berge (1958) a generalizat aceast˘a teorem˘a stabilind c˘a 1 ν(G ) = (|V (G )| − maxS⊆V (G ) [q(G − S) − |S|] ). 2 6/9

Cuplaje Problema cuplajului maxim Fie G = (V , E ) un graf ¸si M ∈ MG un cuplaj al s˘au. Definit¸ie: Se nume¸ste drum alternat al lui G relativ la cuplajul M orice drum P : v0 , v0 v1 , v1 , . . . , vk−1 , vk−1 vk , vk a. ˆı. ∀i = 1, k − 1 {vi−1 vi , vi vi+1 } ∩ M 6= ∅. Vom desemna prin P mult¸imea muchiilor drumului P. Definit¸ie: Se nume¸ste drum de cre¸stere al lui G relativ la cuplajul M un drum alternat cu extremit˘a¸tile vˆırfuri distincte, expuse relativ la cuplajul M. Teorem˘ a.(Berge 1959) Un cuplaj M este de cardinal maxim ˆın graful G dac˘a ¸si numai dac˘a nu exist˘a ˆın G drumuri de cre¸stere relativ la M. Strategie de construire a unui cuplaj de cardinal maxim: a) fie M un cuplaj oarecare a lui G (eventual M = ∅); b) while ∃P drum de cre¸stere relativ la M do M ← M∆P 7/9

Cuplaje Problema cuplajului maxim Hopcroft, Karp (1973) 0. 1.

M ← ∅; repeat Determin˘a P o familie maximal˘a (⊆) de drumuri minime de cre¸stere; for P ∈ P do M ← M∆P until P = ∅.

√ Complexitatea O( nA) unde A este timpul g˘asirii familiei P. Hopcroft ¸si Karp au ar˘atat cum se poate implementa pasul 1 pentru un graf bipartit, astfel ˆıncˆıt A = O(m + n): ⇒ algoritm O(mn1/2 ) pentru aflarea unui cuplaj de cardinal maxim ˆıntr-un graf bipartit. Pentru un graf oarecare, structurile de date necesare obt¸inerii aceleea¸si complexit˘a¸ti sˆınt mult mai elaborate ¸si au fost descrise de Micali ¸si Vazirani 1980. 8/9

Problemele pentru seminarul 7

Se vor discuta (cel put¸in) patru probleme dintre cele date la tema 1 ¸si la seminarul 6 (nediscutate s˘apt˘amˆana trecut˘a.)

9/9

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 9 C. Croitoru [email protected] FII

November 26, 2012

1 / 16

OUTLINE

1

Fluxuri (ag 12-13 allinone.pdf pag. 212 −→ . . . )

2

Problemele pentru seminarul 9

3

Prezentarea temei pentru acas˘ a

2 / 16

Fluxuri Problema fluxului maxim Numim ret¸ea (de transport) cu intrarea s ¸si ie¸sirea t, 4-uplul R = (G, s, t, c) unde: - G = (V , E ) este un digraf, - s, t ∈ V ; s 6= t; dG+ (s) > 0; dG− (t) > 0, - c : E → R+ ; c(e) este capacitatea arcului e. (n ∈ N∗ ) ¸si |E(| = m. Extindem funct¸ia c la c(ij) dac˘a ij ∈ E = cij . c : V × V → R+ prin c((i, j)) = 0 dac˘a ij ∈ /E V = {1, 2, . . . , n}

Numim flux ˆın ret¸eaua R = (G , s, t, c) o funct¸ie x : V × V → R, a.ˆı.: 0 ≤ xij ≤ cij

(i) (ii)

X j∈V

xji −

X

∀ij ∈ V × V

xij = 0 ∀i ∈ V − {s, t}.

j∈V

Dac˘ a ij ∈ E atunci xij se nume¸ste fluxul (transportat)pe arcul ij. Evident, condit¸ia (i) cere ca fluxul pe orice arc s˘ a fie nenegativ ¸si subcapacitar, iar condit¸ia (ii) (legea de conservare a fluxului) cere ca suma fluxurilor pe arcele care intr˘ a ˆın vˆırful i s˘ a fie egal˘ a cu suma fluxurilor pe arcele care ies din vˆırful i. 3 / 16

Fluxuri Problema fluxului maxim Definit¸ie: Dac˘a x este un flux ˆın ret¸eaua R = (G , s, t, c), se nume¸ste valoarea fluxului x num˘arul X X v (x) = xjt − xtj . j∈V

j∈V

v (x) este fluxul net care ajunge ˆın ie¸sirea ret¸elei ¸si este egal cu fluxul net care iese din intrarea ret¸elei. Problema fluxului maxim: Dat˘a R = (G , s, t, c) o ret¸ea, s˘a se determine un flux de valoare maxim˘a.

4 / 16

Fluxuri Problema fluxului maxim Definit¸ie. Dac˘a P este un drum ˆın G , multigraful suport al digrafului G , ¸si e = vi vj este o muchie a lui P atunci: dac˘a e corespunde arcului vi vj al lui G , e se nume¸ste arc direct al drumului P; dac˘a e corespunde arcului vj vi al lui G , atunci e se nume¸ste arc invers. Definit¸ie. Fie R = (G , s, t, c) ¸si x flux ˆın R. Se nume¸ste C-drum (ˆın R relativ la fluxul x) un drum D ˆın G cu proprietatea c˘a ∀ij ∈ E (D) : xij < cij dac˘a ij este arc direct, xji > 0 dac˘a ij este arc invers. Dac˘a D este un C-drum ¸si ij ∈ E (D), a a lui ij ( capacitatea rezidual˘ cij − xij dac˘a ij arc direct ˆın D (relativ la C-drumul D) este r (ij) = xji dac˘a ij arc invers ˆın D . Capacitatea rezidual˘ a a drumului D este r (D) = mine∈E (D) r (e). Definit¸ie. Se nume¸ste drum de cre¸stere a fluxului x, ˆın ret¸eaua R = (G , s, t, c), un C-drum de la s la t. 5 / 16

Fluxuri Problema fluxului maxim Lema 1. Dac˘a D este un drumNde cre¸stere a fluxului x ˆın ret¸eaua R = (G , s, t, c), atunci x 1 = x r (D) definit prin   / E (D) dac˘a ij ∈ xij 1 xij = xij + r (D) dac˘a ij ∈ E (D), ij arc direct ˆın D   xij − r (D) dac˘a ji ∈ E (D), ji arc invers ˆın D este flux ˆın R ¸si v (x 1 ) = v (x) + r (D). Observ˘ am c˘ a dac˘ a x admite un drum de cre¸stere atunci x nu este flux de valoare maxim˘ a. Definit¸ie. Se nume¸ste sect¸iune ˆın ret¸eaua R = (G , s, t, c), o partit¸ie (S, T ) a lui V cu s ∈ S ¸si t ∈ T . Capacitatea sect¸iunii (S, T ) este XX c(S, T ) = cij i∈S j∈T

(suma capacit˘a¸tilor arcelor de la S la T ). 6 / 16

Fluxuri Problema fluxului maxim Lema 2. Daca x este un flux ˆın R = (G , s, t, c) ¸si (S, T ) este o sect¸iune a ret¸elei, atunci XX v (x) = (xij − xji ). i∈S j∈T

(valoarea fluxului este egal˘a cu fluxul net ce trece prin orice sect¸iune.) Teorema 1. (Teorema drumului de cre¸stere) Un flux x este de valoare maxim˘a ˆıntr-o ret¸ea R, dac˘a ¸si numai dac˘a, nu exist˘a drumuri de cre¸stere a fluxului x ˆın ret¸eaua R. Teorema 2. (Teorema fluxului intreg) Dac˘a toate capacit˘a¸tile sˆınt ˆıntregi, atunci exist˘a un flux de valoare maxim˘a cu toate componentele ˆıntregi (flux ˆıntreg de valoare maxim˘a). Teorema 3. ( Ford-Fulkerson, 1956) Valoarea maxim˘a a unui flux ˆın ret¸eaua R = (G , s, t, c) este egal˘a cu capacitatea minim˘a a unei sect¸iuni a ret¸elei. 7 / 16

Fluxuri Problema fluxului maxim Algoritmul lui Ford ¸si Fulkerson pentru aflarea unui flux de valoare maxim˘ a Se va folosi un procedeu de etichetare a vˆırfurilor ret¸elei, ˆın vederea depist˘arii drumurilor de cre¸stere a fluxului curent x. Dac˘a nu exist˘a drumuri de cre¸stere, fluxul va fi de valoare maxim˘a. Eticheta atribuit˘ a unui vˆırf j ∈ V are trei componente (e1 , e2 , e3 ) unde e1 ∈ V ∪ {0} ; e2 ∈ {direct, invers} ; e3 ∈ R+ ¸si au urmatoarea semnificat¸ie: - dac˘ a e2 = direct ¸si e1 = i atunci ∃ un C-drum P de la s la j cu ultimul arc ij, arc direct ¸si r (P) = e3 ; - dac˘ a e2 = invers ¸si e1 = i atunci ∃ un C-drum P de la s la j cu ultimul arc ij, arc invers ¸si r (P) = e3 . Init¸ial, se eticheteaz˘ a sursa s cu eticheta (0, ., ∞). Celelalte vˆırfuri primesc etichet˘ a prin ”cercetarea” vˆırfurilor deja etichetate: Dac˘ a i este un vˆırf etichetat, atunci ∀j ∈ V Dac˘ a j neetichetat, ij ∈ E ¸si xij < cij atunci

se eticheteaz˘a e = (i, direct, min(e3 [i], cij − xij ));

j Dac˘ a j neetichetat, ji ∈ E ¸si xji > 0 atunci j

se eticheteaz˘a e = (i, invers, min(e3 [i], xji )).

8 / 16

Fluxuri Algoritmul lui Ford ¸si Fulkerson 1: Se alege x = (xij ) flux init¸ial (de ex. fluxul nul); Se eticheteaz˘a s cu (0, ., ∞) 2: while (∃ vˆırfuri etichetate necercetate) do { ”alege” un vˆırf etichetat ¸si necercetat i; etichetare(i); if (t a primit etichet˘a) then { modific˘a fluxul pe drumul dat de etichete; ¸sterge toate etichetele; eticheteaz˘a s cu (0, ., ∞) } } 3: S ← {i|i ∈ V , i are etichet˘ a} T ←V −S x este flux de valoare maxim˘ a (S, T ) este sect¸iune de capacitate minim˘ a. Algoritmul are complexitatea O(mv ), unde v este valoarea fluxului maxim iar m = |E |.

9 / 16

Fluxuri Modificarea lui Edmonds & Karp a alg. lui Ford & Fulkerson Numim drum minim de cre¸stere a fluxului x ˆın ret¸eaua R, un drum de cre¸stere de lungime minim˘ a printre toate drumurile de cre¸stere. Fie x un flux oarecare ˆın ret¸eaua R. Definim ¸sirul de fluxuri x k ˆın R astfel: x 0 ← x; N x k ← x k−1 r (Pk−1 ), Pk este drum minim de cre¸stere relativ la x k−1 ; k = 1, 2, . . . Teorema 4. (Edmonds, Karp) Dac˘a x = x 0 este un flux oarecare ˆın ret¸eaua R, atunci ¸sirul de fluxuri x 1 , x 2 , . . . obt¸inut din x 0 prin cre¸steri succesive pe drumuri minime de cre¸stere, are cel mult mn ın cel 2 elemente (ˆ mult mn steri succesive, se obt¸ine un flux care nu admite drumuri de 2 cre¸ cre¸stere). Teorema 5. (Edmonds- Karp 1972)Dac˘a se modific˘a algoritmul lui Ford ¸si Fulkerson cu precizarea alegerii bfs a vˆırfurilor etichetate ˆın vederea cercet˘arii, atunci, fluxul maxim se obt¸ine ˆın timpul O(m2 n) . 10 / 16

Problemele pentru seminarul 9

Se vor discuta (cel put¸in) patru probleme dintre urm˘atoarele: 1 2 3 4 5

Problema 1, Setul 11 Problemele 1,3,4 Setul 10 Problema 1, Setul 11’ Problema 4 Setul 7 Problema 1, Setul 7”

11 / 16

TEMA Problema 1. Fie G = (V , E ) un graf conex cu n vˆarfuri ¸si m muchii. Fiecare muchie e ∈ E are asociat un cost real c(e), iar costurile muchiilor sunt distincte. a) Descriet¸i un algoritm care s˘a decid˘a ˆın timpul O(n + m) dac˘a, pentru o muchie dat˘a e0 ∈ E , exist˘a un arbore part¸ial de cost minim al lui G care s˘a cont¸in˘a muchia e0 . b) Argumentat¸i corectitudinea algoritmului propus. (2+2=4 puncte)

12 / 16

TEMA Problema 2. Pentru graful conex G = (V , E ) cu n vˆarfuri, m muchii ¸si funct¸ia de cost c : E → R, se cunoa¸ste lista muchiilor (cu costurile aferente) ¸si un arbore part¸ial de cost minim T = (V , ET ). Arborele T este reprezentat de vectorul parent cu n componente, ˆın care pentru orice v ∈ V − {s} avem parent[v ] = vˆarful dinaintea lui v de pe unicul drum din T de la vˆarful s la v , iar parent[s] = s (s este un vˆarf oarecare, fixat). Se dore¸ste s˘a se actualizeze lista muchiilor ¸si arborele T la operat¸iile de ad˘augare ¸si de ¸stergere a unei muchii. Se cere s˘a se proiecteze algorimi de complexitate O(n + m) pentru fiecare din aceste operat¸ii (cu justificarea corectitudinii ¸si a complexit˘a¸tii timp). Mai precis, ace¸sti algoritmi au: a) La intrare o muchie e = uv nou˘a ¸si costul ei, iar la ie¸sire noua list˘a de muchii (E ∪ {e}) ¸si vectorul parent reprezentˆand un arbore part¸ial de cost minim ˆın G + e. b) La intrare o muchie e = uv existent˘a ˆın graful G , iar la ie¸sire noua list˘a de muchii (E − {e}) ¸si vectorul parent reprezentˆand un arbore part¸ial de cost minim ˆın G − e (dac˘a acest arbore part¸ial mai exist˘a; altfel se returneaz˘a mesajul c˘a graful nu mai este conex). (2+2 = 4 puncte) 13 / 16

TEMA

Problema 3. Fie T un arbore cu un num˘ar par de vˆarfuri care nu are cuplaj perfect. Demonstrat¸i c˘a exist˘a ˆın T un vˆarf v0 cu proprietatea c˘a stergˆand v0 din arborele T (¸si toate muchiile incidente cu v0 ) se obt¸ine o p˘adure cu m˘acar doi arbori cu un num˘ar impar de vˆarfuri. (2 puncte)

14 / 16

TEMA

Problema 4. Un cuplaj M al unui graf G se nume¸ste cuplaj tare dac˘a subgraful indus ˆın G de mult¸imea vˆarfurilor saturate de M este graful |M|K2 . Proiectat¸i un algoritm de complexitate O(n) pentru g˘asirea unui cuplaj tare de cardinal maxim ˆıntr-un arbore cu n vˆarfuri. Argumentat¸i corectitudinea acestui algoritm. (2+2= 4 puncte)

15 / 16

TEMA Solut¸iile se primesc miercuri 5 decembrie ˆıntre orele 12 ¸si 14, la cabinetul C-402

Preciz˘ ari Este ˆıncurajat˘a asocierea ˆın echipe formate din 2 student¸i care s˘a realizeze ˆın comun tema. Depistarea unor solut¸ii copiate ˆıntre echipe diferite conduce la anularea punctajelor tuturor acestor echipe. Nu e nevoie s˘a se rescrie enunt¸ul problemelor. Nu uitat¸i s˘a trecet¸i numele ¸si grupele din care fac parte membrii echipei la ˆınceputul lucrarii. Este ˆıncurajat˘a redactarea latex a solut¸iilor. Nu se primesc solut¸ii prin e-mail. 16 / 16

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 10 C. Croitoru [email protected] FII

December 3, 2012

1 / 13

OUTLINE

1

Fluxuri (ag 12-13 allinone.pdf pag. 239 −→ . . . )

2

Problemele pentru seminarul 10

2 / 13

Problema fluxului maxim Algoritmi de tip preflux Se nume¸ste preflux ˆın ret¸eaua R, o funct¸ie x : E → R astfel ˆıncˆıt (i) (ii)

0 ≤ xij ≤ cij ∀i 6= s ei =

X j:ji∈E

∀ij ∈ E

xji −

X

xij ≥ 0.

j:ij∈E

Num˘arul ei i ∈ V − {s, t} se nume¸ste excesul din vˆırful i. Dac˘a i ∈ V − {s, t} ¸si ei > 0 atunci i se nume¸ste nod activ. Dac˘a ij ∈ E xij va fi numit fluxul pe arcul ij. Dac˘a ˆın ret¸eaua R nu exist˘a noduri active, atunci prefluxul x este flux de la s la t ˆın R de valoare et . Ideea algoritmulor de tip preflux: se porne¸ste cu un preflux ˆın R ¸si se transform˘ a prin modific˘ari ale fluxului pe arce ˆıntr-un flux care nu admite drumuri de cre¸stere. Reprezentarea digrafului G cu ajutorul listelor de adiacent¸˘a. Totu¸si, vom considera c˘ a dac˘ a ij ∈ E atunci ¸si ji ∈ E (altminteri, ad˘ aug˘ am arcul ji cu capacitate 0). 3 / 13

Problema fluxului maxim Algoritmi de tip preflux x preflux ˆın R, ij ∈ E . Capacitatea rezidual˘ a a arcului ij este rij = cij − xij + xji (reprezentˆınd fluxul adit¸ional ce poate fi ”trimis” de la nodul i la nodul j utilizˆınd arcele ij ¸si ji). A ”trimite” flux de la i la j ˆınseamn˘a s˘a cre¸stem fluxul pe arcul ij sau s˘a mic¸sor˘am fluxul pe arcul ji. Se nume¸ste C-drum ˆın R relativ la prefluxul x, un drum al lui G ale c˘arui arce au capacitatea rezidual˘a pozitiv˘a. Se nume¸ste funct¸ie de distant¸˘a ˆın R relativ la prefluxul x, o funct¸ie d : V → Z+ care satisface (D1) d(t) = 0 (D2)

∀ij ∈ E , rij > 0 ⇒ d(i) ≤ d(j) + 1

P C-drum relativ la prefluxul x ˆın R de la i la t ⇒ d(i) ≤ lg(P) (arcele lui P au capacitate rezidual˘a pozitiv˘a ¸si se aplic˘a (D2)). Rezult˘a c˘a d(i) ≤ τi (lungimea minim˘a a unui C-drum de la i la t).

4 / 13

Problema fluxului maxim Algoritmi de tip preflux Fie x un preflux ˆın R ¸si d o funct¸ie de distant¸˘a relativ la x. Un arc ij ∈ E se nume¸ste admisibil dac˘a rij > 0

∧

d(i) = d(j) + 1.

Dac˘a R este o ret¸ea, consider˘am init¸ializare procedura care construie¸ste ˆın O(m) un preflux x ¸si o funct¸ie de distant¸˘a d corespunz˘atoare acestuia: procedure init¸ializare; for ∀ij ∈ E do if i = s then xsj ← csj else xij ← 0; d[s] ← n; d[t] ← 0; for ∀i ∈ V − {s, t} do d[i] ← 1 Alegerea lui d(s) = n are interpretarea:”nu exist˘ a C-drum de la s la t ˆın R relativ la x” (altfel, ar trebui ca lungimea acestuia s˘a fie ≥ n). Dac˘a, ˆın algoritmii de tip preflux vom p˘astra acest invariant, atunci cˆınd x va deveni flux, va rezulta c˘a nu admite drumuri de cre¸stere ¸si deci x va fi de valoare maxim˘a. 5 / 13

Problema fluxului maxim Algoritmi de tip preflux procedure pompeaz˘a (i); // i este un vˆarf diferit de s, t alege ij ∈ A(i) ij admisibil; ”trimite” δ = min(ei , rij ) unit˘a¸ti de flux de la i la j Dac˘a δ = rij avem o pompare saturat˘ a, altfel pomparea e nesaturat˘ a. procedure reetichetare (i); // i este un vˆarf diferit de s, t d(i) ← min{d(j) + 1 | ij ∈ A(i) ∧ rij > 0} Schema general˘ a a unui algoritm de tip preflux este: init¸ializare; while ∃ noduri active ˆın R do { selecteaz˘a un nod activ i; if ∃ arce admisibile ˆın A(i) then pompeaz˘a(i) else reetichetare(i) } 6 / 13

Problema fluxului maxim Algoritmi de tip preflux Lem˘ a Algoritmul de tip preflux, de mai sus, are ca invariant ”d este funct¸ie de distant¸˘ a relativ la prefluxul x”. La fiecare apel al lui reetichetare(i), d(i) cre¸ste strict. Lem˘ a Dac˘a pe parcursul algoritmului, i0 este un nod activ, atunci exist˘a un C-drum de la i0 la s, ˆın R, relativ la prefluxul curent x. Corolar 1. ∀i ∈ V d(i) < 2n. Corolar 2. Num˘arul total de apeluri ale procedurii reetichetare este mai mic decˆıt 2n2 . Corolar 3. Nr. total de pomp˘ari saturate este ≤ nm. Lem˘ a (Goldberg ¸si Tarjan 1986) Num˘arul pomp˘arilor nesaturate este cel mult 2n2 m. Lem˘ a La terminarea algoritmului x este flux de valoare maxim˘a. 7 / 13

Problema fluxului maxim Algoritmi de tip preflux Algoritmul lui Ahuja ¸si Orlin (1988) – cu o metod˘a de scalare, va m˘argini num˘arul pomp˘arilor nesaturate de la O(n2 m) la O(n2 log U). Capacit˘a¸tile sunt ˆıntregi, maxij∈E (1 + cij ) = U. Fie d log2 Ue = K . Ideia algoritmului: Se vor executa K + 1 etape. Pentru fiecare etap˘a p, cu p luˆınd succesiv valorile K , K − 1, . . . , 1, 0 vor fi ˆındeplinite urm˘atoarele condit¸ii: (a) - la ˆınceputul etapei p, ∀ i satisface ei ≤ 2p (b) - ˆın timpul etapei p se utilizeaz˘a procedurile pompare-etichetare ˆın vederea elimin˘arii nodurilor active cu ei ∈ (2p−1 , 2p ]. Din alegerea lui K , ˆın etapa init¸ial˘a (p = K ) condit¸ia (a) este satisf˘acut˘a ¸si deci, dac˘a (b) va fi invariant al algoritmului, dup˘a K + 1 etape, excesele nodurilor vor fi ≤ 12 . Dac˘a, toate transform˘arile datelor vor p˘astra integritatea exceselor, va rezulta c˘a excesul oric˘arui nod este 0, ¸si, deci, dispunem de un flux de valoare maxim˘a (datorit˘a propriet˘a¸tilor funct¸iei distant¸˘a d(i)). 8 / 13

Problema fluxului maxim Algoritmul Ahuja-Orlin init¸ializare; K ← dlog2 (U)e ; ∆ ← 2K +1 ; for p = K , K − 1, . . . , 0 do { construie¸ste L(p); ∆ ← ∆2 while L(p) 6= ∅ do { fie i primul element din L(p); parcurge lista A(i) din locul curent pˆın˘a se determin˘a un arc admisibil sau se depisteaz˘a sfˆır¸situl ei; if ij este arcul admisibil g˘asit then { δ ← min(ei , rij , ∆ − ej ); ei ← ei − δ; ej ← ej + δ; ”trimite” δ unit˘a¸ti de flux de la i la j; if ei ≤ ∆2 then ¸sterge i din L(p); if ej > ∆2 then adaug˘a j ca prim nod ˆın L(p) } else // s-a depistat sfˆır¸situl listei { ¸sterge i din L(p); parcurge toat˘a lista A(i) pentru calculul lui d(i) = min{d(j) + 1; ij ∈ A(i) ∧ rij > 0}; introdu i ˆın L(p); pune pointerul curent al listei A(i) la ˆınceput } }

9 / 13

Problema fluxului maxim

Algoritmul Ahuja-Orlin Lem˘ a. Num˘arul pomp˘arilor nesaturate este cel mult 8n2 ˆın fiecare etap˘a a scal˘arii, deci O(n2 log U) ˆın total.

Teorem˘ a. (Ahuja-Orlin 1988) Algoritmul de tip preflux cu scalarea exceselor are complexitatea O(nm + n2 log U).

10 / 13

Aplicat¸ii combinatorii Aflarea cuplajului maxim ¸si a stabilei maxime ˆıntr-un graf bipartit. V 2

V 1 ++

1 1

++ 1

s

++

1 1

++

1 t

1 1 1

1 ++

Dac˘a x = (xij ) este un flux cu componente ˆıntregi ˆın R atunci se observ˘a c˘a mult¸imea de arce {ij | i ∈ V1 , j ∈ V2 ∧ xij = 1} induce ˆın graful G bipartit un cuplaj M(x). ˆIn plus, v (x) este cardinalul cuplajului M(x). Reciproc, orice cuplaj din G induce o mult¸ime de arce neadiacente ˆın G1 ; dac˘a pe fiecare astfel de arc ij (i ∈ V1 , j ∈ V2 ) se consider˘a fluxul xij egal cu 1 ¸si de asemenea xsi = xjt = 1, ¸si luˆınd fluxul x = 0 pe orice alt arc, atunci fluxul construit are valoarea |M|. Rezolvˆınd problema fluxului maxim pe ret¸eaua R se determin˘a (pornind de la fluxul nul) ˆın O(nm + n2 log n) un cuplaj de cardinal maxim ˆın graful bipartit G . 11 / 13

Aplicat¸ii combinatorii Aflarea cuplajului maxim ¸si a stabilei maxime ˆıntr-un graf bipartit. Fie (S, T ) sect¸iunea de capacitate minim˘a ce se obt¸ine ˆın O(m), din fluxul maxim aflat. Avem, c(S, T ) = ν(G ) (max-flow min-cut). V V 1

2

T

++ 1 1

++ 1

s

++

1 1

++

1 t

1 1 1

1 ++ S

Cum ν(G ) < ∞, rezult˘a c˘a punˆınd Si = S ∩ Vi ¸si Ti = T ∩ Vi (i = 1, 2), avem: |T1 | + |S2 | = ν(G ), iar X = S1 ∪ T2 este mult¸ime stabil˘ a ˆın graful G (pentru a avea c(S, T ) < ∞). ˆIn plus, |X | = |V1 − T1 | + |V2 − S2 | = n − ν(G ). Rezult˘a c˘a X este stabil˘a de cardinal maxim, ˆıntrucˆıt n − ν(G ) = α(G ) (teorema lui K¨ onig). 12 / 13

Problemele pentru seminarul 10

Se vor discuta (cel put¸in) patru probleme dintre urm˘atoarele: 1 2 3 4 5

Problemele 4,2 Setul 11 Problemele 1,4 Setul 16 Problema 2, Setul 15 Problema 2 Setul 18 Problema 1, Setul 19

13 / 13

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 11 C. Croitoru [email protected] FII

December 10, 2012

1 / 13

OUTLINE

1

Fluxuri (ag 12-13 allinone.pdf pag. 260 −→ 280 )

2

Problemele pentru seminarul 11

2 / 13

Aplicat¸ii combinatorii ale fluxurilor Recunoa¸sterea secvent¸elor digrafice. Date (di+ )i=1,n ¸si (di− )i=1,n , exist˘ a un digraf G cu n vˆırfuri astfel ˆıncˆıt G = ({1, . . . , n}, E ) ¸si dG+ (i) = di+ ¸si dG− (i) = di− ∀i = 1, n ? + Dac˘ ≤ n − 1 ¸si 0 ≤ di− ≤ n − 1 ∀i = 1, n ¸si P a 0 ≤+di P − − + i=1,n di = i=1,n di = m (unde, m = |E |, iar di , di ∈ Z), construim ret¸eaua bipartit˘a: 1 + d1

1’

2

2’

1

d1

d2

+ d2

t

1

s

1 dn+

dn

1 n

n’

R˘aspunsul este da dac˘a ¸si numai dac˘a ˆın aceast˘a ret¸ea, exist˘a un flux ˆıntreg de valoare maxim˘a m. 3 / 13

Aplicat¸ii combinatorii ale fluxurilor Determinarea num˘arului de muchie-conexiune al unui graf. Fie G = (V , E ) un graf. Pentru s, t ∈ V , s 6= t, definim: -pe (s, t) = nr. maxim de drumuri cu muchii disjuncte ce unesc s ¸si t. -ce (s, t) = cardinalul minim al unei mult¸imi de muchii, prin ˆındep˘artarea c˘areia din graf, ˆıntre s ¸si t nu mai exist˘a drumuri. Construim din G digraful G1 , ˆınlocuind fiecare muchie cu o pereche de arce simetrice. Consider˘am c : E (G1 ) → Z+ , c(e) = 1, ∀e ∈ E (G1 ). Fie x 0 un flux ˆıntreg de valoare maxim˘a ˆın R = (G1 , s, t, c). t

t

s s Fluxul pe arcele groase este 1, pe cele subtiri 0.

Rezult˘a c˘a v (x 0 ) = pe (s, t). Dac˘a (S, T ) e sect¸iune de capacitate minim˘a, avem c(S, T ) = v (x 0 ) = ce (s, t). Corolar G conex: λ(G ) = min ce (s, t). s,t∈V (G ) s6=t

(∗) 4 / 13

Aplicat¸ii combinatorii ale fluxurilor

Determinarea num˘arului de muchie-conexiune al unui graf. Pentru a afla λ(G ) ar trebui s˘a rezolv˘am cele flux din (∗).

n(n−1) 2

probleme de

Dac˘a fix˘am un vˆırf s0 ¸si rezolv˘am n − 1 probleme de flux cu t ∈ V − s0 se va obt¸ine ˆın mod necesar o pereche s0 , t0 pentru care c(s0 , t0 ) = λ(G ). Rezult˘a: ˆın O(n· (nm + n2 c)) = O(n2 m) se pot determina λ(G ) ¸si o mult¸ime separatoare de muchii de cardinal minim ˆın G .

5 / 13

Aplicat¸ii combinatorii ale fluxurilor Determinarea num˘arului de conexiune al unui graf. G = (V , E ) este un graf ¸si s, t ∈ V , s 6= t, st ∈ /E -p(s, t) = num˘arul maxim de st−drumuri cu mult¸imile de vˆırfuri disjuncte (cu except¸ia extremit˘a¸tilor), -c(s, t) = cardinalul minim al unei mult¸imi de vˆırfuri st− separatoare, Teorema lui Menger ⇒ p(s, t) = c(s, t) (∗) Num˘arul de conexiune k(G ) al grafului G este  dac˘a G = Kn n − 1 k(G ) = min c(s, t) dac˘a G = 6 Kn   s,t∈V

(∗∗)

st ∈E /

Fie G1 = (V (G1 ), E (G1 )) digraful construit din G astfel: -∀v ∈ V consider˘am av , bv ∈ V (G1 ) ¸si av bv ∈ E (G1 ); - ∀vw ∈ E consider˘am bv aw , bw av ∈ E (G1 ). Definim c : E (G1 ) → Z+ prin ( 1 dac˘a e = av bv c(e) = ∞ altfel. 6 / 13

Aplicat¸ii combinatorii ale fluxurilor Determinarea num˘arului de conexiune al unui graf. Consider˘am ret¸eaua R = (G1 , bs , at , c). Exemplu: b1 1

t

s

2

a t

a1

bt

S a s

a2 bs

b2

Arcele groase au capacitate infinit, cele subtiri 1.

x 0 flux ˆıntreg de la bs la at ˆın R de valoare maxim˘a ⇒ v(x0 ) = p(s, t). (S, T ) o sect¸iune ˆın R a.ˆı. v (x 0 ) = c(S, T ). ⇒ c(s, t) = |A0 | = c(S, T ) = v (x0 ) = p(s, t), unde A0 este o mult¸ime de vˆırfuri st− separatoare de cardinal minim. Pentru a determina k(G ) determin˘am minimul din (**) prin rezolvarea a |E (G )| probleme de flux. Se poate construi un algoritm de complexitate O(m(nm + n2 log n)). 7 / 13

Fluxuri Flux de cost minim. Fie R = (G , s, t, c) o ret¸ea ¸si x un flux de la s la t ˆın R. Consider˘am a : E → R o funct¸ie de cost care asociaz˘a fiec˘arui arc ij ∈ E a(ij) = aij costul (transportului unei unit˘a¸ti de flux) pe arcul ij. Costul fluxului x se define¸ste ca fiind X aij xij . a(x) = i,j

Problema fluxului de cost minim Dat˘a R o ret¸ea, v ∈ R+ ¸si a : E → R funct¸ie de cost, s˘a se determine x 0 flux ˆın R astfel ˆıncˆıt a(x 0 ) = min{a(x) | x flux ˆın R, v (x) = v }. Problema simpl˘a a atribuirii Se dispune de n lucr˘atori ¸si n lucr˘ari. Costul atribuirii lucr˘atorului i la lucrarea j este aij (i, j ∈ {1, . . . , n}). S˘ a se atribuie fiecare dintre cele n lucr˘ ari la cˆıte un lucr˘ ator, astfel ˆıncˆıt costul total al atribuirii s˘ a fie minim. 8 / 13

Flux de cost minim Problema atribuirii. 1,a 11 1

1

1,0

1,0 2 1,0 s

1,0

2 1,a ij

1,0

j

1,0

t

i 1,0

1,0 n

1,a n1

n

Un flux ˆıntreg de valoare n ¸si de cost minim, ofer˘a solut¸ia problemei atribuirii. Problema simpl˘a a transporturilor (Hitchcock-Koopmans): O marf˘a disponibil˘a ˆın depozitele D1 , . . . , Dn ˆın cantit˘a¸tile d1 , . . . , dn este solicitat˘a ˆın centrele de consum C1 , C2 , . . . , Cm ˆın cantit˘a¸tile c1 , c2 , . . . , cm . Se cunoa¸ste costul aij al transportului unei unit˘a¸ti de marf˘a de la depozitul Di la centrul de consum Cj (∀i ∈ {1, . . . , n}, ∀j ∈ {1, . . . , m}). Se cere s˘ a se stabileasc˘ a un plan de transport care s˘ a satisfac˘ a toate cererile ¸si s˘ a aib˘ a costul total minim

9 / 13

Flux de cost minim Problema transporturilor P P Dac˘aP i=1,n di ≥ j=1,m cj , un flux de cost minim ¸si de valoare v = i=1,m ci ˆın ret¸eaua urm˘atoare, rezolv˘a problema. oo ,a 11 C1

D1 d1, 0

C2

d2, 0

D2

d i, 0

Di

s

o o ,a ij

Cj

d n, 0 Dn

c ,0 1 c ,0 2 c j, 0

t

c ,0 m o o ,a n1

Cm

Definit¸ie. Fie x un flux ˆın R = (G , s, t, c) ¸si a : E → R o funct¸ie de cost. P C-drum ˆın R relativ la fluxul x, ⇒ costul drumului P este X X a(P) = aij − aji . ij

ij∈P direct

ij

ij∈P invers

Dac˘a C este un C-drum ˆınchis, a(C ) se calculeaz˘a dup˘a aceea¸si formul˘a, dup˘a stabilirea unui sens de parcurgere a lui C . 10 / 13

Flux de cost minim Solut¸ia problemei fluxului de cost minim. N Dac˘a P este drum de cre¸stere relativ la fluxul x, atunci x 1 = x r (P) este un flux de valoare v (x 1 ) = v (x) + r (P) ¸si de cost a(x) + r (P)· a(P). N Dac˘a C este un C-drum ˆınchis relativ la x, atunci x 1 = x r (C ) este un flux de valoare v (x 1 ) = v (x) ¸si de cost a(x 1 ) = a(x) + r (C )· a(C ). Dac˘ a a(C ) < 0 atunci x 1 este un flux de aceea¸si valoare ca ¸si x, dar de cost strict mai mic. Teorem˘ a. Un flux de valoare v este de cost minim dac˘a ¸si numai dac˘a nu admite C-drumuri ˆınchise de cost negativ. Teorem˘ a. Dac˘a x este un flux de valoare v ¸si de cost minim iar P0 este un drum de cre¸stere, astfel ˆıncˆıt a(P0N ) = min{a(P) | Pdrum de cre¸stere relativ la x}, atunci x 1 = x r (P0 ) este un flux de valoare v (x 1 ) = v + r (P0 ) ¸si de cost minim.

11 / 13

Flux de cost minim Algoritm generic de rezolvare a problemei fluxului de cost minim. Algoritm generic de rezolvare a problemei fluxului de cost minim 0: Se consider˘a x = (xij ) un flux cu valoarea v 0 ≤ v ; {x poate fi fluxul nul sau un flux y determinat cu ajutorul algoritmului de flux maxim ¸si apoi v considerˆınd x = ( v (y ) y )} 1: while (∃ circuite de pondere < 0 relativ la aij ) do { determin˘a un astfel de circuit; modific˘a fluxul pe acest circuit } 2: while v (x) < v do { aplic˘a un algoritm de drum minim ˆın raport cu ponderile aij pentru depistarea unui C-drumNP de cost minim; x ←x min(r (P), v − v (x)) } Complexitatea pentru pasul 2 este O(n3 v ), dac˘a se pleac˘a de la fluxul nul. Se poate dovedi c˘a pasul 1 se poate implementa astfel ca num˘arul iterat¸iilor s˘a fie O(nm2 logn). 12 / 13

Problemele pentru seminarul 11

Se vor discuta (cel put¸in) patru probleme dintre urm˘atoarele: 1 2 3 4 5

Problema Problema Problema Problema Problema

1 Setul 11” 1 Setul 12 4, Setul 15 3 Setul 11’ 2, Setul 16

13 / 13

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 12 C. Croitoru [email protected] FII

December 17, 2012

1 / 11

OUTLINE

1

Reduceri polinomiale pentru probleme de decizie pe grafuri (ag 12-13 allinone.pdf pag. 281 −→ 320 )

2

Problemele pentru seminarul 12

2 / 11

Reduceri polinomiale Stabila maxim˘a. SM Instant¸˘a : G = (V , E ) graf ¸si k ∈ N. Intrebare: Exist˘a S mult¸ime stabil˘a ˆın G a. ˆı. |S| ≥ k ? Teorem˘ a. (Karp 1972) 3SAT ∝ SM. Exemplu: U = {u1 , u2 , u3 , u4 }; C = (u1 ∨ u3 ∨ u4 ) ∧ (u 1 ∨ u2 ∨ u4 ) ∧ (u2 ∨ u 3 ∨ u4 ); k = 4 + 3 = 7. u1

u1

u

2

u2

3

u3

u 4

a

12

a 21

u4

a 33

a 23

a 13

a 11

u

a 22

a

31

a 32

3 / 11

Reduceri polinomiale Colorarea vˆarfurilor. COL Instant¸˘a: G = (V , E ) graf ¸si p ∈ N∗ . Intrebare: Exist˘a o p-colorare a vˆarfurilor lui G ? v

1

Lem˘ a. Fie H graful: v

2

v

v 4

3

a) Dac˘a c este o 3-colorare a lui H astfel ˆıncˆıt c(v1 ) = c(v2 ) = c(v3 ) = a ∈ {1, 2, 3} atunci c(v4 ) = a. b) Fie c : {v1 , v2 , v3 } → {1, 2, 3} a.ˆı. c({v1 , v2 , v3 }) 6= {a}. Atunci c poate fi extins˘a la o 3-colorare a lui H cu c(v4 ) 6= a. Vom desemna (pentru simplitate) graful H astfel: v

1

v

2

v

h

v 4

4 / 11

Reduceri polinomiale Colorarea vˆarfurilor. Teorem˘ a. 3SAT ∝ COL. Exemplu: U = {u1 , u2 , u3 , u4 } , C = (u 1 ∨ u2 ∨ u3 ) ∧ (u1 ∨ u3 ∨ u 4 ) ∧ (u 2 ∨ u3 ∨ u4 ) Graful G va fi (p = 3): b

u1

u1

u2

h1

a1

u

u

2

h2

3

u3

u

4

u

4

h3

a3

a2

a

5 / 11

Reduceri polinomiale Probleme hamiltoniene. Definit¸ie: Fie G = (V (G ), E (G )) un (di)graf. Un circuit C al lui G se nume¸ste circuit hamiltonian dac˘a V (C ) = V (G ). Un drum deschis D al lui G se nume¸ste drum hamiltonian dac˘a V (D) = V (G ). Un (di)graf care are un circuit hamiltonian se nume¸ste (di)graf hamiltonian.Un (di)graf care are un drum hamiltonian se nume¸ste (di)graf trasabil. Teorem˘ a. (Nash-Williams 1969) Problemele urm˘atoare sˆınt polinomial echivalente: CH : TR : DCH: DTR: BCH:

Dat G Dat G Dat G Dat G Dat G

graf. Este G hamiltonian ? graf. Este G trasabil ? digraf. Este G hamiltonian ? digraf. Este G trasabil ? graf bipartit. Este G hamiltonian ?

6 / 11

Reduceri polinomiale Probleme hamiltoniene. CH ∝ TR

x vo

vo

y z

N (vo) G

N (vo) G

H

G

TR ∝ CH G

G+K1

DCH ∝ CH v

aw

bv w

av

b w

bx

x

ax bb b

a D

a

b

ba G

aa

7 / 11

Reduceri polinomiale Probleme hamiltoniene. Teorem˘ a. (Karp 1972) SM ∝ CH. Pentru orice muchie a grafului G (intrare ˆın SM) asociem graful v

(v,e,1)

(v,e,2)

(v,e,3)

(v,e,4)

(v,e,5)

(v,e,6)

u

(u,e,1)

(u,e,2)

(u,e,3)

(u,e,4)

(u,e,5)

(u,e,6)

e

Singurele posibilit˘a¸ti de traversare de c˘atre un circuit hamiltonian al lui H a vˆırfurilor din Ge0 sˆınt (a) (b) ¸si (c) indicate ˆın figura urm˘atoare: a

b

c

8 / 11

Reduceri polinomiale Probleme hamiltoniene. u

e1 v 1 u (u,e ,1) 1

ep

e

2

vp

v 2 u (u,e ,6) 1

a

Exemplu:

u (u,e ,1) 2

(u,e

u (u,e p,1)

u ,6) 2

a

1

u (u,e p,6)

k

a2

1

3 2 4

1

3

2

4

3 1

a1

2

4

2

4

2

4

9 / 11

Problema comisului voiajor Algoritmi de aproximare. CV Dat n ∈ Z+ (n ≥ 3) ¸si d : E (Kn ) → R+ , s˘a se determine H0 circuit hamiltonian ˆın graful complet Kn cu d(H0 ) minim printre toate circuitele hamiltoniene ale lui Kn . Algoritmi A, care pentru datele unei probleme CV vor oferi ˆın timp polinomial (ˆın raport cu n) un circuit hamiltonian HA , care va aproxima solut¸ia optim˘a H0 . M˘asuri ale eficient¸ei unei astfel de ”euristici” A pot fi considerate numerele: d(HA ) RA (n) = sup d:E (Kn )→R+ d(H0 ) d(H0 )6=0

RA = sup RA (n). n≥3

Teorem˘ a. Dac˘a exist˘a un algoritm aproximativ A cu timp de lucru polinomial pentru CV, astfel ˆıncˆıt RA < ∞, atunci CH se poate rezolva ˆın timp polinomial. P 6= NP ⇒ nu exist˘a algoritm aproximativ A polinomial cu RA < ∞. 10 / 11

Problemele pentru seminarul 12

11 / 11

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 13 C. Croitoru [email protected] FII

January 14, 2013

1 / 14

LA MULT ¸ I ANI!

2 / 14

OUTLINE

1

Abord˘ ari ale unor probleme NP-dificile pe grafuri (ag 12-13 allinone.pdf pag. 325 −→ 353 )

2

Problemele pentru seminarul 13

3

Prezentarea temei pentru acas˘ a

3 / 14

Abord˘ari ale problemelor NP-dificile Colorarea vˆarfurilor unui graf Algoritmul greedy de colorare Fie G = (V , E ), cu V = {1, 2, . . . , n} ¸si π o permutare a lui V . Se construie¸ste colorarea c ce utilizeaz˘a χ(G , π) culori, c : {1, 2, . . . , n} −→ {1, 2, . . . , χ(G , π)}. c(π1 ) ← 1; χ(G , π) ← 1; S1 ← {π1 }; for i ← 2 to n do { j ← 0; repeat j ← j + 1; fie v primul vˆarf (cf. ordon˘arii π), din Sj a. ˆı. πi v ∈ E (G ); if v exist˘a then first(πi , j) ← v else { first(πi , j) ← 0; c(πi ) ← j; Sj ← Sj ∪ {πi } } until first(πi , j) = 0 or j = χ(G , π); if first(πi , j) 6= 0 then { c(πi ) ← j + 1; Sj+1 ← {πi }; χ(G , π) ← j + 1; } } 4 / 14

Abord˘ari ale problemelor NP-dificile Colorarea vˆarfurilor unui graf Algoritmul Dsatur { Degree of Saturation} Acest algoritm ( Br´elaz, 1979 ) este o metod˘a secvent¸ial˘a dinamic˘a de colorare. Ideea este de colora vˆ arfurile pe rˆ and, alegˆ and de fiecare dat˘ a vˆ arful cu un num˘ ar maxim de constrˆ angeri privitoare la culorile disponibile acestuia.Aceast˘ a abordare este ˆıntr-un fel opus˘ a primeia (cea geedy) deoarece se aleg vˆ arfuri care formeaz˘ a “clici” mari ˆın raport cu vˆ arfurile deja alese (spre deosebire de mult¸imi stabile mari ˆın cazul greedy).

Dac˘a G este un graf ¸si c o colorare part¸ial˘a a vˆarfurilor lui G , definim gradul de saturat¸ie al unui vˆarf v , notat dsat (v ), ca fiind num˘arul de culori diferite din vecin˘atatea acestuia. -

ordoneaz˘ a vˆ arfurile ˆın ordinea descresc˘ atoare a gradelor lor; atribuie unui vˆ arf de grad maxim culoarea 1; while exist˘ a vˆ arfuri necolorate do { alege un vf. necol. cu gr. de satur. maxim; dac˘ a acesta nu-i unic, alege un vf. de grad maxim ˆın subgr.necolorat; coloreaz˘ a vˆ arful ales cu cea mai mic˘ a culoare posibil˘ a; }

Algoritmul DSatur garanteaz˘a g˘asirea num˘arului cromatic pentru grafurile bipartite.

5 / 14

Abord˘ari ale problemelor NP-dificile Problema comisului voiajor O euristic˘ a popular˘ a pentru problemele ˆın care funct¸ia de distant¸˘ a satisface inegalitatea triunghiular˘ a, este dat˘ a de Christofides. Spre deosebire de cazul general cˆ and nu se poate spera la o euristic˘ a polinomial˘ a A cu RA finit˘ a, dac˘ a P 6= NP, ˆın acest caz se poate demonstra urm˘ atoarea

Teorem˘ a. ( Christofides,1973) Fie CV cu d satisf˘acˆınd ∀v , w , u ∈ V (Kn ) distincte d(vw ) ≤ d(vu) + d(uw ). Exist˘a un algoritm aproximativ A pentru CV care satisface RA = 23 ¸si are timp de lucru polinomial. 1

Se determin˘a T 0 mult¸imea muchiilor unui arbore part¸ial de cost minim ˆın K n (costul muchiei e fiind d(e) ).Algoritmul lui Prim.

2

Se determin˘a M 0 un cuplaj perfect ˆın subgraful indus de vˆırfurile de grad impar ale arborelui T 0 ¸si de cost minim. Alg. lui Edmonds.

3

Se consider˘a multigraful obt¸inut din < T 0 ∪ M 0 >Kn , prin duplicarea muchiilor din T 0 ∩ M 0 . Exist˘a un parcurs Eulerian ˆınchis, cu vˆırfurile (vi1 , vi2 , . . . , vi1 ). Eliminˆınd aparit¸iile multiple a unui vˆırf, cu except¸ia primului ¸si ultimului, se obt¸ine un circuit hamiltonian HA ˆın Kn cu muchiile HA = (vj1 vj2 , vj2 vj3 , . . . , vjn vj1 ) ( O(n2 ) operat¸ii). 6 / 14

Abord˘ari ale problemelor NP-dificile Metode care imit˘a natura Metaeuristica simulated annealing. Inspirat˘a din termodinamic˘a, inventat˘a independent de Kirkpatrick, ˇ Gelatt ¸si Vechi ˆın 1983 ¸si de Cerny ˆın 1985. Probabilitatea de cre¸stere a energiei scade odat˘a cu temperatura: dE

Pr (E + dE ) = Pr (E ) · e − kT

C˘alirea simulat˘a este o metod˘a computat¸ional˘a care imit˘a modul natural de determinare a unei configurat¸ii care minimizeaz˘a energia unui sistem. Atunci cnd se dore¸ste minimizarea unei funct¸ii f : D → R, vom interpreta domeniul de definit¸ie al funct¸iei, D, ca fiind mult¸imea configurat¸iilor posibile ale sistemului, iar funct¸ia f ca fiind energia acestuia. O variabil˘a fictiv˘a T , asociat˘a procesului de c˘autare, va juca rolul temperaturii iar constanta lui Bolzmann va fi considerat˘a 1. 7 / 14

Abord˘ari ale problemelor NP-dificile Algoritm de c˘alire simulat˘a 1. Plan de c˘ alire: - temperatura init¸ial˘a Tstart ; configurat¸ia init¸ial˘a xstart ∈ D; - temperatura final˘a Tmin ; o funct¸ie de reducere lent˘a a temperaturii decrease (T); - nr. maxim de ˆıncerc˘ari de ˆımbun˘at˘a¸tire a solut¸iei la fiecare prag de temperatur˘a attempts - nr. maxim de schimb˘ari ale solut¸iei la fiecare prag de temperatur˘a changes. 2. T ← Tstart ; xold ← xstart while T > Tmin do { na ← 0; nc ← 0 while na < attempts and nc < changes do { genereaz˘a o solut¸ie nou˘a xnew ; na + +; ∆E ← f (xold ) − f (xnew ); If ∆E < 0 then { xold ← xnew ; nc + +} else { genereaz˘a q ∈ (0, 1) un nr. aleator ∆E if q < e − T then { xold ← xnew ; nc + +} } } decrease(T ) } 3. return xold Pentru problema comisului voiajor, se porne¸ste cu un tur ales aleator, iar solut¸iile vecine se obt¸in cu 2-move. Se √ poate lua Tstart = O( n), attempts = 100n, changes = 10n, decrease(T ) = 0.95T ¸si Tmin = O(1).

8 / 14

Problemele pentru seminarul 13

1 2 3 4 5

Problema Problema Problema Problema Problema

4 Setul 11’ 2 Setul 18 2, Setul 19 3 Setul 19 2, Setul 16

9 / 14

TEMA

Problema 1. Fie G un graf cu proprietatea c˘a nu are circuite impare disjuncte. Demonstrat¸i c˘a G este 5-colorabil. (2 puncte)

10 / 14

TEMA Problema 2. Graful G = (V , E ) cu n vˆarfuri ¸si m muchii modeleaz˘a o ret¸ea de comunicat¸ie bidirect¸ional˘a: ˆın fiecare vˆarf este plasat un utilizator care schimb˘a mesaje cu ceilalt¸i utilizatori folosind muchiile incidente cu vˆarful ˆın care este localizat (un sistem de rutare asociat ret¸elei va asigura ajungerea mesajelor la destinatari). ˆIntr-un vˆarf special s ∈ V se afl˘a un utilizator care trimite spamuri. Pentru fiecare muchie {u, v } ∈ E a grafului se cunoa¸ste costul c({u, v }) al instal˘arii unui filtru care s˘a blocheze orice spam ce s-ar putea transmite pe muchia {u, v } (de la u la v sau de la v la u). Se dore¸ste ca o mult¸ime A ⊆ V − {s} de utilizatori s˘a fie protejat˘a de spamurile trimise de utilizatorul din s. Se cere s˘a se proiecteze un algoritm cu timp de lucru polinomial care s˘a determine o mult¸ime de muchii E 0 ⊆ E pe care s˘a se plaseze filtrele care sa protejeze utilizatorii din A ¸si s˘a aib˘a cost minim (suma costurilor muchiilor din E 0 s˘a fie minim˘a printre toate mult¸imile ce pot proteja A). Justificare. (2+2 = 4 puncte)

11 / 14

TEMA Problema 3. Un nucleu ˆıntr-un digraf G = (V , E ) este o mult¸ime S de vˆarfuri cu proprietatea c˘a S nu cont¸ine vˆarfuri adiacente ¸si pentru orice vˆarf u ∈ V − S exist˘a v ∈ S astfel ˆıncˆat (v , u) ∈ E . Fie problema de decizie: ˘ G = (V , E ) digraf. NUCLEU INSTANT ¸ A: ˆINTREBARE: Are G un nucleu? Demonstrat¸i c˘a urm˘atoarea construct¸ie ofer˘a o reducere polinomial˘a a problemei SAT la problema NUCLEU (SAT ∝ NUCLEU). Dat˘a o instant¸˘a F a lui SAT construim digraful G astfel: - pentru fiecare clauz˘a C a lui F ad˘aug˘am la G un 3-circuit vC1 , (vC1 , vC2 ), vC2 , (vC2 , vC3 ), vC3 , (vC3 , vC1 ), vC1 ; - pentru fiecare variabil˘a x care apare ˆın formula F ad˘aug˘am la G un 2-circuit vx , (vx , vx ), vx , (vx , vx ), vx ; - pentru fiecare pereche (l, C ) unde l este un literal (x sau x) care apare ˆın clauza C ad˘aug˘am la G arcele (vl , vC1 ), (vl , vC2 ), (vl , vC3 ) . (2+2=4 puncte) 12 / 14

TEMA

Problema 4. Fiecare student dintr-o mult¸ime S de n > 0 student¸i opteaz˘a pentru o submult¸ime de 4 cursuri opt¸ionale dintr-o mult¸ime C de k > 4 cursuri opt¸ionale. Se cere s˘a se descrie un algoritm care s˘a determine ˆın timp polinomial o alocare a student¸ilor la cursurile opt¸ionale astfel ˆıncˆat fiecare student s˘a fie alocat la exact 3 cursuri opt¸ionale (din cele patru pentru care a optat) ¸si fiecare curs ¸i (dac˘a o astfel de opt¸ional s˘a aib˘a repartizat cel mult d 3n k e student alocare exist˘a). Justificare. (2+2= 4 puncte)

13 / 14

TEMA Solut¸iile se primesc miercuri 23 ianuarie ˆıntre orele 12 ¸si 14, la cabinetul C-402

Preciz˘ ari Este ˆıncurajat˘a asocierea ˆın echipe formate din 2 student¸i care s˘a realizeze ˆın comun tema. Depistarea unor solut¸ii copiate ˆıntre echipe diferite conduce la anularea punctajelor tuturor acestor echipe. Nu e nevoie s˘a se rescrie enunt¸ul problemelor. Nu uitat¸i s˘a trecet¸i numele ¸si grupele din care fac parte membrii echipei la ˆınceputul lucrarii. Este ˆıncurajat˘a redactarea latex a solut¸iilor. Nu se primesc solut¸ii prin e-mail. 14 / 14

ALGORITMICA GRAFURILOR S˘ apt˘ amˆ ana 14 C. Croitoru [email protected] FII

January 21, 2013

1 / 15

OUTLINE

1

Grafuri planare (ag 12-13 allinone.pdf pag. 354 −→ )

2

Problemele pentru seminariile 14,15

3

Anunt¸uri.

2 / 15

Grafuri planare Propriet˘a¸ti de baz˘a. Definit¸ie. Fie G = (V , E ) un graf ¸si S o suprafat¸˘a ˆın R3 . Spunem c˘a G este reprezentabil pe S dac˘a exist˘a G 0 = (V 0 , E 0 ) un graf astfel ˆıncˆıt: a) G ∼ = G 0. 0 b) V e o mult¸ime de puncte distincte din S. c) Orice muchie e 0 ∈ E 0 este o curb˘a simpl˘a cont¸inut˘a ˆın S care une¸ste cele dou˘a extremit˘a¸ti. d) Orice punct al lui S este sau vˆırf al lui G 0 , sau prin el trece cel mult o muchie a lui G 0 . G 0 se nume¸ste reprezentare a lui G ˆın S. Dac˘a S este un plan atunci G se nume¸ste planar iar G 0 o reprezentare planar˘ a a lui G . Dac˘a S este un plan ¸si G 0 este un graf care satisface b) c) ¸si d) de mai sus atunci G 0 se nume¸ste graf plan. 3 / 15

Grafuri planare Propriet˘a¸ti de baz˘a. Lem˘ a.Un graf este planar dac˘a ¸si numai dac˘a este reprezentabil pe o sfer˘a. proiect¸ia stereografic˘a ! Definit¸ie. Fie G un graf plan. Dac˘a ˆındep˘art˘am punctele lui G (vˆırfurile ¸si muchiile sale) din plan se obt¸ine o reuniune de regiuni conexe (orice dou˘a puncte se pot uni printr-o curb˘a simpl˘a cont¸inut˘a ˆın regiune) ale planului, care se numesc fet¸ele lui G . Orice graf plan are un num˘ar finit de fet¸e, dintre care una singur˘a este nem˘arginit˘a ¸si se nume¸ste fat¸˘ a exterioar˘ a a lui G . 5

6

2 6

f4

f2 5 f4

f3 f5

7

8 3

2 f5

4

2 f4

1

f1

8

4

1

6

1

f3 f1

f1 3 f2

7

8

5 4

f5

f3 7

3 f2

4 / 15

Grafuri planare Propriet˘a¸ti de baz˘a. Lem˘ a.Orice reprezentare planar˘a a unui graf poate fi transformat˘a ˆıntr-o reprezentare diferit˘a astfel ˆıncˆıt o fat¸˘a specificat˘a a sa s˘a devin˘a fat¸a exterioar˘a. Teorem˘ a. (Formula lui Euler) Fie G = (V , E ) un graf plan conex cu n vˆırfuri, m muchii ¸si f fet¸e. Atunci f =m−n+2 Din punct de vedere algoritmic, teorema are drept consecint¸˘ a imediat˘ a faptul c˘ a orice graf planar este ”rar”, num˘ arul muchiilor este de ordinul num˘ arului de vˆırfuri. Va rezulta c˘ a orice traversare ˆın ordinul O(|V | + |E |) a lui G este de fapt ˆın O(|V |) operat¸ii.

Corolar 1. Fie G un graf planar, conex, cu n(≥ 3) vˆırfuri ¸si m > 2 muchii. Atunci m ≤ 3n − 6. Graful K5 nu este planar ! 5 / 15

Grafuri planare Propriet˘a¸ti de baz˘a. Corolar 2. Dac˘a G este un graf bipartit, conex ¸si planar cu m > 2 muchii ¸si n vˆırfuri, atunci m ≤ 2n − 4. Graful K33 nu este planar. Corolar 3. Dac˘a G este un graf planar conex, atunci G are un vˆırf de grad cel mult 5. Fie G = (V , E ) un graf ¸si v ∈ V (G ) astfel ˆıncˆıt dG (v ) = 2 ¸si vw1 , vw2 ∈ E , w1 6= w2 . Fie h(G ) = (V \ {v }, E \ {vw1 , vw2 } ∪ {w1 w2 }). Se observ˘a c˘a G este planar dac˘a ¸si numai dac˘a h(G ) este planar. Vom nota cu h∗ (G ) graful obt¸inut din G aplicˆındu-i repetat transformarea h, pˆın˘a cˆınd graful curent nu mai are vˆırfuri de grad 2. Rezult˘a c˘a G este planar, dac˘a ¸si numai dac˘a h∗ (G ) este planar. Definit¸ie. Dou˘a grafuri G1 ¸si G2 se numesc homeomorfe dac˘a ¸si numai dac˘a h∗ (G1 ) ∼ = h∗ (G2 ). Teorem˘ a. (Kuratowski 1930)Un graf este planar dac˘a ¸si numai dac˘a nu are subgrafuri homeomorfe cu K5 sau K33 .

6 / 15

Grafuri planare Desenarea unui graf planar. Fary 1948 ( independent Wagner ¸si Stein): Orice graf planar are o reprezentare planar˘a cu toate muchiile segmente de dreapt˘a (reprezentarea Fary). Existent¸a unei reprezent˘ari Fary cu vˆırfuri ˆın puncte de coordonate ˆıntregi ¸si, ˆın acela¸si timp, aria suprafet¸ei ocupate de reprezentare s˘a fie polinomial˘a ˆın raport cu num˘arul n de vˆırfuri ale grafului ! Teorem˘ a. (Fraysseix, Pach, Pollack (1988))Orice graf planar cu n vˆırfuri are o reprezentare planar˘a cu vˆırfuri de coordonate ˆıntregi ˆın [0, 2n − 4] × [0, n − 2] ¸si cu muchii segmente de dreapt˘a. Demonstrat¸ia: algoritm de complexitate O(n log n) pentru obt¸inerea acestei reprezent˘ari. Vom demonstra teorema ˆın ipoteza suplimentar˘ a c˘ a G este maximal planar : orice muchie i s-ar ad˘ auga se obt¸ine un graf neplanar (sau multigraf). S˘ a observ˘ am c˘ a orice fat¸˘ a a unui graf maximal planar este un C3 (altminteri ˆın reprezentarea lui G cu fat¸a exterioar˘ a m˘ arginit˘ a de un Cn cu n ≥ 4 se pot introduce muchii f˘ ar˘ a a pierde planaritatea grafului). Ipoteza nu este restrictiv˘ a: de la o reprezentare a lui G ca o hart˘ a planar˘ a (ce se obt¸ine aplicˆınd de exemplu algoritmul de testare a planarit˘ a¸tii) se trece la o hart˘ a cu toate fet¸ele triunghiului prin insert¸ia ˆın timp liniar de corzi ˆın circuite. La desenarea grafului obt¸inut, muchiile fictive introduse nu se vor trasa. 7 / 15

Grafuri planare Grafuri plane - versiunea combinatorial˘a. ˆIn versiunea combinatorial˘a un graf este un triplet G = (E , θ,− ), unde E este o mult¸ime de cardinal par, − este o involut¸ie pe E (permutare de ordin 2) f˘ar˘a puncte fixe, ¸si θ este o permutare pe E . Elementele lui E sunt gˆandite ca arce; o muchie (neorientat˘a) este reprezentat˘a ca o pereche e, e ∈ E de arce, inverse unul altuia. Aplicat¸ia − inverseaz˘a direct¸ia. Se dore¸ste ca aplicat¸ia θ s˘a dea o orientare a muchiilor din jurul unui vˆ arf (ˆın sens contrar acelor de ceasornic). Vˆ arfurile sunt ciclii permut˘arii θ. (Un ciclu al permut˘arii θ este o submult¸ime nevid˘a a lui E ˆınchis˘ a ˆın raport cu θ ¸si minimal˘ a cu aceast˘ a proprietate).

Dac˘a not˘am cu V mult¸imea ciclilor permut˘arii θ atunci definim t : E → V , t(e) = unicul ciclu al lui θ ce cont¸ine e (extremit. init¸ial˘a a lui e) h : E → V , h(e) = unicul ciclu al lui θ ce cont¸ine e (extremit. final˘a a lui e) Se observ˘a c˘a ∀e t(e) = h(e) ¸si h(e) = t(e). Dac˘ a θ ∗ : E → E definit˘ a de θ ∗ (e) = θ(e), atunci o fat¸˘ a a lui G este un ciclu al permut˘ arii θ ∗ . Intuitiv, pentru a calcula θ ∗ (e), invers˘ am e pentru a obt¸ine e ¸si apoi ne rotim (ˆın sensul acelor de ceasornic) ˆın jurul extremit˘ a¸tii init¸iale a lui e.

Num˘arul fet¸elor lui G se noteaz˘a cu f . 8 / 15

Grafuri planare Grafuri plane - versiunea combinatorial˘a. O component˘ a conex˘ a a lui G este o orbit˘a a lui E ˆın grupul de permut˘ari generat de θ ¸si − : o mult¸ime nevid˘ a minimal˘ a cu proprietatea c˘ a este ˆınchis˘ a la θ ¸si − . Fie G un graf cu m = 12 |E | muchii (neorientate), n = |V | vˆarfuri, f fet¸e, ¸si c componente conexe. Caracteristica Euler a lui G se define¸ste ca fiind χ(G ) = 2c + m − n − f . Un graf G se nume¸ste graf plan dac˘a χ(G ) = 0. Se poate demonstra c˘a pentru un graf conex ˆın definit¸ia tradit¸ional˘a, cele dou˘a not¸iuni de grafuri plane coincid (graful neorientat construit a¸sa cum am descris mai sus ata¸sat unui graf ˆın form˘a combinatorial˘a este graf plan conform definit¸iei tradit¸ionale ¸si invers, dac˘a pentru un graf tradit¸ional plan conex se construie¸ste θ conform unei orient˘ari inverse acelor de ceasornic a muchiilor ¸si − corespunz˘atoare, graful combinatorial obt¸inut este plan ˆın noua definit¸ie). 9 / 15

Grafuri planare

Teorema Separatorului. Teorem˘ a. (Tarjan & Lipton, 1979) Fie G un graf planar cu n vˆarfuri. Exist˘a o partit¸ie a lui V (G ) ˆın clasele disjuncte A, B, S astfel ˆıncˆat: 1. S separ˘a A de B ˆın G : G − S nu are muchii de la A la B. 2. |A| ≤ 23√n, |B| ≤ 23 n. 3. |S ≤ 4 n. Aceast˘a partit¸ie se poate afla ˆın timpul O(n). Demonstrat¸ie. Consider˘am graful conex ¸si de asemenea consider˘am c˘a dispunem de o reprezentare planar˘a. Alegem un vˆ arf s ¸si execut˘ am o parcurgere bfs din s numerotˆ and vˆ arfurile (ˆın ordinea ˆıntˆ alnirii lor ˆın aceast˘ a parcurgere) ¸si atribuind fiec˘ arui vˆ arf v nivelul s˘ au ˆın arborele bfs construit. Vom nota cu L(t), 0 ≤ t ≤ l + 1 mult¸imea vˆ arfurilor de pe nivelul t (nivelul l + 1 va fi introdus ˆın scopuri tehnice ¸si este vid, ultimul nivel este de fapt l). Fiecare nivel este un separator ˆın G (avem muchii doar ˆıntre nivele consecutive). Fie t1 nivelul de la mijloc, adic˘ a nivelul ce cont¸ine vˆ arful numerotat bfs cu num˘ arul de ordine n2 . Mult¸imea L(t1 ) are a¸tile separatorului pe care ˆıl c˘ aut˘ am: o parte din propriet˘ ∪ ∧ ∪t>t L(t) < n2 . L(t) < n2 t t1 a. ˆıncˆat |L(t0 )| ≤ |L(t2 )| ≤ n ¸si t2 − t0 ≤ n. Se alege t0 cel mai mare num˘ ar cu propriet˘ a¸tile t0 ≤ t1 ¸si |L(t0 )| ≤

√

n,

√

n (exist˘ a un astfel de nivel pentru c˘ a √ |L(0)| = 1). La fel, exist˘ a t2 un cel mai mic num˘ ar astfel ˆınc at t2 > t1 ¸si |L(t2 )| ≤ n (de aceea s-a luat √ |L(l + 1)| = 0). Orice nivel strict ˆıntre t0 ¸si t2 are mai mult de n vˆ arfuri deci num˘ arul acestor nivele este mai √ mic decˆ at n, altfel am avea mai mult de n vˆ arfuri ˆın graf. Consider˘ am

C = ∪t c.

√

Se obt¸ine T (n) = 2O( n) , destul de bun pentru probleme de dimensiuni rezonabile. Este posibil ˆıns˘a ca notat¸ia O(.) s˘a ascund˘a constante mari ! 13 / 15

Problemele pentru seminariile 14 ¸si 15

1

http://profs.info.uaic.ro/ croitoru/ag/Examen/

14 / 15

Anunt¸uri

1

Acesta este ultimul curs! S˘ apt˘ amˆ ana viitoare nu se face cursul.

2

Evaluare: ∼croitoru/ag/week01.pdf pagina 13

3

Pogramare test final: 2,3 februarie; atent¸ie la anunt¸urile de la http://profs.info.uaic.ro/ orar-examene/ (se vor preciza orele pe grupe ¸si s˘ alile de examen)

4

Seminarul special de vineri seara se suspend˘ a.

15 / 15