Bipartitni Graf

Bipartitni grah je graf u kojem vrhove možemo podijeliti u dva skupa tako da sve veze idu iz jednog skupa u drugi.
Odnosno, ne postoji veza između čvorova koje smo stavili u isti skup.
To izgleda ovako nekako:

Problem

Odaberi najveći mogući broj parova vrhova tako da svaki vrh pripada najviše jednom odabranom paru.
U paru smiju biti samo vrhovi između kojih postoji veza.

Algoritam

Nazovimo dva skupa bipartitnog grafa skup A i skup B.
Na početku ćemo usmjeriti veze tako da pokazuju samo iz A u B.
Za vrijeme trajanja algoritma, okretanje veze tako da vodi iz B u A značit će nam da smo napravili sparivanje dva vrha koja ta veza spaja.

Sve dok možemo, ponavljamo ova dva koraka:

Nađi put koji počinje u skupu A i završava u nesparenom vrhu iz skupa B
- vrh iz B je nesparen ako nemožemo nigdje otići iz njega, jer bi veza koja počinje u skupu B značila da je taj vrh sparen
Okreni sve veze na tom putu

Na kraju očitamo rješenje tako što pronađemo sve veze koje su okrenute od B prema A.
U svakom koraku algoritma povećat ćemo rješenje za 1.
Nacrtaj si jedan put kakav smo opisali gore, i pogledaj što se dogodi kad okreneš sve veze, pa ćeš vidjet!
A možeš pogledat i ovaj primjer.

Implementacija

Predlažem da probaš sam napisati algoritam i rješiti prvi zadatak dan dolje prije nego što pogledaš ovu implementaciju.
Ako nećeš to, onda bar pažljivo pročitaj objašnjenje i shvati ovaj kod, i onda ga napiši sam bez gledanja tu.

je tipična matrica sa nulama i jedinicama:

Osim ovoga, koristimo još dva polja:

nam kaže jesmo li u i-tom vrhu skupa A već bili ili ne
nam kaže s kojim vrhom iz skupa A je sparen i-ti vrh skupa B

U matching funkciji, pokušavamo spariti jedan po jedan vrh.
Nije očito zašto smijemo ići po redu i sparivati jedan po jedan vrh, odnosno zašto nikad ne moramo pokušati spariti neki od vrhova kojeg u prethodnim koracima nismo uspjeli spariti.
Dokaz nije složen i provodi se indukcijom, ali ovdje nećemo ulaziti u njega.

Prije svakog pokušaja sparivanja vrha, popunimo polje bio nulama.
Funkcija dfs poziva se samo sa vrhovima iz skupa A, dakle stalno smo u tom skupu.
Ona vraća jedan ako postoji put od danog vrha do nekog nesparenog vrha iz skupa B.

Pokušavamo pronaći nesparenog susjeda, ili put koji počinje od vrha s kojim je taj susjed sparen (vidi kod).
Ako uspijemo, sparimo tog našeg susjeda s nama i vratimo 1.
Okretanje veza se ovdje naoko nigdje ne vidi, ali se odvija odmotavanjem rekurzije.

int dfs(int node) {
  if (bio[node]) return 0;
  bio[node] = 1;  
  for (int i = 0; i < N; ++i) {
    if (!graph[node][i]) continue;       
    if (matched[i] == -1 || dfs(matched[i])) {
      matched[i] = node;
      return 1;
    }
  }
  return 0;
}

int matching() {
  int sol = 0;
  memset(matched, -1, sizeof matched);
  for (int i = 0; i < N; ++i) {
    memset(bio, 0, sizeof bio);
    sol += dfs(i);
  }
  return sol;
}

Zadaci

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License