Note de curs, clasele 11-12, 8 februarie 2013

Cuplaj maxim

• trecere în revistă a algoritmilor de flux
  • Ford-Fulkerson
  • Edmonds-Karp
  • push-relabel
  • relabel-to-front
• reducerea problemei de cuplaj la o problemă de flux prin adăugarea a două noduri
• Ford-Fulkerson funcționează în O(mn), căci poate itera de cel mult n ori
• implementare (fără nodurile s și t)
• forma drumurilor de creștere (lungime impară)
• algoritmul Hopcroft-Karp
  • găsește la fiecare iterație un set maximal de drumuri de creștere de lungime minimă
  • stratifică graful cu BFS (arbore ungar)
  • construiește drumurile prin ștergere topologică
  • demonstrație (incompletă) că la următorul pas, lungimea drumurilor crește
  • demonstrație (incompletă) că pot fi cel mult $O({\sqrt {n}})$ iterații
• problemă de cuplaj: acoperirea unui graf cu cicluri
  • scurtă discuție despre fluxuri de cost minim, drumuri negative, Bellman-Ford

Probleme de programare dinamică

• dinamică pe arbore: pomul de Crăciun. Un arbore are câte un bec și câte un buton în fiecare nod. La apăsarea butonului, becul din nod și din toți vecinii își schimbă starea. Să se găsească o modalitate de a aprinde toate becurile.
• Se dă un vector cu n elemente. Să se găsească o submulțime de sumă maximă divizibilă cu n.
  • când se cere doar o submulțime (nu de sumă maximă), se rezolvă cu principiul lui Dirichlet
• rucsac cu diverse variațiuni
• ciclu hamiltonian bitonic