Informatyka MIMUW

Przypomnijmy, że:

Graf dwudzielny to graf $\mathbf{G}=( V,E )$, w którym zbiór wierzchołków $V$ da się podzielić na dwa rozłączne podzbiory $V_1$ oraz $V_2$ tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru $V_i$ nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez $( V_1\cup V_2,E )$. Zauważmy jednak, że podział taki nie jest jednoznaczny - np. w antyklice $\mathcal{A}_{n}$ dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Twierdzenie 13.6

Graf jest dwudzielny wtedy i tylko wtedy, gdy każdy jego cykl ma parzystą długość.

Dowód

Załóżmy najpierw, że graf $\mathbf{G}=( V,E )$ jest dwudzielny czyli, że $V$ można podzielić na dwa rozłączne zbiory wierzchołków $V_1$ oraz $V_2$, w ten sposób, że podgrafy indukowane $\mathbf{G}|_{V_i}$ są antyklikami. Rozważmy cykl $v_1\to v_2\to\ldots\to v_{k-1}\to v_k \to v_1$ o $k$ elementach. Bez straty ogólności możemy załóżyć, że $v_1\in V_1$. Ponieważ pomiędzy wierzchołkami z $V_1$ nie ma krawędzi, to $v_2\in V_2$. Z kolei $v_3\in V_1$, a $v_4\in V_2$ i tak dalej. Tak więc każdy $v_i$ o nieparzystym indeksie $i$ należy do $V_1$. W konsekwencji $v_k$ musi mieć parzysty indeks $k$, aby mógł być połączony z $v_1$. W rezultacie otrzymujemy, że cykle muszą być parzystej długości.

Dowód odwrotnej implikacji przeprowadzimy najpierw przy założeniu, że graf $\mathbf{G}$ jest spójny. Naszym celem jest takie podzielenie $V$ na dwa zbiory wierzchołków $V_1,V_2$, by, dla $i=1,2$, żadne dwa wierzchołki z $V_i$ nie były ze sobą połączone. Wybierzmy z $V$ dowolny wierzchołek $v$. Niech $V_1$ będzie zbiorem, do którego należy $v$ oraz wszystkie wierzchołki, do których można dojść z $v$ ścieżką parzystej długości, zaś $V_2$ niech składa się z pozostałych wierzchołków. Załóżmy, że $u_1,u_2\in V_1$. Wtedy oczywiście istnieją ścieżki $v\to\ldots\to u_1$ oraz $u_2\to\ldots\to v$ o parzystej długości. Gdyby $u_1,u_2$ były połączone krawędzią, to dostalibyśmy cykl $v\to\ldots\to u_1\to u_2\to\ldots\to v$ o nieparzystej długości. A zatem $\mathbf{G}|_{V_1}$ jest antykliką. Aby zobaczyć, że również $\mathbf{G}|_{V_2}$ jest antykliką, wystarczy zauważyć że $V_2$ składa się z tych wierzchołków grafu $\mathbf{G}$, do których z początkowo wybranego wierzchołka $v$ można dojść jedynie ścieżkami nieparzystej długości. Teraz uzasadnienie, że także $V_2$ indukuje antyklikę jest analogiczne jak dla $V_1$.

Niech teraz graf $\mathbf{G}$ ma $l>1$ spójnych składowych $C_1,\ldots,C_l$. Wtedy każdą spójną składową $C_i$ możemy podzielić na zbiory $C_i^1,C_i^2$ świadczące o dwudzielności grafu indukowanego $\mathbf{G}_{C_i}$. W konsekwencji daje to podział $V$ na $C_1^1\cup\ldots\cup C_l^1$ oraz $C_1^2\cup\ldots\cup C_l^2$ świadczący o dwudzielności całego grafu $\mathbf{G}$.

Z grafami dwudzielnymi związany jest problem biura matrymonialnego. Do biura matrymonialnego zgłaszają się mężczyźni i kobiety poszukujący swojej drugiej połowy. Niestety nie każdemu mężczyźnie odpowiada każda kobieta i na odwrót. A więc każdy zgłaszający podaje swój opis, jak i wymagania stawiane potencjalnemu partnerowi. Interpretując mężczyzn i kobiety jako wierzchołki grafu, w którym krawędzie łączą "mężczyznę" z "kobietą", jeśli nawzajem sobie odpowiadają, otrzymujemy dwudzielny graf $\mathbf{G}_z( M,K )$ odpowiadający potencjalnym związkom. Biuro matrymonialne ku uciesze klientów (i maksymalizacji swojego zysku) chciałoby stworzyć jak najwięcej par. Optymalnie by było, gdyby nikt nie został samotny. Wtedy jednak musimy oczywiście założyć, że mężczyzn jest tyle samo co kobiet.

Skojarzenie w grafie dwudzielnym $\mathbf{G}=( V_1\cup V_2,E )$ to podzbiór krawędzi $M\subseteq{\sf E}\!(\mathbf{G})$, w którym żadne dwie $v_1 v_2, u_1 u_2\in M$ nie wychodzą z tego samego wierzchołka.
Powiemy ponadto, że $v\in V_i$ jest skojarzony, jeśli istnieje $w\in V_{3-i}$ taki, że krawędź $vw$ należy do skojarzenia.

Pełne skojarzenie $V_1$ z $V_2$ w grafie dwudzielnym $\mathbf{G}=( V_1\cup V_2,E )$ to skojarzenie, w którym każdy wierzchołek z $V_1$ jest skojarzony.

Naturalnym jest pytanie, kiedy istnieje pełne skojarzenie $V_1$ z $V_2$ w grafie dwudzielnym $\mathbf{G}=( V_1\cup V_2, E )$. Odpowiedział na nie P. Hall. Użył do tego funkcji $\Phi\!(A)$ zwracającej dla $A\subseteq V_1$ zbiór tych wierzchołków $V_2$, które są sąsiednie z przynajmniej jednym wierzchołkiem w $A$.

Twierdzenie 13.7 [O Skojarzeniach w Grafie Dwudzielnym, P. Hall 1935]

Niech $\mathbf{G}=( V_1\cup V_2,E )$ będzie grafem dwudzielnym. Wówczas pełne skojarzenie $V_1$ z $V_2$ istnieje wtedy i tylko wtedy, gdy $\vert A \vert \leq\vert \Phi\!(A) \vert$ dla każdego podzbioru $A$ zbioru $V_1$.

Dowód

Dla dowodu nierówności $\vert A \vert \leq\vert \Phi\!(A) \vert$ załóżmy, że $M$ jest pełnym skojarzeniem. Elementy skojarzone z elementami zbioru $A$ muszą być oczywiście w $\Phi\!(A)$. Z drugiej strony skojarzenie $M$ determinuje injekcję $A \longrightarrow \Phi\!(A)$, skąd natychmiast $\vert A \vert \leq\vert \Phi\!(A) \vert$.

Dowód implikacji odwrotnej jest nieco trudniejszy. Przeprowadzimy go indukcyjnie ze względu na liczbę wierzchołków $n_1=\vert V_1 \vert$. Dla $n_1=1$ nierówność $\vert V_1 \vert \leq\vert \Phi\!(V_1) \vert$ gwarantuje, że jest co kojarzyć z jedynym wierzchołkiem w $V_1$. Załóżmy więc, że $n_1>1$ i rozważmy dwa przypadki:

1. Dowolny właściwy podzbiór $W$ zbioru wierzchołków $V_1$ posiada więcej sąsiadów niż jego moc, tzn. $\vert \Phi\!(W) \vert>\vert W \vert$. Wtedy wybieramy dowolne wierzchołki $v_1\in V_1$ oraz $v_2\in V_2$ i je kojarzymy. Dla $W \subseteq V_1-\lbrace v_1 \rbrace$ zbiór sąsiadów w zbiorze $V_2$ pomniejszonym o wybrany już $v_2$ jest nadal nie liczniejszy niż liczność $\vert W \vert$. Założenie indukcyjne gwarantuje nam więc jakieś skojarzenie pełne $M$ zbioru $V_1-\lbrace v_1 \rbrace$ z $V_2-\lbrace v_2 \rbrace$ w grafie pozostałych wierzchołków $\mathbf{G}|_{(V_1-\lbrace v_1 \rbrace)\cup(V_2-\lbrace v_2 \rbrace)}$. Oczywiście $M\cup{v_1v_2}$ jest poszukiwanym skojarzeniem pełnym w $\mathbf{G}$.

2. Istnieje właściwy podzbiór $W$ zbioru $V_1$, taki że $\vert \Phi\!(W) \vert=\vert W \vert$.

Ponieważ dla $A\subseteq W$ mamy $\Phi\!(A)\subseteq \Phi\!(W)$, to

$\vert A \vert\leq\vert \Phi\!(A) \vert=\vert \Phi\!(A)\cap\Phi\!(W) \vert.$

Ta nierówność pozwala użyć założenia indukcyjnego do skojarzenia wszystkich elementów ze zbioru $W$ z elementami należącymi do $\Phi\!(W)$.

Wystarczy więc znaleźć skojarzenie pozostałych elementów, czyli skojarzenie zbioru $V_1- W$ ze zbiorem $V_2- \Phi\!(W)$. Skojarzenie takie dostaniemy również indukcyjnie, o ile pokażemy, że dla dowolnego $A\subseteq V_1- W$, zbiór jego sąsiadów w $V_2- \Phi\!(W)$ jest liczniejszy od $A$, tzn.

$\vert A \vert\leq\vert \Phi\!(A)-\Phi\!(W) \vert.$

Załóżmy, że jakiś zbiór $A\subseteq V_1- W$ nie spełnia powyższej nierówności. Wtedy

$\vert A\cup W \vert =\vert A \vert\cup\vert W \vert >\vert \Phi\!(A)-\Phi\!(W) \vert+\vert \Phi\!(W) \vert \geq\vert \Phi\!(A\cup W) \vert,$

co przeczy założeniu twierdzenia, przy którym pracujemy.