AlgoritmicaGrafurilor-Cursul10olariu/curent/AG/files/agr10.pdf · Algoritmica Grafurilor - Cursul...

C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms *

Algoritmica Grafurilor - Cursul 10

Decembrie 2018

Algoritmica Grafurilor - Cursul 10 Decembrie 2018 1 / 44


Cuprins

1 Fluxuri în reţeleFluxuri de cost minim

2 Reduceri în timp polinomial pentru probleme pe grafuriMulţimii stabile de cardinal maximColorări ale nodurilorProbleme Hamiltoniene

3 Exerciţii pentru seminarul din săptămâna a 13-a



Fluxuri de cost minim

Să presupunem că în reţeaua R = (G; s ; t ; c), se dă în plus o funcţie decost: a : E ! R; 8ij 2 E , a(ij ) = aij este costul arcului ij (interpretatca fiind costul trimiterii unei "unităţi" de flux pe arcul ij ).Dacă x este un flux în R, atunci costul lui x este

a(x) =Xi;j

aijxij:

Problema fluxului de cost minimDate: R o reţea, a : E ! R o funcţie de cost, şi v 2 R+,Determină: un flux x 0 în R astfel încât

a(x 0) = min fa(x ) : x flux în R; v(x ) = vg:

Să observăm că, dacă v nu este mai mare decât valoarea fluxului maximîn R, atunci problema are întotdeauna soluţii (a(x ) este o funcţie liniarădefinită pe mulţimea nevidă şi compactă din Rm+1 a tuturor fluxurilorde valoare v).



Fluxuri de cost minim - Exemple

1. Problema asignării. Se dau n muncitori şi n slujbe. Costul repar-tizării muncitorului i slujbei j este aij . Să se asigneze fiecare muncitorcâte unei slujbe astfel încât costul total să fie minim.Considerăm reţeaua bipartită de mai jos, unde fiecare arc este etichetatcu capacitatea sa urmată de cost. Astfel, cij 0 = 1, csi = 1, asi = 0,cj 0t = 1, şi aj 0t = 0, 8i ; j 2 f1; 2; : : : ;ng.

b

b

b

b

b

b

b bs t

1, a11′

1, ann′

1, 0

1, 0

1, 0

1, 0

1, 0

1, 0

b b1, aij′

1, a1j′

1 1′

2

i

n

2′

j′

n′




Un flux de cost minim de valoare n constituie soluţia problemei.Similar putem determina un cuplaj perfect de pondere minimă într-ungraf bipartit.2. Problema de transport Hitchcock-Koopmans. Un produs,disponibil în depozitele D1; : : : ;Dn în cantităţile d1; : : : ; dn , respectiv,este cerut decătre clienţiiC1; : : : ;Cm în cantităţile c1; : : : ; cm , respectiv.Se cunosc costurile de transport unitar, aij - de la depozitul Di la clientulCj , 8i 2 f1; : : : ;ng,8j 2 f1; : : : ;mg.Să se determine o schemă de transport care să satisfacă cererea clienţilorcu un cost total al transportului minim.




Problema are soluţie numai dacănX

i=1

di >

mXj=1

cj . În acest caz, un flux

de cost minim de valoare v =mX

i=1

ci , în reţeaua de mai jos, rezolvă

problema.

b bs t

∞, a11

∞, anm

c1, 0

cm, 0

c2, 0

d1, 0

dm, 0

d2, 0

∞, aij

D1 C1

D2

Di

Dn

C2

Cj

Cm

cj , 0

b

b

b

b

b

b

b

b




DefiniţieFie x un flux în R = (G ; s ; t ; c) şi a : E ! R o funcţie de cost.

Dacă P este un A-drum în R relativ la x , atunci costul drumuluiP este definit ca

a(P) =X

ij2E(P);ij forward

aij �X

ij2E(P);ji backward

aji

Dacă C este un A-drum închis în R relativ la x , atunci a(C ) estecalculat ca mai sus, după stabilirea unui sens de parcurgere alui C(este possible ca ambele sensuri să ofere A-drumuri relativ la x ).

RemarciDacă P este un drum de creştere relativ la x , atunci x 1 = x r(P)

este un flux de valoare v(x 1) = v(x )+ r(P) şi cost a(x 1) = a(x )+r(P) � a(P).




RemarciDacă C este un A-drum închis în R relativ la x , atunci x 1 = x r(C ) este un flux de valoare v(x 1) = v(x ) şi cost a(x 1) = a(x ) +r(C ) � a(C ). Urmează că dacă a(C ) < 0 atunci x 1 este un fluxde aceeaşi valoare cu x dar de cost c(x 1) < c(x ).

Teorema 1

Un flux x de valoare v este un flux de cost minim dacă şi numai dacănu există un A-drum închis de cost negativ relativ la x în R.

Demonstraţie. ")" Din remarca de mai sus."(" Fie x un flux de valoare v astfel încât nu există un A-drum închisde cost negativ relativ la x în R. Fie x � un flux de cost minim de valoarev astfel încât

�(x ; x �) = min f�(x ; x 0) : x 0 flux de cost minim de valoare vg;

unde �(x ; x 0) = jfij 2 E : xij 6= x 0ij gj.Algoritmica Grafurilor - Cursul 10 Decembrie 2018 8 / 44



Dacă �(x ; x �) = 0, atunci x = x �, astfel x este un flux de cost minim.Altfel, �(x ; x �) > 0 şi există ij astfel încât xij 6= x �ij . Să presupunemcă 0 6 xij < x �ij 6 cij (dacă xij > x �ij , raţionamentul este similar). Dinlegea conservării fluxului, există jk 2 E astfel încât 0 6 xjk < x �jk 6 cjk ,sau există kj 2 E astfel încât 0 6 x �kj < xkj 6 cjk .Deoarece numărul de noduri este finit, repetând acest raţionament,obţinem, C , un A-drum închis relativ la x în R:

i

j

k

t

v

xij < x∗ij

xjk < x∗jk

xvj < x∗vj

x∗tk < xtk

C

b

b

bb

b

b




Dacă parcurgem C în sens contrar, obţinem un A-drum închis, C 0, rela-tiv la x �. Deoarece a(C ) > 0 (din ipoteză), şi a(C 0) = �a(C ) urmeazăcă a(C ) = 0. (x � este de cost minim; astfel, din implicaţia directă,a(C 0) > 0).Dacă vom considera x 0 = x � �(C 0), unde

�(C 0) = min

�min

kj forward in C 0

(xkj � x �kj ); minkj backward in C 0

(x �jk � xjk )

�;

atunci x 0 satisface v(x 0) = v(x �) = v , a(x 0) = a(x �) + �(C 0) � a(C 0) =

a(x �).Astfel x 0 este un flux de cost minim de valoare v , dar �(x ; x 0) <

�(x ; x �), în contradicţie cu alegerea lui x �. Astfel �(x ; x �) = 0, şiteorema este demonstrată. �




Teorema 2

Dacă x este un flux de cost minim de valoare v şi P0 este un drum decreştere relativ la x astfel încât

a(P0) = min fa(P) : P drum de creştere relativ la xg;

atunci x 1 = x r(P0) este un flux de cost minim de valoare v(x 1) =

v + r(P0).

Demonstraţie. Omisă.

Un drum de creştere de cost minim poate fi găsit folosind un algoritmpentru drumuri de cost minim. Dacă x este un flux în R şi a : E ! R

este o funcţie de cost, atunci luând aij =1 dacă ij 2 E (când x ij = 0),construim




a ij =

8>>><>>>:

aij ; dacă xij < cij şi xji = 0;min faij ;�ajig; dacă xij < cij şi xji > 0;�aji ; dacă xij = cij şi xji > 0;+1; dacă xij = cij şi xji = 0:

Un st -drum de cost a minim corespunde unui drum de creştere de costminim relativ la x în R, şi un circuit de cost negativ corespunde unuiA-drum închis relativ la x în R.Atunci, avem următorul algoritm pentru determinarea unui flux de costminim:



Fluxuri de cost minim - Un algoritm generic (Klein, Busacker, Gowanetc.)

fie x un flux de valoare v 0 6 v ; // x poate fi nul sau x = (v=v(y) � y ,unde y este un flux valoare maximă.while (9C un circuit de cost a negative) do

x x r(C );end whilewhile (v(x ) < v) dodetermină un st -drum P de cost a minim;x x min fr(P); v � v(x )g;

end whileComplexitatea timp al celui de-al doilea while este O(n3v) (dacă pornimcu fluxul nul şi capacităţile sunt întregi). Primul while poate fi imple-mentat astfel încât să aibă O(nm2 logn) iteraţii.



Reduceri în timp polinomial pentru probleme pe grafuri - Memento

Memento

Fie Pi : Ii ! fda ;nug (i 2 f1; 2g) două probleme de decizie.P1 se reduce polinomial la P2, şi notăm aceasta prin P1 6P P2,dacă există o funcţie calculabilă în timp polinomial � : I1 ! I2,astfel încât P1(i) = P2(�(i)), 8i 2 I1.

Funcţiile � vor fi definite folosind un algoritm care construieşte,pentru fiecare instanţă i1 2 I1, o instanţă i2 2 I2 în timp polinomial(în dimensiunea lui i1), astfel încât P1(i1) = da dacă şi numai dacăP2(i2) = da .

Construcţia din spatele reducerii în timp polinomial arată cumprima problemă poate fi rezolvată eficient folosind un oracol pentrucea de-a doua.




Relaţia 6P este o relaţie tranzitivă pe mulţimea problemelor dedecizie (deoarece, clasa funcţiilor polinomial calculabile este închisăla compunere).

ExempluSAT 6P 3SATSATInstanţă: U = fu1;u2; : : : ;ung o mulţime finită de variabile booleene;

C = C1 ^C2 : : : ^Cm o formulă CNF peste U :

Ci = vi1 _ vi2 _ : : : _ viki ; i = 1;m ; unde

8ij ; 9� 2 f1; 2; : : : ;ng a. î. vij = u� sau vij = u�:

Întrebare: Există o asignare t : U ! ftrue ; falseg a. î. t(C ) = true?




3SAT este restricţia problemei SAT la mulţimea instanţelor în carefiecare clauză Ci are exact 3 literali (ki = 3), unde un literal, vij , este ovariabilă sau o variabilă negată.Problema SAT este faimoasă deoarece este prima problemă de-spre care s-a arăta ca este NP-completă (Cook, 1971).

NP 6= NP \ coNP = P



Reduceri în timp polinomial - Problema mulţimii stabile de cardinalmaxim

SMInstanţă: G = (V ;E) un graf şi k 2 N.Întrebare: Există o mulţime stabilă S în G astfel încât jS j > k?

Teorema 3

(Karp, 1972). 3SAT 6P SM.

Demonstraţie. Fie U = fu1;u2; : : : ;ung, (n 2 N�), C = C1 ^

C2 : : : ^ Cm (m 2 N�) cu Ci = vi1 _ vi2 _ vi3 , i = 1;m , (unde

8ij ; 9� 2 f1; 2; : : : ;ng a. î. vij = u� sau vij = u�) reprezentând dateleunei instanţe a problemei 3SAT.Vom construi în timp polinomial (în n + m) un graf G şi k 2 N, astfelîncât există o asignare t care satisface C dacă şi numai dacă există omulţime stabilă S în G astfel încât jS j > k .




Demonstraţie (continuare).Construcţia grafului G :

8i 2 f1; 2; : : : ;ng, fie grafurile disjuncte Ti = (fui ;u ig; fuiu ig).

8j 2 f1; 2; : : : ;mg, fie grafurile disjuncteZj = (faj1; aj2; aj3g; faj1aj2; aj2aj3; aj3aj1g).

8j 2 f1; 2; : : : ;mg, fie mulţimea de muchiiEj = faj1vj1; aj2vj2; aj3vj3g, unde vj1 _ vj2 _ vj3 este clauza Cj .

V (G) =

n[i=1

V (Ti )

![

0@ m[

j=1

V (Zj )

1A

E(G) =

n[i=1

E(Ti )

![

0@ m[

j=1

E(Zj ) [ Ej

1A :




Evident, construcţia lui G se poate face în timp polinomial relativ ladimensiunea n +m a instanţei 3SAT. Fie k = n +m .

ExempluU = fu1;u2;u3;u4g; C = (u1 _u3 _u4)^ (u1 _u2 _u4)^ (u2 _u3 _u4);k = 4+ 3 = 7.

b b b b b b b b

b

b

b

b

b b b

b

b

u1 u1 u2 u2 u3 u3 u4 u4

a13

a11 a12 a21 a22

a23 a33

a31 a32




Să presupunem că răspunsul la întrebarea problemei SM pentru (G; k)instanţă este da.9S 2 SG (familia tuturor mulţimilor stabile din G) astfel încât jS j > k .Deoarece fiecare mulţime stabilă poate avea cel mult un nod în fiecareV (Ti ) şi fiecare V (Zj ), urmează că jS j = k şi jS \ V (Ti )j = 1, jS \V (Zj )j = 1, 8i = 1;n , 8j = 1;m .Fie t : U ! ftrue ; falseg dată prin

t(ui ) =

(true ; dacă S \V (Ti ) = fu ig

false ; dacă S \V (Ti ) = fuig

Atunci, t(Cj ) = true , 8j = 1;m , astfel t(C ) = true , şi răspunsul la3SAT este da.Într-adevăr, 8j = 1;m , dacă Cj = vj1 _ vj1 _ vj3 şi S \ V (Zj ) = fajkg

(k 2 f1; 2; 3g), atunci (deoarece ajkvjk 2 E) urmează că vjk =2 S .Algoritmica Grafurilor - Cursul 10 Decembrie 2018 20 / 44



Dacă vjk = u�, atunci u� =2 S , deci u� 2 S , şi - din definiţialui t - avem t(u�) = true , adică, t(vjk ) = true , ceea ce implicăt(Cj ) = true .

Dacă vjk = u�, atunci u� =2 S , deci u� 2 S , şi - din definiţialui t - avem t(u�) = true , adică, t(vjk ) = true , ceea ce implicăt(Cj ) = true .

Reciproc, dacă răspunsul la întrebarea problemei 3SAT este da, atunci9t : U ! ftrue ; falseg astfel încât t(Cj ) = true , 8j = 1;m .

Fie S1 mulţimea stabilă S1 =n[

i=1

V 0

i cu n noduri, unde

V 0

i =

(fu ig; dacă t(ui ) = truegfuig; dacă t(ui ) = falseg




Atunci, deoarece t(Cj ) = true , 8j = 1;m , urmează că există kj 2

f1; 2; 3g astfel încât t(vjk ) = true . Fie S2 =m[

j=1

fajkj g. Evident, S2 este

o mulţime stabilă în G având m noduri.Fie S = S1 [ S2. Evident, jS j = n + m = k (astfel jS j > k). Dacăarătăm că S este o mulţime stabilă, atunci răspunsul la SM pentruinstanţă (G ; k) este da.Să presupunem că 9v ;w 2 S astfel încât e = vw 2 E(G). Atunci oextremitate a lui e este în S1, iar cealaltă în S2. Dacă v 2 S1, atunciavem două cazuri:

v = u�, w = ajkj , � 2 f1; 2; : : : ;ng, j 2 f1; 2; : : : ;mg, kj 2 f1; 2; 3gşi vjkj = u�.Deoarece t(vjkj ) = true , urmează că t(u�) = true , astfel v = u� =2

S1, contradicţie.Algoritmica Grafurilor - Cursul 10 Decembrie 2018 22 / 44



v = u�, w = ajkj , � 2 f1; 2; : : : ;ng, j 2 f1; 2; : : : ;mg, kj 2 f1; 2; 3gşi vjkj = u�.Deoarece t(vjkj ) = true , urmează că t(u�) = true , astfel t(u�) =

false . Astfel, v = u� =2 S1, contradicţie. �

O demonstraţie similară poate fi făcută pentru a arăta că SAT 6P SM,singura diferenţă este că Zi sunt grafuri complete cu ki noduri.



Reduceri în timp polinomial - Colorări ale nodurilor

COLInstanţă: G = (V ;E) graf şi p 2 N�.Întrebare: Există o p-colorare (a nodurilor) lui G?

Teorema 4

3SAT 6P COL.

Această teoremă arată că problema colorării nodurilor este NP-hard.Demonstraţia dată mai jos arată că problema, care se obţine din COLprin restricţia la instanţele cu p = 3, care poate fi numită 3-COL, esteNP-hard, de asemeni.




Lema 1

Fie H graful

b

b b

b

b b

b

b

b

v1

v2

v3

v4

a) Dacă c este o 3-colorare a lui H a. î. c(v1) = c(v2) = c(v3) = a 2f1; 2; 3g, atunci în mod necesar c(v4) = a (forcing).

b) Dacă c : fv1; v2; v3g ! f1; 2; 3g satisface c(fv1; v2; v3g) 6= fag, (a 2f1; 2; 3g), atunci c poate fi extinsă la o 3-colorare c a lui H cuc(v4) 6= a .




Demonstraţie. Se examinează lista 3-colorărilor lui H .Vom utiliza reprezentarea simplificată a grafului H :

h

v1

v2

v3

v4

Demonstraţia Teoremei 4. Considerăm datele unei instanţe a 3SAT:U = fu1; : : : ;ung, (n 2 N�), o mulţime de variabile booleene, şi C =

C1^ : : :^Cm , (m 2 N�) formulă CNF cu Cj = vj1 _ vj2 _ vj3 , 8j = 1;m ,unde 8i = 1; 3, 9� a. î. vji = u� sau vji = u�.Vom construi un graf G cu proprietatea că G este 3-colorabil dacă şinumai dacă răspunsul la 3SAT pentru această instanţă este da, adică,există o asignare t : U ! ftrue ; falseg astfel încât t(C ) = true .




Construcţia necesită un timp polinomial, şi constă din următorii paşi:Considerăm grafurile disjuncte (Vi ;Ei ), 8i = 1;n , unde Vi =

fui ;u ig şi Ei = fuiu ig.

Pentru Cj = vj1 _ vj2 _ vj3 , 8j = 1;m , considerăm grafurile:

hj

vj1

vj2

vj3

aj

unde, vjk (k = 1; 3) sunt nodurile corespunzătoare literalilor vjk ,grafurile hj sunt disjuncte, şi aj sunt noduri distincte.

Considerăm un nod nou a , şi toate muchiile aaj , 8j = 1;m .

Considerăm un nod nou b, toate muchiile bui , bu i , 8i = 1;n şi ba .

Graful G are un număr de liniar de noduri relativ la n +m .




ExempluU = fu1;u2;u3;u4g, C = (u1_u2_u3)^ (u1_u3_u4)^ (u2_u3_u4).Graful G este

b

b b b b b b b b

b

b

bb

u1u1

u2 u2

b

a

u3

u3

u4

u4

a1 a2 a3

h1 h2 h3




Traveling salesman problem

Să presupunem că răspunsul la 3SAT pentru instanţă considerată estedaAstfel 9t : U ! ftrue ; falseg a. î. t(C ) = true , adică, t(Cj ) = true ,8j = 1;m . Vom arăta că G este 3-colorabil.Colorăm mai întâi nodurile ui şi u i , 8i1;n .(

c(ui ) = 1 şi c(u i ) = 2;dacă t(ui ) = truec(ui ) = 2 şi c(u i ) = 1;dacă t(ui ) = false

Observăm că, dacă v este un literal, atunci c(v) = 2 dacă şi numai dacăt(v) = false .Deoarece t este o asignare pentru care satisface C , t(Cj ) = true , 8j =

1;m . Urmează că c(fvj1 ; vj2 ; vj3g) 6= f2g, 8j = 1;m .Din Lema 1 b), putem extinde c la o 3-colorare, în fiecare graf hj , astfelîncât c(aj ) 6= 2, adică c(aj ) 2 f1; 3g.Luând c(a) = 2 şi c(b) = 3, obţinem o 3-colorare a lui G .Algoritmica Grafurilor - Cursul 10 Decembrie 2018 29 / 44



Reciproc, să presupunem că G este 3-colorabil.Putem presupune că c(b) = 3 şi c(a) = 2 (altfel, redenumim culorile).Urmează că fc(ui ); c(u ig = f1; 2g, 8i = 1;n şi c(aj ) 2 f1; 3g, 8j =

1;m .Din Lema 1 a), urmează că c(fvj1 ; vj2 ; vj3g) 6= 2, 8j = 1;m . Aceastaînseamnă că, 8j = 1;m , există a vjk 2 Cj astfel încât c(vjk ) = 1.Astfel, definind t : U ! ftrue ; falseg prin

t(ui ) =

(true ; dacă c(ui ) = 1false ; dacă c(ui ) = 2

;

Obţinem o asignare cu proprietatea că t(Cj ) = true , 8j = 1;m .Astfel răspunsul la 3SAT pentru instanţa dată este da.



Reduceri în timp polinomial - Probleme Hamiltoniene

Memento: Fie G un (di)graf. Un circuit C al lui G este un circuitHamiltonian dacă V (C ) = V (G).Un drum deschis P al lui G este un drum Hamiltonian dacă V (P) =

V (G). Un (di)graf Hamiltonian este un (di)graf care are un circuitHamiltonian. Un (di)graf trasabil este a (di)graf careare un drumHamiltonian.

Teorema 5

(Nash-Williams, 1969) Următoarele cinci probleme sunt echivalentepolinomial:

CH: Dat un graf G . Este G Hamiltonian?

TR: Dat un graf G . Este G trasabil?




DCH: Dat un digraf G . Este G Hamiltonian?

DTR Dat un digraf G . Este G trasabil?

BCH: Dat un graf bipartit G . Este G Hamiltonian?

RemarcăP1 şi P2 sunt echivalente polinomial dacă P1 6P P2 şi P2 6P P1.

Demonstraţia Teoremei 5.CH 6P TR Fie G un graf şi v0 2 V (G). Construim în timp polinomialun graf H astfel încât G este Hamiltonian dacă şi numai dacă H estetrasabil.Fie V (H ) = V (G)[fx ; y ; zg şi E(H ) = E(G)[fxv0; yzg[fwy : w 2V (G) şi wv0 2 V (G)g.




Demonstraţia Teoremei 5 (continuare).

bb

bb b

bb b

b

b

bb b

NG(v0)NG(v0)

v0v0

x

y

z

G H

Atunci, H este trasabil dacă şi numai dacă are un drum Hamiltonian,P , cu extremităţile x şi z (care au gradul 1 în H ). P există în H dacă şinumai dacă în G există un drum Hamiltonian cu o extremitate în v0 şicealaltă un vecin al lui v0, adică, dacă şi numai dacă G este Hamiltonian.




Demonstraţia Teoremei 5 (continuare).TR 6P CH Fie G un graf. Considerăm H = G + K1. Atunci, H esteHamiltonian dacă şi numai dacă G are un drum Hamiltonian.

b

G

G+K1

bb b

Echivalenţa problemelor DCH şi DTR se dovedeşte similar.CH 6P DCH Fie G un graf. Fie D digraful obţinut din G prin în-locuirea fiecărei muchii cu o pereche simetrică de arce.




Evident fiecare circuit în G dă un circuit în D şi reciproc, fiecare circuitîn D dă un circuit în G .DCH 6P CH fie D un digraf. Fiecare nod v 2 V (D) este înlocuitprintr-un graf neorientat P3(v) cu extremităţi av şi bv :

P3(v) = (fav ; bv ; cv ; dvg; favcv ; cvdv ; dvbvg):

Fiecare arc vw 2 E(D) este înlocuit prin muchia (neorientată) bvaw .Fie G graful obţinut (în timp polinomial) astfel:

b b

b

b b

b

v w

x

y z

b

b

b b

b

b

b

b

bbb

bax

bx

av

bv aw

bw

by ay bz

az

G

D




Fiecare circuit C al lui D corespunde unui circuit în G şi reciproc,fiecare circuit în G corespunde unui circuit al lui D . Urmează că D esteHamiltonian dacă şi numai dacă G este Hamiltonian.Să observăm că dacă C este un circuit al lui G , atunci acesta este generatde un circuit C 0 of D , şi length(C ) = 3 � length(C 0) + length(C 0) =

4 � length(C 0). Urmează că orice circuit al lui G este par, deci G esteun graf bipartit.Astfel demonstraţia de mai sus (DCH 6P CH) este de fapt DCH 6P

BCH.Deoarece BCH 6P CH este evidentă, Teorema 5 este complet demon-strată. �



Exerciţii pentru seminarul din săptămâna a 13-a

Exerciţiul 1. Arătaţi că următoarea problemă este NP-completăINTInstanţă: n ;m 2 N�;A 2 Zm�n ; b 2 Zm .Întrebare: Există o asignare x 2 Zn a. î. Ax 6 b?(Inegalitatea 6 dintre doi vectori este pe componente.) Hint: You cantry SM 6P INT.

Exerciţiul 2. Considerăm următoarea problemă de deciziePInstanţă: G = (V ;E un digraf şi p 2 N.Întrebare: Există A � V astfel încât jAj 6 p şi G � A nu conţinecircuite?Arătaţi că SM 6P P.




Exerciţiul 3. Un hipergraf k -uniform este o pereche H = (V ;E), undeV 6= ? este o mulţime finită, k 2 N� n f1g, şi E � Pk (V ) = fA � E :

jAj = kg. Este uşor de văzut că un hipergraf 2-uniform este un grafsimplu.Spunem că un hipergraf k -uniform H = (V ;E) este simplu dacă există ofuncţie c : V ! f1; 2; : : : ; kg astfel încât 8u ; v 2 V , u 6= v , dacă u ; v 2e pentru o anumită muchie e 2 E , atunci c(u) 6= c(v). Considerămurmătoarea problemă de deciziek -SIMPLEInstanţă: H un hipergraf k -uniform.Întrebare: H este simplu?

(a) Arătaţi că problema 3-SIMPLE este NP-completă.

(b) Arătaţi că problema 2-SIMPLE este în P.




Exerciţiul 4. Considerăm următoarea problemă de decizie:AGMInstanţă: G un graf, k 2 N.Întrebare: G are un arbore parţial T astfel încât �(T ) > k?Arătaţi că AGM 2 P.

Exerciţiul 5. Fie D = (V ;E) un digraf fără bucle. O mulţime stabilăa lui D , S � V , este numită quasi-kernel dacă fiecare nod v 2 V n Ssibil din S pe un drum de lungime cel mult 2.

(a) Arătaţi că un quasi-kernel poate fi construit în O(n + m), unden = jV j şi m = jE j.

(b) Arătaţi că 3-SAT se poate reduce în timp polinomial la problemadeterminării dacă într-un digraf dat există un quasi-kernel careconţine un nod dat.




Exerciţiul 6. Considerăm următoarea problemă de decizie: LPLInstanţă: G un graf, k 2 N.Întrebare: Are G un drum P astfel încât length(P) > k?Arătaţi că LPL este NP-completă.

Exerciţiul 7. Un kernel într-un digraf G = (V ;E) este o mulţimestabilă S � V astfel încât 8 u 2 V n S există v 2 S cu vu 2 E .Considerăm următoarea problemă de decizie:NUCLEUInstanţă: G un digraf.Întrebare: Are G un kernel?Arătaţi că următoarea construcţie conduce la o reducere polinomială alui SAT la NUCLEU (i.e. SAT 6P NUCLEU):




Exerciţiul 7 (continuare). Pentru fiecare conjucţie de clauze, F , in-stanţă a lui SAT, definim un digraf G (o instanţă pentru NUCLEU):

- pentru fiecare clauză C a lui F adăugăm un 3-circuit la G

v1C ; v

1C v2

C ; v2C ; v

2C v3

C ; v3C ; v

3C v1

C ;

- pentru fiecare variabilă x care apare în formula F , adăugăm un2-circuit la G

vx ; vxvx ; vx ; vxvx ; vx ;

- pentru fiecare clauză C şi fiecare literal u care apare în C adăugăma G trei arce

vuv1C ; vuv2

C ; vuv3C :




Exercise 8. Considerăm următoarea problemă de decizie2SATInstanţă: C o familie de clauze fiecare cu doi literali.Întrebare: Există o asignare a valorilor de adevăr către variable astfel catoate clauzele din C să fie satisfăcute?Define G digraful (implicaţiilor): V (G) = mulţimea literalilor folosiţiîn C şi E(G) = fv jwj ;w j vj : Cj = vj _ wj ; j = 1;mg (fiecare clauzăintroduce în G două arce). Arătaţi că C este satisfiabilă dacă şi numaidacă xi şi x i aparţin la componente tari conexe diferite ale lui G , 8i =1;n . Arătaţi că această proprietate poate fi verificată în O(n +m).

Exercise 9. Arătaţi că următoarea problemă este NP-completă.MAX-2SATInstanţă: C o familie de clauze fiecare cu cel mult doi literali şi k 2 N.Întrebare: Există o asignare a valorilor de adevăr către variable astfel cacel puţin k dintre clauze să fie satisfăcute?




Exercise 10. Considerăm următoarea problemă de decizieNAE-3SATInstanţă: C o familie de clauze fiecare cu doi literali.Întrebare: Există o asignare a valorilor de adevăr către variable astfel caîn fiecare clauză să avem şi un literal adevărat şi unul fals?Arătaţi că următoarea construcţie conduce la o reducere polinomială alui 3SAT la NAE 3SAT (i.e. 3SAT 6P NAE 3SAT):

- păstrăm variabilele booleene ale instanţei 3SAT, U =

fu1;u2; : : : ;ung şi adăugăm o variabilă (nouă) x ;

- pentru fiecare clauză Cj = vj1 _ vj2 _ vj3 adăugăm o variabilă nouăyj şi înlocuim Cj cu două clauze:

C 1j = vj1 _ vj2 _ yj ;C 2

j = vj3 _ x _ y j :




Exerciţiul 11. Arătaţi că următoarea problemă este NP-completă.PInstanţă: G un graf, k 2 N, k 6 jG j.Întrebare: Are G un arbore parţial, T , cu �(T ) 6 k?


AlgoritmicaGrafurilor-Cursul10olariu/curent/AG/files/agr10.pdf · Algoritmica Grafurilor - Cursul...

Documents

Transcript of AlgoritmicaGrafurilor-Cursul10olariu/curent/AG/files/agr10.pdf · Algoritmica Grafurilor - Cursul...