Clasele 11-12 lecția 22 - 11 mar 2015

From Algopedia
Jump to: navigation, search

Discutarea subiectelor de la OJI

Idei pentru concursul de programe

Întrucât nu cred că voi avea timp să mai creez un întreg website pentru runde și partide, cred că merită să încercăm un joc de tip solitaire.

  • Poker american (cu informație parțială -- cărțile vin de la un modul)
  • Yams (cu informație parțială -- zarurile vin de la un modul)
  • etc.

Cuplaje în grafuri bipartite

Reducerea la flux

Introducem o sursă și o terminație fictive. Rezultă că tot ce am vorbit despre fluxuri se aplică și la cuplaje, inclusiv metoda Ford-Fulkerson și algoritmul Edmonds-Karp. Mai mult, fluxul în graful extins poate fi cel mult n/2, deci avem nevoie de cel mult n/2 parcurgeri în lățime pentru a găsi cuplajul maxim. Complexitatea algoritmului naiv este O(mn).

Iată o demonstrație că un cuplaj este maxim dacă și numai dacă nu admite drumuri de creștere. Demonstrația este considerabil mai simplă decât pentru fluxuri în grafuri, căci nu mai necesită conceptul de tăietură. Dacă cuplajul este maxim, este evident că nu mai există drumuri de creștere.

Reciproc, fie M un cuplaj care nu mai admite drumuri de creștere și să presupunem prin absurd că există un cuplaj |M'|>|M|. Fie P=M\oplus M'. Gradele nodurilor în P sunt cel mult 2, deci P este compus din căi și cicluri disjuncte. Ciclurile au lungime pară și conțin, alternativ, muchii din M și M′. În schimb, căile pot avea lungime impară și pot conține cu o muchie mai mult din M sau din M′. Cum |M'|>|M|, rezultă că trebuie să existe o cale care să conțină cu o muchie mai mult din M′. Acea cale este un drum de creștere.

Algoritmul Hopcroft-Karp

Putem îmbunătăți algoritmul naiv să necesite doar O({\sqrt  {n}}) parcurgeri în lățime, obținând o complexitate totală de O(m{\sqrt  {n}}).

  • Colecție maximală de căi disjuncte
  • Demonstrație de corectitudine
  • Detalii de implementare (se simplifică destul de mult)

(Eventual) Teorema căsătoriilor, a lui Hall

Este o teoremă interesantă care ne oferă o condiție echivalentă pentru a decide dacă un graf admite un cuplaj perfect.

Probleme

Există multe probleme care se reduc la cuplaj maxim, în mod neevident.

  • (RMI 2014) Se dă o tablă de m x n cu unele pătrate blocate. Să se plaseze un număr maxim de turnuri pe tablă care să nu se atace între ele. Două turnuri se atacă pe linie sau pe coloană, dar nu și peste un obstacol.
  • Se dă un graf orientat. Să se acopere cu cicluri. Mai exact, să se găsească o colecție de n muchii astfel încât din orice nod să intre și să iasă exact câte o muchie.

Temă