Algojáték 9. gyakorlat megoldókulcs

Javaslat

A megoldásokat ne nézd meg rögtön, előbb szánj egy kis időt az önálló gondolkodásra és az ötletelésre! A problémamegoldás képessége olyan mint egy izom: mindenkiben fejleszthető. Ezek a feladatok pontosan ebben segítenek. Ha teljesen elakadnál, ott a hint.

1. feladat

Határozzunk meg az alábbi preferencialistákkal megadott páros gráfokban egy-egy stabil párosítást. A gráfok egyik színosztályának csúcsait az $\{a,b,c,d,e\}$ halmazból vett betűkkel, a másik színosztályának csúcsait az $\{s,r,t,x,y,z\}$ halmazból vett betűkkel jelöltük. Az egyes csúcsok a szomszédaikat a preferenciasorrendjük szerinti csökkenő sorrendben sorolják fel.

a)

$a$: $s, t, r$
$b$: $t, s, r$
$c$: $s, t, r$

$s$: $b, a, c$
$r$: $a, c, b$
$t$: $a, c, b$

Hint

Alkalmazzuk a Gale-Shapley algoritmust (lánykérő algoritmus) egy stabil párosítás megtalálására!

A páros gráf egyik színosztályát fiúknak, a másikat lányoknak nevezzük.

Minden fiú megkéri a neki legszimpatikusabb (a preferencialistájában első helyen lévő) lány kezét.
Ha minden lányt legfeljebb egy fiú kért meg, akkor az algoritmus megáll, visszaadja ezt a párosítást.
Ha van olyan lány, akit egynél több kérő kért meg, akkor ő a neki legszimpatikusabbat leszámítva kikosaraz mindenki mást (ekkor a lány és a fiú is törlik egymást a preferencialistájukból).
Ezt ismételjük amíg van kikosarazás.

Megoldás

Futtassuk a Gale-Shapley algoritmust úgy, hogy az $\{a,b,c\}$ csúcsok a fiúk, az $\{s,r,t\}$ csúcsok a lányok!

1. kör:

$a$ megkéri $s$-t, $b$ megkéri $t$-t, $c$ megkéri $s$-t.

$a$: $\boxed{s}, t, r$
$b$: $\boxed{t}, s, r$
$c$: $\boxed{s}, t, r$

$s$: $b, \boxed{a}, \boxed{c}$
$r$: $a, c, b$
$t$: $a, c, \boxed{b}$

$s$ a két kérője közül a számára kevésbé szimpatikus $c$-t kikosarazza.

$a$: $\boxed{s}, t, r$
$b$: $\boxed{t}, s, r$
$c$: $\boxed{\cancel{s}}, t, r$

$s$: $b, \boxed{a}, \boxed{\cancel{c}}$
$r$: $a, c, b$
$t$: $a, c, \boxed{b}$

Kör vége.

$a$: $s, t, r$
$b$: $t, s, r$
$c$: $\cancel{s}, t, r$

$s$: $b, a, \cancel{c}$
$r$: $a, c, b$
$t$: $a, c, b$

2. kör:

$a$ megkéri $s$-t, $b$ megkéri $t$-t, $c$ megkéri $t$-t.

Megjegyzés: tök jogosan merülhet fel valakiben, hogy $a$ és $b$ miért zaklatják itt a lányokat, ha azok már az előző körben igent mondtak nekik. Erre az a válasz, hogy ez csak a sztori szempontjából furcsa, ha ezt leprogramozzuk ott pont a kérőkre emlékezésnek nincs értelme: a fiúk várakozási sorainak első elemeit kell összeszedni és azoknak a fiúknak a sorait poppolni, akiknek nem minimális a preferenciasorszámuk a lány oldalon. A lányokat reprezentáló tömbök pedig nem sértődnek meg ránk, ha többször is kiolvassuk belőlük ugyanazt az elemet.

$a$: $\boxed{s}, t, r$
$b$: $\boxed{t}, s, r$
$c$: $\cancel{s}, \boxed{t}, r$

$s$: $b, \boxed{a}, \cancel{c}$
$r$: $a, c, b$
$t$: $a, \boxed{c}, \boxed{b}$

$t$ a két kérője közül a számára kevésbé szimpatikus $b$-t kikosarazza.

$a$: $\boxed{s}, t, r$
$b$: $\boxed{\cancel{t}}, s, r$
$c$: $\cancel{s}, \boxed{t}, r$

$s$: $b, \boxed{a}, \cancel{c}$
$r$: $a, c, b$
$t$: $a, \boxed{c}, \boxed{\cancel{b}}$

Kör vége.

$a$: $s, t, r$
$b$: $\cancel{t}, s, r$
$c$: $\cancel{s}, t, r$

$s$: $b, a, \cancel{c}$
$r$: $a, c, b$
$t$: $a, c, \cancel{b}$

3. kör:

$a$ megkéri $s$-t, $b$ megkéri $s$-t, $c$ megkéri $t$-t.

$a$: $\boxed{s}, t, r$
$b$: $\cancel{t}, \boxed{s}, r$
$c$: $\cancel{s}, \boxed{t}, r$

$s$: $\boxed{b}, \boxed{a}, \cancel{c}$
$r$: $a, c, b$
$t$: $a, \boxed{c}, \cancel{b}$

$s$ a két kérője közül a számára kevésbé szimpatikus $a$-t kikosarazza.

$a$: $\boxed{\cancel{s}}, t, r$
$b$: $\cancel{t}, \boxed{s}, r$
$c$: $\cancel{s}, \boxed{t}, r$

$s$: $\boxed{b}, \boxed{\cancel{a}}, \cancel{c}$
$r$: $a, c, b$
$t$: $a, \boxed{c}, \cancel{b}$

Kör vége.

$a$: $\cancel{s}, t, r$
$b$: $\cancel{t}, s, r$
$c$: $\cancel{s}, t, r$

$s$: $b, \cancel{a}, \cancel{c}$
$r$: $a, c, b$
$t$: $a, c, \cancel{b}$

4. kör:

$a$ megkéri $t$-t, $b$ megkéri $s$-t, $c$ megkéri $t$-t.

$a$: $\cancel{s}, \boxed{t}, r$
$b$: $\cancel{t}, \boxed{s}, r$
$c$: $\cancel{s}, \boxed{t}, r$

$s$: $\boxed{b}, \cancel{a}, \cancel{c}$
$r$: $a, c, b$
$t$: $\boxed{a}, \boxed{c}, \cancel{b}$

$t$ a két kérője közül a számára kevésbé szimpatikus $c$-t kikosarazza.

$a$: $\cancel{s}, \boxed{t}, r$
$b$: $\cancel{t}, \boxed{s}, r$
$c$: $\cancel{s}, \boxed{\cancel{t}}, r$

$s$: $\boxed{b}, \cancel{a}, \cancel{c}$
$r$: $a, c, b$
$t$: $\boxed{a}, \boxed{\cancel{c}}, \cancel{b}$

Kör vége.

$a$: $\cancel{s}, t, r$
$b$: $\cancel{t}, s, r$
$c$: $\cancel{s}, \cancel{t}, r$

$s$: $b, \cancel{a}, \cancel{c}$
$r$: $a, c, b$
$t$: $a, \cancel{c}, \cancel{b}$

5. kör:

$a$ megkéri $t$-t, $b$ megkéri $s$-t, $c$ megkéri $r$-t.

$a$: $\cancel{s}, \boxed{t}, r$
$b$: $\cancel{t}, \boxed{s}, r$
$c$: $\cancel{s}, \cancel{t}, \boxed{r}$

$s$: $\boxed{b}, \cancel{a}, \cancel{c}$
$r$: $a, \boxed{c}, b$
$t$: $\boxed{a}, \cancel{c}, \cancel{b}$

Minden lányt legfeljebb egyvalaki kért meg. Az algoritmus leáll.

Eredmény: a stabil párosítás: $(a,t)$, $(b,s)$, $(c,r)$.

b)

$a$: $s, z, t, y$
$b$: $t, s, r, x$
$c$: $z, x, y, s$
$d$: $t, z, x$

$s$: $c, b, a$
$r$: $b$
$t$: $d, b, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, c$

Megoldás

Futtassuk a Gale-Shapley algoritmust úgy, hogy az $\{a,b,c,d\}$ csúcsok a fiúk, az $\{s,r,t,x,y,z\}$ csúcsok a lányok!

1. kör:

$a$ megkéri $s$-t, $b$ megkéri $t$-t, $c$ megkéri $z$-t, $d$ megkéri $t$-t.

$a$: $\boxed{s}, z, t, y$
$b$: $\boxed{t}, s, r, x$
$c$: $\boxed{z}, x, y, s$
$d$: $\boxed{t}, z, x$

$s$: $c, b, \boxed{a}$
$r$: $b$
$t$: $\boxed{d}, \boxed{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, \boxed{c}$

$t$ a két kérője közül a számára kevésbé szimpatikus $b$-t kikosarazza.

$a$: $\boxed{s}, z, t, y$
$b$: $\boxed{\cancel{t}}, s, r, x$
$c$: $\boxed{z}, x, y, s$
$d$: $\boxed{t}, z, x$

$s$: $c, b, \boxed{a}$
$r$: $b$
$t$: $\boxed{d}, \boxed{\cancel{b}}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, \boxed{c}$

Kör vége.

$a$: $s, z, t, y$
$b$: $\cancel{t}, s, r, x$
$c$: $z, x, y, s$
$d$: $t, z, x$

$s$: $c, b, a$
$r$: $b$
$t$: $d, \cancel{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, c$

2. kör:

$a$ megkéri $s$-t, $b$ megkéri $s$-t, $c$ megkéri $z$-t, $d$ megkéri $t$-t.

$a$: $\boxed{s}, z, t, y$
$b$: $\cancel{t}, \boxed{s}, r, x$
$c$: $\boxed{z}, x, y, s$
$d$: $\boxed{t}, z, x$

$s$: $c, \boxed{b}, \boxed{a}$
$r$: $b$
$t$: $\boxed{d}, \cancel{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, \boxed{c}$

$s$ a két kérője közül a számára kevésbé szimpatikus $a$-t kikosarazza.

$a$: $\boxed{\cancel{s}}, z, t, y$
$b$: $\cancel{t}, \boxed{s}, r, x$
$c$: $\boxed{z}, x, y, s$
$d$: $\boxed{t}, z, x$

$s$: $c, \boxed{b}, \boxed{\cancel{a}}$
$r$: $b$
$t$: $\boxed{d}, \cancel{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, \boxed{c}$

Kör vége.

$a$: $\cancel{s}, z, t, y$
$b$: $\cancel{t}, s, r, x$
$c$: $z, x, y, s$
$d$: $t, z, x$

$s$: $c, b, \cancel{a}$
$r$: $b$
$t$: $d, \cancel{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, c$

3. kör:

$a$ megkéri $z$-t, $b$ megkéri $s$-t, $c$ megkéri $z$-t, $d$ megkéri $t$-t.

$a$: $\cancel{s}, \boxed{z}, t, y$
$b$: $\cancel{t}, \boxed{s}, r, x$
$c$: $\boxed{z}, x, y, s$
$d$: $\boxed{t}, z, x$

$s$: $c, \boxed{b}, \cancel{a}$
$r$: $b$
$t$: $\boxed{d}, \cancel{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, \boxed{a}, \boxed{c}$

$z$ a két kérője közül a számára kevésbé szimpatikus $c$-t kikosarazza.

$a$: $\cancel{s}, \boxed{z}, t, y$
$b$: $\cancel{t}, \boxed{s}, r, x$
$c$: $\boxed{\cancel{z}}, x, y, s$
$d$: $\boxed{t}, z, x$

$s$: $c, \boxed{b}, \cancel{a}$
$r$: $b$
$t$: $\boxed{d}, \cancel{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, \boxed{a}, \boxed{\cancel{c}}$

Kör vége.

$a$: $\cancel{s}, z, t, y$
$b$: $\cancel{t}, s, r, x$
$c$: $\cancel{z}, x, y, s$
$d$: $t, z, x$

$s$: $c, b, \cancel{a}$
$r$: $b$
$t$: $d, \cancel{b}, a$
$x$: $b, c, d$
$y$: $c, a$
$z$: $d, a, \cancel{c}$

4. kör:

$a$ megkéri $z$-t, $b$ megkéri $s$-t, $c$ megkéri $x$-t, $d$ megkéri $t$-t.

$a$: $\cancel{s}, \boxed{z}, t, y$
$b$: $\cancel{t}, \boxed{s}, r, x$
$c$: $\cancel{z}, \boxed{x}, y, s$
$d$: $\boxed{t}, z, x$

$s$: $c, \boxed{b}, \cancel{a}$
$r$: $b$
$t$: $\boxed{d}, \cancel{b}, a$
$x$: $b, \boxed{c}, d$
$y$: $c, a$
$z$: $d, \boxed{a}, \cancel{c}$

Minden lányt legfeljebb egyvalaki kért meg. Az algoritmus leáll.

Eredmény: a stabil párosítás: $(a,z)$, $(b,s)$, $(c,x)$, $(d,t)$.

c)

$a$: $s, t, r$
$b$: $s, r, t$
$c$: $s, t, x$
$d$: $y, x$
$e$: $y, s$

$s$: $e, b, c, a$
$r$: $b, a$
$t$: $c, a, b$
$x$: $d, c$
$y$: $d, e$

Megoldás

Futtassuk a Gale-Shapley algoritmust úgy, hogy az $\{a,b,c,d,e\}$ csúcsok a fiúk, az $\{s,r,t,x,y\}$ csúcsok a lányok!

1. kör:

$a$ megkéri $s$-t, $b$ megkéri $s$-t, $c$ megkéri $s$-t, $d$ megkéri $y$-t, $e$ megkéri $y$-t.

$a$: $\boxed{s}, t, r$
$b$: $\boxed{s}, r, t$
$c$: $\boxed{s}, t, x$
$d$: $\boxed{y}, x$
$e$: $\boxed{y}, s$

$s$: $e, b, \boxed{c}, \boxed{a}, \boxed{b}$
$r$: $b, a$
$t$: $c, a, b$
$x$: $d, c$
$y$: $\boxed{d}, \boxed{e}$

$s$ a három kérője közül a számára kevésbé szimpatikus $a$-t és $c$-t kikosarazza.
$y$ a két kérője közül a számára kevésbé szimpatikus $e$-t kikosarazza.

$a$: $\boxed{\cancel{s}}, t, r$
$b$: $\boxed{s}, r, t$
$c$: $\boxed{\cancel{s}}, t, x$
$d$: $\boxed{y}, x$
$e$: $\boxed{\cancel{y}}, s$

$s$: $e, \boxed{b}, \boxed{\cancel{c}}, \boxed{\cancel{a}}$
$r$: $b, a$
$t$: $c, a, b$
$x$: $d, c$
$y$: $\boxed{d}, \boxed{\cancel{e}}$

Kör vége.

$a$: $\cancel{s}, t, r$
$b$: $s, r, t$
$c$: $\cancel{s}, t, x$
$d$: $y, x$
$e$: $\cancel{y}, s$

$s$: $e, b, \cancel{c}, \cancel{a}$
$r$: $b, a$
$t$: $c, a, b$
$x$: $d, c$
$y$: $d, \cancel{e}$

2. kör:

$a$ megkéri $t$-t, $b$ megkéri $s$-t, $c$ megkéri $t$-t, $d$ megkéri $y$-t, $e$ megkéri $s$-t.

$a$: $\cancel{s}, \boxed{t}, r$
$b$: $\boxed{s}, r, t$
$c$: $\cancel{s}, \boxed{t}, x$
$d$: $\boxed{y}, x$
$e$: $\cancel{y}, \boxed{s}$

$s$: $\boxed{e}, \boxed{b}, \cancel{c}, \cancel{a}$
$r$: $b, a$
$t$: $\boxed{c}, \boxed{a}, b$
$x$: $d, c$
$y$: $\boxed{d}, \cancel{e}$

$s$ a két kérője közül a számára kevésbé szimpatikus $b$-t kikosarazza.
$t$ a két kérője közül a számára kevésbé szimpatikus $a$-t kikosarazza.

$a$: $\cancel{s}, \boxed{\cancel{t}}, r$
$b$: $\boxed{\cancel{s}}, r, t$
$c$: $\cancel{s}, \boxed{t}, x$
$d$: $\boxed{y}, x$
$e$: $\cancel{y}, \boxed{s}$

$s$: $\boxed{e}, \boxed{\cancel{b}}, \cancel{c}, \cancel{a}$
$r$: $b, a$
$t$: $\boxed{c}, \boxed{\cancel{a}}, b$
$x$: $d, c$
$y$: $\boxed{d}, \cancel{e}$

Kör vége.

$a$: $\cancel{s}, \cancel{t}, r$
$b$: $\cancel{s}, r, t$
$c$: $\cancel{s}, t, x$
$d$: $y, x$
$e$: $\cancel{y}, s$

$s$: $e, \cancel{b}, \cancel{c}, \cancel{a}$
$r$: $b, a$
$t$: $c, \cancel{a}, b$
$x$: $d, c$
$y$: $d, \cancel{e}$

3. kör:

$a$ megkéri $r$-t, $b$ megkéri $r$-t, $c$ megkéri $t$-t, $d$ megkéri $y$-t, $e$ megkéri $s$-t.

$a$: $\cancel{s}, \cancel{t}, \boxed{r}$
$b$: $\cancel{s}, \boxed{r}, t$
$c$: $\cancel{s}, \boxed{t}, x$
$d$: $\boxed{y}, x$
$e$: $\cancel{y}, \boxed{s}$

$s$: $\boxed{e}, \cancel{b}, \cancel{c}, \cancel{a}$
$r$: $\boxed{b}, \boxed{a}$
$t$: $\boxed{c}, \cancel{a}, b$
$x$: $d, c$
$y$: $\boxed{d}, \cancel{e}$

$r$ a két kérője közül a számára kevésbé szimpatikus $a$-t kikosarazza.

$a$: $\cancel{s}, \cancel{t}, \boxed{\cancel{r}}$
$b$: $\cancel{s}, \boxed{r}, t$
$c$: $\cancel{s}, \boxed{t}, x$
$d$: $\boxed{y}, x$
$e$: $\cancel{y}, \boxed{s}$

$s$: $\boxed{e}, \cancel{b}, \cancel{c}, \cancel{a}$
$r$: $\boxed{b}, \boxed{\cancel{a}}$
$t$: $\boxed{c}, \cancel{a}, b$
$x$: $d, c$
$y$: $\boxed{d}, \cancel{e}$

Kör vége.

$a$: $\cancel{s}, \cancel{t}, \cancel{r}$
$b$: $\cancel{s}, r, t$
$c$: $\cancel{s}, t, x$
$d$: $y, x$
$e$: $\cancel{y}, s$

$s$: $e, \cancel{b}, \cancel{c}, \cancel{a}$
$r$: $b, \cancel{a}$
$t$: $c, \cancel{a}, b$
$x$: $d, c$
$y$: $d, \cancel{e}$

4. kör:

$a$-nak sajnos nincs több opciója, $b$ megkéri $r$-t, $c$ megkéri $t$-t, $d$ megkéri $y$-t, $e$ megkéri $s$-t.

$a$: $\cancel{s}, \cancel{t}, \cancel{r}$
$b$: $\cancel{s}, \boxed{r}, t$
$c$: $\cancel{s}, \boxed{t}, x$
$d$: $\boxed{y}, x$
$e$: $\cancel{y}, \boxed{s}$

$s$: $\boxed{e}, \cancel{b}, \cancel{c}, \cancel{a}$
$r$: $\boxed{b}, \cancel{a}$
$t$: $\boxed{c}, \cancel{a}, b$
$x$: $d, c$
$y$: $\boxed{d}, \cancel{e}$

Minden lányt legfeljebb egyvalaki kért meg. Az algoritmus leáll.

Eredmény: a stabil párosítás: $(b,r)$, $(c,t)$, $(d,y)$, $(e,s)$.

Megjegyzés: $a$ párosítatlan marad, mivel minden lehetséges partnerét kikosarázták. $x$ szintén párosítatlan marad, mert nincs kérője.

2. feladat

Változik-e attól a stabil párosítások száma, ha az ábrán látható gráfból töröljük

a) az $e$, illetve

b) az $f$ élt?

Hint

Használjuk az éltörlési lemmát: Ha egy $uv$ csúcspárra igaz, hogy $u$-nak $v$ az elsőszámú választottja, akkor $v$ számára $u$ "be van biztosítva", azaz minden $u$-nál rosszabb szomszédját kikosarazhatja, úgy hogy a gráfban a stabil párosítások halmaza nem változik meg.

Ahol az éltörlési lemma nem használható, ott gondoljuk végig keletkezhet-e, illetve törlődhet-e stabil párosítás a gráfban az adott él törlésével.

Megoldás

Az $e$ él törölhető, hiszen a $v_1, v_2$ csúcspárra alkalmazzuk az éltörlési lemmát: $v_1$-nek a $v_2$ az elsőszámú választottja, tehát $v_2$ törölheti a számára $v_1$-nél kevésbé szimpatikus $v_3$-hoz tartozó élét. Ettől a stabil párosítások halmaza nem változik meg, így a száma sem.

Az $f$ él sajnos nem törölhető éltörlési lemmával, ezért másképp kell érvelnünk. Két eset lehetséges:

1. eset: Az $f$ benne van egy stabil párosításban, ami eltűnik ha töröljük $f$-et. Ha az $f$ része egy stabil párosításnak, akkor abban a $(v_5, v_1)$, illetve a $(v_8, v_4)$ élek is benne kell hogy legyenek, különben a $(v_5, v_6)$, illetve a $(v_7, v_8)$ élek blokkolnának. Ekkor a $v_2$ és a $v_3$ csúcsok már csak egymás párjai lehetnek. A kapott párosítás nem stabil, hiszen a $(v_1, v_2)$ él blokkolja.

2. eset: Az $f$ blokkol egy stabil párosítást, ami stabillá válik ha töröljük $f$-et. Ilyen viszont van, például a függőleges élek: $(v_1, v_5), (v_2, v_6), (v_3, v_7), (v_4, v_8)$. Ezt blokkolja az $f$, de más él nem.

Arra jutottunk, hogy semelyik stabil párosítás nem tűnik el az $f$ él törlésével, azonban legalább egy új keletkezik. Tehát a számuk biztosan változik.

3. feladat

Lássuk be, hogy a $K_{n,m}$ teljes páros gráfban tetszőleges preferenciasorrendek mellett minden stabil párosítás lefedi a nemnagyobbik színosztályt.

Hint

Adott gráfban, adott preferenciasorrendek mellett bármely két stabil párosítás ugyanazt a csúcshalmazt fedi. Mutassunk egy stabil párosítást, amire igaz a feladatban leírt állítás!

Megoldás

Futtassuk a Gale-Shapley algoritmust a nemnagyobbik színosztály felől! Ahhoz, hogy egy fiú a preferenciasorrendjében a $k$. lányt kapja, arra van szükség, hogy $k-1$ lány kikosarazza őt. Ez csak akkor történhet meg, ha a $k-1$ lánynak már van párja. Tehát ha na $n$ fiú van, akkor egy adott fiút legfeljebb $n-1$ lány fog kikosarazni. Mivel legalább annyi lány van mint fiú, ezzel beláttuk, hogy a kapott stabil párosításban minden fiúnak lesz párja.

Tanultuk, hogy egy adott gráfban, adott preferenciasorrendek mellett bármely két stabil párosítás ugyanazt a csúcshalmazt fedi. Ezzel tehát azt is beláttuk, hogy minden stabil párosítás fedi a nemnagyobbik színosztályt.

4. feladat

Mutassunk olyan gráfot, amelyben létezik stabil párosítás ami se nem fiú-optimális se nem lány-optimális.

Hint

Bármilyen gráf jó, amiben van legalább három különböző stabil párosítás.

Legyen $3$ fiú és $3$ lány és konstruáljunk olyan példát, ahol a fiúk $k$. választásai stabil párosítást adnak, $k=1,2,3$-ra.

Megoldás

Tekintsük például az alábbi preferenciákkal ellátott gráfot:

Fiúk:

$a$: $s, r, t$
$b$: $r, t, s$
$c$: $t, s, r$

Lányok:

$s$: $b, c, a$
$r$: $c, a, b$
$t$: $a, b, c$

Ez úgy lett összerakva, hogy ha egy lány leginkább szeret egy fiút, akkor az a fiú legkevésbé szereti, illetve fordítva.

Ebben a fiú-optimális stabil párosítás az $(a,s), (b,r), (c,t)$, a lány-optimális pedig az $(s,b), (r,c), (t,a)$.

Ezen kívül stabil még az is, amikor mindenki a második választottját kapja, azaz $(a,r), (b,t), (c,s)$, hiszen a gráfban bármely más él olyan, hogy az egyik végpontjának a lehető legrosszabb, vagyis nem blokkol.

5. feladat

Mutassunk olyan gráfot, amelyben a csúcsok számában exponenciális sok stabil párosítás létezik.

Hint

Hogy alakul a stabil párosítások száma egy olyan gráfban, ahol sok független komponens van?

Megoldás

Konstrukció: Vegyünk $k$ darab független alternáló négyzetet.

Vagyis az $i$. négyzet preferencialistái legyenek:

$a_i$: $s_i, r_i$
$b_i$: $r_i, s_i$

$s_i$: $b_i, a_i$
$r_i$: $a_i, b_i$

(Ahol $a_i, b_i, s_i, r_i$ az $i$. négyzet csúcsai.)

Minden komponensben két stabil párosítás van, tehát a gráfban összesen $2^k$ stabil párosítás van. A csúcsok száma $n=4k$, azaz a stabil párosítások száma $2^{\frac{n}{4}}$, ami exponenciális $n$-ben.

6. feladat

Lássuk be, hogy a lányok szempontjából a lánykérő algoritmus nem taktikázásbiztos.

Hint

Keressünk olyan példát, ahol egy lány a preferencialistája megváltoztatásával jobb partnert tud szerezni magának, mint ha őszintén adná meg a preferenciáit.

Megoldás

Fiúk:

$f_1$: $l_1, l_2, l_3$
$f_2$: $l_1, l_3, l_2$
$f_3$: $l_3, l_1, l_2$

Lányok:

$l_1$: $f_3, f_2, f_1$
$l_2$: $f_1, f_2, f_3$
$l_3$: $f_1, f_2, f_3$

Az őszinte preferencialistákkal a Gale-Shapley algoritmus a következő eredményt adja:

Fiúk:

$f_1$: $\boxed{\cancel{l_1}}, \boxed{l_2}, l_3$
$f_2$: $\boxed{l_1}, l_3, l_2$
$f_3$: $\boxed{l_3}, l_1, l_2$

Lányok:

$l_1$: $f_3, \boxed{f_2}, \cancel{f_1}$
$l_2$: $\boxed{f_1}, f_2, f_3$
$l_3$: $f_1, f_2, \boxed{f_3}$

Azonban az $l_1$ lány döntsön most úgy, hogy megcseréli az $f_1$ és $f_2$ fiúkat.

Fiúk:

$f_1$: $l_1, l_2, l_3$
$f_2$: $l_1, l_3, l_2$
$f_3$: $l_3, l_1, l_2$

Lányok:

$l_1$: $f_3, \textcolor{red}{f_1}, \textcolor{red}{f_2}$
$l_2$: $f_1, f_2, f_3$
$l_3$: $f_1, f_2, f_3$

Ennek hatására az $f_2$ fiút fogja elutasítani az $f_1$ helyett, aki ezen túltéve magát felkéri az $l_3$ lányt, aki emiatt dobja az $f_3$ fiút, aki ezért fel tudja kérni $l_1$-et. $l_1$ pedig ennek nagyon örül.

Fiúk:

$f_1$: $\boxed{\cancel{l_1}}, \boxed{l_2}, l_3$
$f_2$: $\boxed{\cancel{l_1}}, \boxed{l_3}, l_2$
$f_3$: $\boxed{\cancel{l_3}}, \boxed{l_1}, l_2$

Lányok:

$l_1$: $\boxed{f_3}, \boxed{\cancel{\textcolor{red}{f_1}}}, \boxed{\cancel{\textcolor{red}{f_2}}}$
$l_2$: $f_1, \boxed{f_2}, f_3$
$l_3$: $\boxed{f_1}, f_2, \boxed{\cancel{f_3}}$

7. feladat

Tegyük fel, hogy a $G$ páros gráfban a lányok egy közös preferencialista szerint sorrendezik a fiúkat. Mutassuk meg, hogy ekkor pontosan egy stabil párosítás van $G$-ben!

Hint

Használhatjuk az alábbi órán tanult állítást.

Állítás. Legyenek $e_1, e_2, \dots, e_m$ a $G$ gráf élei és a gráf minden csúcsa preferálja a kisebb indexű éleket. Ekkor $G$-ben pontosan egy stabil párosítás van, ami az éltörlési lemma ismételt alkalmazásával megkapható.

Magyarán, ha mindenki az élek egy globális sorrendjéből származtatja a saját preferenciasorrendjét, akkor egy stabil párosítás van a gráfban.

Megoldás

Legyen a lányok közös preferencialistája $f_1, \dots, f_n$. Ekkor egy lehetséges jó globális sorrendje az éleknek az, hogy a fiúk preferencialistáit ebben a sorrendben konkatenáljuk egymás után. Ha mindenki ebből származtatja a saját preferenciasorrendjét, akkor pont az eredeti sorrendeket kapjuk vissza.

Ekkor a fenti állításból következik, hogy pontosan egy stabil párosítás van a gráfban.

8. feladat

Tegyük fel, hogy $G$-ben van egy él aki semelyik stabil párosításban nincs benne. Megváltozhat-e a stabil párosítások halmaza $G$-ben ha ezt az élet kitöröljük?

Hint

A válasz igen. Már találkoztunk is ilyen helyzettel. :)

Megoldás

Lásd 2. feladat b) alpont. (A gráfból tulajdonképpen csak a $v_1, v_2, v_5, v_6, v_7$ csúcsok által feszített részgráf kell.)

Megjegyzés: fontos látni, hogy nem csak attól változhat a stabil párosítások száma, ha egy stabil párosításbeli élet kitörlünk, hanem akkor is ha egy olyan éltől szabadulunk meg, ami (egymagában) blokkol egy stabil párosítást.

9. feladat

Mutassuk meg, hogy $K_{n,n}$-ben tetszőleges preferenciasorrendek mellett a fiú-optimális stabil párosításban nem lehet két különböző fiú aki a preferenciasorrendjében a legutolsó lányt kapta.

Hint

Gondoljuk végig mi történik a Gale-Shapley algoritmus futása közben azon a ponton amikor az első fiú a számára legrosszabb lányt megkapja.

Megoldás

A fiú-optimális stabil párosítást a Gale-Shapley algoritmus szolgáltatja nekünk. Ennek futása közben amikor az első fiú a számára legrosszabb lányt megkapja, az pont akkor van amikor $n-1$ lány már elutasította őt. Ez csak úgy lehetséges, ha annak az $n-1$ lánynak már van párja, vagyis a másik $n-1$ fiú már különböző párokat kapott. Vagyis abban a pillanatban, hogy egy fiú megkapja a számára legrosszabb lányt az algoritmus véget ér. Tehát több fiú nem kerülhet ebbe a helyzetbe.

10. feladat

Tegyük fel, hogy a $G$ gráf minden $e$ élére igaz, hogy van olyan stabil párosítása $G$-nek amely tartalmazza $e$-t. Lássuk be, hogy ha $M$ a $G$ egy stabil párosítása, akkor $M$ stabil marad akkor is, ha $G$ minden csúcsa megfordítja a preferenciasorrendjét az élei felett.

Hint

Tegyük fel indirekt, hogy nem lesz stabil, ekkor van hozzá blokkoló él. Azt mondtuk, hogy a gráf minden élét tartalmazza a gráf valamely stabil párosítása. Vegyünk egy ezen blokkoló élet tartalmazó az eredeti preferenciasorrendek szerint stabil párosítást, legyen ez $M'$.

Ha valaki ad nekünk két stabil párosítást egy gráfban, mit kell csinálni vele?

Megoldás

Képezzük $M$ és $M'$ szimmetrikus különbségét, vagyis azon élhalmazt amelyben minden él pontosan az egyikőjükben van benne.

Órán láttuk, hogy két stabil párosítás szimmetrikus különbsége izolált pontokból és alternáló preferenciakörökből áll. (Az alternáló preferenciakör kifejezés itt azt jelenti, hogy a kör minden éle olyan, hogy az egyik szomszédjának ő a jobbik, a másiknak meg ő a rosszabbik éle.)

A blokkoló él valamelyik alternáló körhöz tartozik.

A preferenciasorrendek megfordítása után úgy tud blokkolni az él, ha mindkét végpontja számára jobb, mint az $M$-beli éle. Ez viszont nem lehetséges, hiszen ekkor nem lett volna alternáló a kör.

11. feladat

A "barátságos békák" játékban adott a síkon $n$ darab pont úgy, hogy bármely két pontpár távolsága különböző — ezek a pontok egy tó tavirózsáinak helyét jelölik. A játékban két játékos lép felváltva a következő szabályok szerint. A kezdőjátékos az első lépésben kiválaszt egy tavirózsát és rátesz egy békát. Ezután a másik játékos választ egy, az előzőtől különböző tavirózsát és szintén rátesz egy békát. Innentől minden lépésben a soron következő játékos választ egyet a két béka közül és áthelyezi azt egy másik tavirózsára úgy, hogy a két béka közötti távolság szigorúan csökkenjen, de a két béka nem kerülhet ugyanarra a tavirózsára. Az a játékos veszít, aki nem tud lépni.

a) Bizonyítsuk be, hogy ha $n$ páros, akkor a második játékosnak van nyerő stratégiája.

b) Bizonyítsuk be, hogy ha $n$ páratlan, akkor a kezdőjátékosnak van nyerő stratégiája.

(Pöttyös feladat.)