7.b) Parositasok

Parositasok paros grafokban

Stabil parositas: Gale–Shapley algoritmus $O(m)$

Fiuk algoritmusa: Minden fiu eloszor megkeri az altala legkedveltebb lanyt, ha az kikosarazza, akkor megkeri a kovetkezot, es igy tovabb addig ameddig nem talal valakit vagy nincs mar senki.

Lanyok algoritmusa: Egy lany az elso kerot elfogadja ideiglenes partnernek, a tovabbi keroknel eldonti melyik a jobb: a mostani partner, vagy az uj kero, a rosszabbikat kikosarazza, es igy tovabb. Mindig az eddigi legjobbat tartja meg (ideiglenes) partnernek, es az osszes tobit kikosarazza.

Tartalmazasra maximalis parositas

Konig javito utas algoritmusa $O(\min (n_1,n_2)\cdot m)$

Def.: Legyen $G$ graf es $M$ parositas $G$-ben, es $P:v_0,e_1,v_1,\dots ,e_k,v_k$ egy ut. Ekkor $P$ egy javito ut $M$-re nezve, ha $v_0$ es $v_k$ nem parositottak, $k$ paratlan es a paros sokadik elek elemei $M$-nek.
Tehat, $P$ minden masodik ele eleme az eredeti parositasnak, es az elso es utolso csucs $P$-nek nem fedett $M$ altal.

Algoritmus: Kiindulunk egy tetszoleges parositasbol es amig van javito ut addig csinaljuk a kovetkezot: vegyuk a szimmetrikus differenciajat a parositasnak es a javito utnak es az legyen a kovetkezo parositas.

Hopcroft–Karp algoritmus $O(m\sqrt{n^{\ast }})$ ahol $n^{\ast }=\nu (G)\le \min (|U|,|V|)\le n/2$

Tetel: (Hall) Paros grafban akkor es csak akkor letezik $A$-t fedo parositas, ha $|X|\le |N(X)|$ minden $X\subseteq A$-ra.
Tetel: (Konig-Hall) Maximalis meretu parositas merete megegyezik minimalis lefogo ponthalmaz meretevel.

Maximalis sulyu eset

• Maximalis sulyo parositas: Kuhn Magyar modszere $O(|V{|}^2\cdot |E|)$

Feladat: Egy $G=(S,T)$ paros grafon adott $c:E\to {\mathbb{R}}^{+}$ elek sulyozasa es $\pi :V\to {\mathbb{R}}^{+}$ csucsok sulyozasa ugy hogy $c(uv)\le \pi (u)+\pi (v)$. Ezen a grafon es sulyozasokkal szeretnenk egy maximalis sulyu parositast talalni.

Algoritmus: Legyen $E_{\pi }$ azon elek halmaza melyre $c(uv)=\pi (u)+\pi (v)$, tehat az eles elek halmaza.
Altalanos lepes:

1. $M\subseteq E_{\pi }$ a jelenlegi parositas az eles eleken.
2. Nezzuk meg, hogy $M$ maximalis-e $E_{\pi }$-ben, tehat nezzuk meg hogy van-e alternalo ut $O(m)$ idoben.
3. Ha van alternalo ut akkor bovitsuk ki $M$-et.
4. Ha nincs alternalo ut akkor $M$ maximalis $E_{\pi }$-ben.
5. Legyen $R_T$ azon $T$-beli csucsok melyeket nem fed $M$, hasonlokeppen $R_S$ azon $S$-beli csucsok melyeket nem fed $M$.
6. Legyen $Z$ az $R_S$-bol elerheto csucsok halmaza.
7. Meggondolhato hogy egy $M$-beli parositas el vagy mindket csucsa $Z$-ben van, vagy egyik sem, kulonben lenne alternalo ut.
8. Azt szeretnenk csinalni, hogy $Z\cap T$ csucsok $\pi$-jet $\epsilon$-al noveljuk, es $Z\cap S$-beli csucsok $\pi$-jet $\epsilon$-al csokkentjuk.
9. Ez a modositas $\pi$-t csak a $Z\cap S\to T-Z$ kereszt eleken ronthatja el.
10. Tehat vegyuk $\epsilon =\min \{\pi (u)+\pi (v)-c(uv)\}$ ahol $u\in Z\cap S$ es $v\in T-Z$.
11. Ezzel az $\epsilon$-al modositsuk a lefogo sulyozast es kezdjuk ujra az elso lepestol.

Megj.: Minden $\pi$-nek valtoztatasa utan $Z\cap T$ merete no tehat legfeljebb $|T|$ darab modositast kell elvegezni. Figyelem, az eles elek szama nem feltetlenul no, ezt szokta sok ember elcseszni.

Tetel: (Egervary) Adott $G=(S,T,E)$ paros graf, melyen letezik teljes parositas. Tovabba edott $c:E\to \mathbb{R}$ elek sulyozasa es $\pi :V\to \mathbb{R}$ melyre $\pi (u)+\pi (v)\ge c(u,v)$ lefogo sulyozasa. Ekkor a maximalis sulyo teljes parositas erteke egyenlo a minimalis sulyo lefogo csucshalmaz ertekevel.

Elszinezes

• Ketszinezes: BFS $\to$ BFS szintek, van vagy nincs paratlan kor

G3C NP-teljes
G$k$C NP-teljes