Optimizare combinatorială în teoria jocurilor

Cristina SichimColegiul National Ferdinand I, Bacau31 aug. 2020

Formularea problemei. Ana și Barbu se joacă pe un graf G, alegând alternativ vârfuri distincte v0, v1,.. astfel încât, pentru orice i > 0, vi este adiacent cu vi-1. Pierde jucătorul care nu mai poate alege un vârf. Demonstrați că dacă Ana începe jocul, atunci ea are o strategie căștigătoare (adică indiferent de căt de bine joacă Barbu, ea căștigă) dacă și numai dacă graful G nu are un cuplaj perfect. Argumentați că,pentru un graf dat, problema de a decide dacă Ana are o strategie căștigătoare (atunci cănd ea îcepe jocul) este din NP.
Ipoteză generală : Ana începe jocul.
• =>Demonstrăm că dacă, Ana are o strategie câștigătoare (indiferent de cât de bine joacă Barbu) atunci graful G nu are un cuplaj perfect.
Presupunem prin reducere la absurd că Ana are o strategie câștigătoare și graful G are un cuplaj perfect.

Un cuplaj este o mulțime independentă de muchii.
Dacă G admite un cuplaj perfect M, atunci S(M)=V(G), unde S(M) reprezintă mulțimea vârfurilor saturate de cuplajul M => dM(v) = 1,vV, unde dM(v)=|{e|eM, e incidentă cu v}|, ceea ce indică faptul că orice vârf al grafului este incident cu o muchie a cuplajului.

Atunci când Ana alege prima dată un vârf, problema se reduce la componenta conexă din care face parte acel vârf. Un graf care are un cuplaj perfect are în orice componentă conexă un număr par de vârfuri.
Considerăm P un drum alternat realativ la cuplajul M => dintre oricare două muchii consecutive ale drumului alternat P, exact una aparține cuplajului M.
Pentru orice alegere a Anei a unui vârf vV(G), Barbu va alege un vârf w V(G), de pe drumul alternat P al lui G relativ la cuplajul M, astfel încât muchia vw să aparțină cuplajului M. În acest fel, la următorul pas Ana va fi obligată să aleagă un vârf v’, cu proprietatea că muchia wv’ nu aparține cuplajului M.
Cum fiecare vârf este incident cu o muchie a cuplajului și, chiar de la prima alegere, Barbu alege vârfuri mergând doar pe muchii aparținând cuplajului M => Barbu va putea alege, la fiecare pas, vârful vB corespunzător muchiei vAvB care aparține cuplajului și vA reprezintă vârful ales de Ana la pasul anterior => Barbu câștigă jocul pentru că va alege ultimul vârf (daca Ana ar face ultima alegere a unui vârf ar însemna că acel vârf nu este incident cu o muchie din cuplajul M, ceea ce ar contrazice faptul că M este cuplaj perfect).
În exemplul următor am marcat fiecare muchie a cuplajului cu linie continuă.

Rezultă că presupunerea făcută este falsă și, dacă Ana are o strategie câștigătoare atunci graful G nu are un cuplaj perfect.
• <= Demonstrăm că dacă, graful G nu are un cuplaj perfect atunci Ana are o strategie câștigătoare (indiferent de cât de bine joacă Barbu)

Considerăm că G nu are cuplaj perfect.
Fie M un cuplaj de cardinal maxim în G.
La primul pas, Ana alege un vârf vA care nu este incident cu muchii ce aparțin cuplajului M. Vârful v0 este adiacent doar cu vârfuri care sunt incidente cu muchii ce aparțin cuplajului M. Dacă v0 ar fi adiacent și cu alte vârfuri vx care nu aparțin cuplajului M, atunci muchia vovX ar putea fi adăugată cuplajului M ceea ce contrazice faptul că M este un cuplaj de cardinal maxim în G.
În acest fel, Barbu este nevoit să aleagă un vârf vB incident cu o muchie ce aparține cuplajului M. În continuare, Ana alege un vârf vA adiacent cu vB astfel încât muchia vBvA să aparțină cuplajului M. În continuare, pentru orice alegere v a lui Barbu, Ana alege vârful w, adiacent cu v, cu proprietatea că vwM.
Ultima alegere aparține Anei, pentru că altfel, dacă ultima alegere ar aparține lui Barbu, ar rezulta că în G există drumuri de creștere relativ la M, ceea ce ar contrazice faptul că M este un cuplaj de cardinal maxim în G (Berge).

Exemplu: A(1) B(2) A(3) B(4) A(5) B(6) A(7) B(8) reprezintă un drum de creștere pentru graful din imaginea următoare, ceea ce contrazice faptul că M este un cuplaj de cardinal maxim.

Conform observațiilor de mai sus, rezultă că ultima alege aparține Anei, deci acesta câștigă jocul.

Pentru exemplu anterior, atunci când M este un cuplaj maxim, Ana câștigă jocul conform strategiei prezentate anterior:

Demonstrăm că problema de a decide dacă Ana are o strategie câștigătoare este din NP.

Conform celor demonstrate anterior, pentru a decide dacă Ana are o strategie de câștig este suficient să verificăm, utilizând un algoritm polinomial, dacă graful G are un cuplaj perfect.

Dacă se consideră următoarea 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ștere relativ la M do
M ← MP
Neajunsul acestui algoritm este acela că testul de oprire a ciclului - inexistența drumului de creștere - poate conduce la un număr exponențial de operații. Edmonds (1965) a demonstrat posibilitatea implementării acestui algoritm astfel încât numărul total de operații să fie polinomial în raport cu numărul de vârfuri ale grafului G.

Teoremă. Algoritmul lui Edmonds determină, în O(n3) operații, un cuplaj de cardinal maxim într-un graf oarecare.
Secvența care verifică dacă cuplajul de cardinal maxim este perfect este liniară (pentru cuplajul identificat verificăm dacă fiecare vârf este incident cu o muchie a cuplajului) și nu modifică complexitatea algoritmului => Putem verifica, în timp polinomial, faptul că G are un cuplaj perfect => Problema de a decide dacă Ana are o strategie câștigătoare este din NP.

Observație.
Putem verifica dacă algoritmul admite un cuplaj perfect și utilizând teorema lui Tutte însă, în acest caz algoritmul general nu este polinomial dacă se generează toate submulțimile lui S (numărul submulțimilor nevide este 2n-1).
Demonstrație.
Conform teoremei lui Tutte, un graf G=(V,E) are un cuplaj perfect dacă și numai dacă q(G-S)≤|S|, SV, unde q(G-S) reprezintă numărul componentelor conexe impare ale lui G-S.

Considerăm următorul algoritm polinomial care verifică dacă q(G-S)≤|S|, SV.

Fie SV(G) cu s=|S| și G1=G-S.
Considerăm următorul algoritm care determină numărul componentelor conexe impare ale lui G1.
Notăm V=V(G1)
Algoritm A1
kimpar←0
V1←∅
while(V≠V1)
          { alege v∈V\V1
             V1←V1∪\{v}
             C←∅
             k←1
             adauga(C,v)
             while(C≠∅){ x←prim(C)
                                          for v∈N_G1 (x)   do
                                              if v∉V1 then {k←k+1
                                                                               adauga(C,v)
                                                                               V1←V1∪{v}
                                                                              }
                                         elimina(C,x)
                                       }
                 if k%2≠0 then kimpar←kimpar+1
}
Complexitatea algorimului este O(n_1+m_1 ),unde n_1=|V(G1)|=n-s,m_1=|E(G1)| (complexitatea unui algoritm BFS)

Pentru determinarea tuturor submulțimilor S putem să utilizăm un șir de n cifre binare. Inițial, șirul de cifre este format doar din 0-uri. La fiecare pas se adună 1 (în baza 2) și se obține numărul corespunzător următoarei submulțimi. Fiecare cifră binară 1, aflat pe o poziție i în șirul cifrelor binare, marchează apartenența elementului i la submuțimea S.

Exemplu. Pentru n=3, obținem succesiv:
000+1=001  S={3}
001+1=010  S={2}
010+1=011  S={2,3}
011+1=100  S={1}
100+1=101  S={1,3}
101+1=110  S={1,2}
110+1=111  S={1,2,3}

Acest algoritm (A2) determină la fiecare pas, următoarea submuțime S.

Algoritmul care verifică dacă q(G-S)≤|S|, SV :
Inițializează șirul de n biți cu 0
ok←true
do {
- determina urmatoarea submulțime S (conform A2)
- calculeaza kimpar conform (algoritmului A1)
if kimpar>|S| then ok←false
} while(ok and |S|<n)

Dacă valoarea variabilei ok este true la sfârșitul algoritmului => q(G-S)≤|S|, SV => Ana are o strategie de câștig.

2 comentarii22 de accesări

Comentarii

Mariana Lulache

Profil

Colegi

Coleg pentru

ABSOLUT REMARCABIL !! FELICITARI !!

Mariana Lulache acum 2228 zile

Mariana Lulache

Profil

Colegi

Coleg pentru

Va MULTUMESC pentru ca mi-ati redat increderea ca i_Teach nu este confiscat de persoane care insereaza niste linkuri ce nu duc nicaieri,in loc de articole !

Mariana Lulache acum 2228 zile

Alte articole ale autorului

MyMouseRectifier - JavaScript31 aug. 20201 comentariu
Perspico - implementare Java31 aug. 20201 comentariu
Elemente de Teoria probabilităților31 aug. 20201 comentariu

Toate articolele autorului

Ministerul Educaţiei

Cristina Sichim

Optimizare combinatorială în teoria jocurilor

Comentarii

Mariana Lulache

Mariana Lulache

Alte articole ale autorului

Termeni şi condiţii de utilizare a serviciilor platformei iTeach