Zastosowania w teorii grafów

Do tej pory mowa była jedynie o grafach zorientowanych. Teraz potrzebować będziemy grafu zwykłego i grafu dwudzielnego. Grafem zwykłym nazywamy parę $G=(V;E)$, gdzie $V$ jest dowolnym zbiorem zwanym zbiorem wierzchołków grafu $G$, zaś $E$ jest pewnym podzbiorem zbioru dwuelementowych podzbiorów zbioru $V$, czyli

$$E \subset \{ \{ x,y\} : x, y \in V, x \neq y \}$$

nazywanym zbiorem krawędzi grafu. Krawędź $\{x,y\}$ grafu $G$, zapisujemy krócej $xy$. $x$ i $y$ nazywamy jej końcami. Jeśli $x,y \in E$ to mówimy, że $x$ i $y$ są wierzchołkami sąsiednimi lub połączonymi . Zbiór sąsiadów wierzchołka $x$ w grafie $G$ znaczamy przez $N_G(x) = \{ y\in V: xy \in E\}$.
Grafy zwykłe mają swoją - bardzo wygodną i sugestywną - interpretację graficzną: wierzchołki w tej reprezentacji są przedstawiane jako punkty płaszczyzny a krawędzie jako łączące je krzywe (p. rys. 8.5.1).
Zbiór krawędzi $F \subset E$ jest niezależny jeżeli dla dowolnych różnych krawędzi $e,f \in F$ zachodzi $e\cap f = \emptyset$. Zbiory niezalężne krawędzi grafu $G$ nazywać będziemy skojarzeniami w grafie $G$.
Graf $G$ nazywamy dwudzielnym jeżeli istnieje podział^8.11 zbioru $V=X \cup Y$ taki, że dla każdej krawędzi $xy \in E$ jeden z wierzchołków $x, y$ należy do zbioru $X$ podczas gdy drugi należy do zbioru $Y$. Piszemy wtedy $G=(X,Y;E)$.
Problem znajdowania skojarzeń w grafach - na przykład pełnych skojarzeń czyli takich zbiorów $M$ niezależnych krawędzi, że $\bigcup_{e \in M}e = V$, lub skojarzeń o maksymalnej liczbie krawędzi, są bardzo ważnymi problemami teorii grafów, posiadającymi także zastosowania (czy też interpretacje) praktyczne.

Przykład 8.4   W pewnym zakładzie pracy zatrudnieni są pracownicy
$p_1,...,p_k$. W zakładzie tym są też stanowiska pracy $s_1,...,s_l$, przy czym nie każdy pracownik może pracować przy każdym stanowisku. Dla dobrego funkcjonowania zakładu istotny jest problem jak przydzielić stanowiska pracy wszystkim zatrudnionym, by optymalnie wykorzystać pracowników i obsadzić stanowiska pracy.
Taka sytuacja łatwo daje się opisać przy pomocy grafu dwudzielnego $G=(X,Y;E)$, gdzie $X=\{p_1,...,p_k\}, Y=\{s_1,...,s_l\}, E=\{ p_is_j: p_i \mbox{ może} \linebreak \mbox{ obsługiwać stanowisko } j\}$.
Nasz problem w języku teorii grafów można sformułować tak: znajdź w $G$ skojarzenie $M$ o maksymalnej liczbie krawędzi. Sytuacja będzie oczywiście najlepsza wtedy, gdy takie skojarzenie będzie pełnym skojarzeniem $X$ w $Y$ grafu dwudzielnego $G=(X,Y;E)$, t.j. wtedy gdy dla każdego $x \in X$ istnieje krawędź $e \in E$ taka, że $x\in e$^8.12.

W związku z powyższym przykładem powstaje naturalny problem: kiedy w grafie dwudzielnym $G=(X,Y;E)$ istnieje pełne skojarzenie $X$ w $Y$?
Na pytanie to odpowiada ważne twierdzenie Halla z 1935 roku.

Twierdzenie 8.7 (P. Hall)   Niech $G=(X,Y;E)$ będzie grafem dwudzielnym. W $G$ istnieje skojarzenie pełne $X$ w $Y$ wtedy i tylko wtedy, jeśli dla każdego podzbioru $A \subset X$ zachodzi $\mid A \mid \leq \mid N_G(A)\mid$.

Dowód. Zacznijmy od skojarzenia z grafem dwudzielnym $G=(X,Y;E)$ sieci $S=(X'\cup Y';A,c)$ w sposób następujący (por. rys. 8.5.1).

-

zbiorem wierzchołków sieci $S$ jest $V= X' \cup Y'$, gdzie

$X'=X \cup \{s\}$

$Y'=Y \cup \{ t \}$

-

$s$ jest źródłem,

-

$t$ odpływem,

przy czym o wierzchołkach $s$ i $t$ zakładamy, że nie należą do $X \cup Y$ i są między sobą różne.

-

Zbiorem łuków sieci $S$ jest $A=\{ (x,y): x=s, y\in X \mbox{ lub } x \in X, xy \in E, \mbox{ lub } x \in Y, y=t\}.$

-

Funkcja przepustowości $c:A \rightarrow {\bf R}$ dana jest wzorem

$$c(x,y) = \left\{ \begin{array}{rrlll} \infty & \mbox{ gdy }... ...y\in X \mbox{ lub } x\in Y \mbox{ i } y=t \end{array} \right.$$

Oczywistym jest, że maksymalny przepływ całkowitoliczbowy w sieci $S$ wyznacza maksymalne skojarzenie w $G$ i na odwrót: maksymalne skojarzenie w $G$ definiuje całkowitoliczbowy przepływ w sieci $S$. Z wniosku (lub ) wynika, że istnieje maksymalny przepływ w $S$ przyjmujący wartości całkowite na wszystkich łukach sieci^8.13. Przypuśćmy wpierw, że dla każdego podzbioru $A \subset X$ zachodzi $\mid N_G(A)\mid \geq \mid A \mid$. Wykażemy, że wtedy istnieje w $S$ przepływ $f$ o wartości $w(f) \geq \mid X \mid$.
Rzeczywiście niech $f$ będzie całkowitoliczbowym przepływem maksymalnym w $S$ i niech $(W,\bar{W})$ będzie przekrojem o przepustowości minimalnej rozdzielającym $s$ od $T$ (na przykład wyznaczonym przez algorytm Forda-Fulkersona).
Oznaczmy $A = X \cap W$ oraz $B=Y \cap W$ (p. rys. 8.5.2).

Zauważmy, że nia ma łuków o początku w $A$ i końcu w $Y-B$, w przeciwnym razie mielibyśmy $c(W,\bar{W})=+\infty$, a więc istnieje przekrój o mniejszej przepustowości, n.p. $W=\{ s\}$^8.14.
Stąd $B \supset N_G(A)$ i

$$c(W,\bar{W}) = \mid X-A\mid + \mid B\mid = \mid X \mid - \mid A \mid + \mid B \mid \geq$$

$$\geq \mid X \mid - \mid A \mid + \mid N_G(A)\mid \geq \mid X \mid$$

Tak więc istnieje przepływ w $S$ o wartości $w(f) \geq \mid X \mid$, a skoro żaden przepływ nie może mieć wartości większej niż $\mid X \mid$, $w(f)=\mid X \mid$.
Łuki o niezeroeym przepływie z $X$ do $Y$ w $S$ wyznaczają oczywiście krawędzie pełnego skojarzenia $X$ w $Y$ w grafie $G$.
Przypuśćmy teraz, że w $G$ istnieje pełne skojarzenie $X$ w $Y$. Wykażemy, że wtedy dla każdego $A \subset X$ zachodzi $\mid A \mid \leq \mid N_G(A)\mid$.
Rzeczywiście, gdyby istnił zbiór $A \subset X$ taki, że $\mid A \mid > \mid N_G(A)\mid$ wtedy w sieci $S$ moglibyśmy wziąć przekrój $(W,\bar{W})$ ze zbiorem $W=\{ s\} \cup A \cup N_G(A)$. Przepustowość tego przekroju wynosi

$$c(W,\bar{W})=\mid X\mid - \mid A \mid + \mid N_G(A)\mid < \mid X \mid$$

Skoro istnieje przekrój rozdzielający o przepustowości mniejszej niż $\mid X \mid$, to w $S$ nie ma przepływu o wartości $\mid X \mid$, czyli w $G$ nie istnieje skojarzenie pełne $X$ w $Y$ - ta sprzeczność kończy dowód twierdzenia Dla grafów dwudzielnych prawdziwe jest następujące twierdzenie.