Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Zachęcam Czytelnika, żeby przed przystąpieniem do rozwiązywania zadań zapoznał się z poprzednim kącikiem (nr 69 w \(\Delta_{24}^9\)) oraz z artykułem o twierdzeniu Tutte’a i twierdzeniu Halla \((\star),\) zamieszczonym w niniejszym numerze. Znajdują się w nim definicje takich pojęć i oznaczeń, jak ścieżka powiększająca, graf dwudzielny czy \(\mathcal{O}(G),\) wykorzystywane w poniższych zadaniach. Przypomnijmy również, że graf \(d\)-regularny to taki, w którym stopień każdego wierzchołka jest równy \(d.\)
Zadania
1. Dowieść, że skojarzenie \(M\) w grafie \(G\) można powiększyć wtedy i tylko wtedy, gdy istnieje ścieżka powiększająca \(M\) w grafie \(G\) (twierdzenie Berge’a).
Implikacja (\(\Leftarrow\)) to lemat o ścieżce naprzemiennej z artykułu \((\star)\).
(\(\Rightarrow\)) Niech \(M\) i \(M'\) będą skojarzeniami w grafie \(G,\) przy czym \(|M'|>|M|.\) Rozważyć multigraf będący sumą skojarzeń \(M\) i \(M'\) (podobnie jak w dowodzie twierdzenia Tutte’a w artykule). Można go podzielić na parami rozłączne cykle i ścieżki. Jedna z tych ścieżek ma więcej krawędzi z \(M'\) niż z \(M\) – i to ta ścieżka powiększa skojarzenie \(M.\)
2. Mostem nazywamy taką krawędź \(e\) grafu \(G,\) że graf \(G-e\) ma więcej spójnych składowych niż graf \(G.\) Dowieść, że graf \(3\)-regularny bez mostów ma skojarzenie pełne (twierdzenie Petersena).
Trzeba wykazać, że spełniony jest warunek (T) z artykułu. Niech \(S\subsetneq V\) oraz niech \(N\) będzie nieparzystą spójną składową grafu \(G-S,\) o ile taka istnieje. Niech \(l\) będzie liczbą krawędzi łączących \(N\) i \(S\) w grafie \(G.\) Wiadomo, że \(l>1,\) bo w grafie \(G\) nie ma mostów. Ponadto \(2\nmid l,\) bo stopnie wierzchołków należących do \(N\) oraz ich liczba są nieparzyste. Wynika stąd, że \(l\ge 3.\) Suma stopni wierzchołków należących do \(S\) wynosi \(3|S|,\) więc składowych nieparzystych jest nie więcej niż \(|S|.\)
3. Udowodnić, że drzewo ma co najwyżej jedno skojarzenie pełne.
Niech \(M_1\) i \(M_2\) będą skojarzeniami pełnymi w drzewie \(T.\) Rozważmy multigraf będący sumą \(M_1\) i \(M_2\) (podobnie jak w dowodzie twierdzenia Tutte’a). Jest on sumą parami rozłącznych cykli. Każdy z nich ma długość \(2,\) bo w grafie \(T\) nie ma cykli. Stąd \(M_1=M_2.\)
4. Dowieść, że drzewo \(T=(V,E)\) o co najmniej dwóch wierzchołkach ma skojarzenie pełne wtedy i tylko wtedy, gdy \[\label{KPO-Drzewo}\tag{D} \mathop{\forall}_{v\in V} \mathcal{O}(T-v)=1.\]
(\(\Rightarrow\)) Warunek (D) to warunek (T) osłabiony dodatkowym założeniem \(|S|=1,\) więc teza wynika z twierdzenia Tutte’a.
(\(\Leftarrow\)) Dowód będzie indukcyjny ze względu na \(|V|.\) Dla \(|V|=2\) teza
jest oczywista. Załóżmy, że spełniony jest warunek (D). Niech \(u\in V\) będzie
stopnia \(1\) (jeśli \(|V|\ge 2,\) to drzewo ma taki wierzchołek) i niech
\(v\) będzie jedynym sąsiadem \(u.\) Graf \(T-v\) ma spójną składową złożoną z pojedynczego wierzchołka \(u\) oraz być może jakieś jeszcze spójne
składowe, które zgodnie z (D) muszą być parzyste. Niech
\(S\) będzie jedną z nich; oczywiście \(S\) jest drzewem i ma mniej wierzchołków niż \(T.\) Niech \(R\) będzie spójną składową grafu \(S-w,\) a \(R'\) – zawierającą ją
spójną składową grafu \(T-w.\) Jeśli \(v\not\in {R'},\) to \(R=R',\) a jeśli \(v\in R,\) to
\(R\) i \(R'\) są tej samej parzystości. Z tego wynika, że składowa \(S\) spełnia
warunek (D), więc ma pełne skojarzenie na mocy założenia indukcyjnego.
Analogicznie rozumujemy dla pozostałych spójnych składowych. Te skojarzenia wraz
z krawędzią \(uv\) dają pełne skojarzenie w drzewie \(T.\)
5. Znaleźć błąd w następującym rozumowaniu:
Wykażemy, że graf \(G=(V,E),\) mający cykl Hamiltona, ma skojarzenie pełne. Weźmy dowolny \(S\subseteq V.\) Ponieważ wszystkie wierzchołki grafu \(G\) leżą na jednym cyklu, graf \(G-S\) ma najwyżej \(|S|\) spójnych składowych, więc tym bardziej \(\mathcal{O}(G-S)\le|S|.\) Graf \(G\) spełnia zatem warunek Tutte’a, a więc ma skojarzenie pełne.
Dla nieparzystych \(|V|\) mamy \(\mathcal{O}(G-\emptyset)=1\nleqslant|\emptyset|.\)
6. Niech \(a,b\ge3\) będą liczbami naturalnymi. Z \(2n\) klocków o wymiarach \(a\times b\times 1\) zbudowano prostopadłościan o wysokości \(2.\) Dowieść, że w ten prostopadłościan można wbić pionowo \(n\) gwoździ w taki sposób, by każdy z klocków został przebity.
Klocki tworzą dwie warstwy. Rozważmy graf dwudzielny o dwupodziale \((A,B),\) w którym zbiór \(A\) stanowią klocki jednej z warstw, a \(B\) – drugiej. Krawędź \(ab\) istnieje wtedy i tylko wtedy, gdy klocek \(a\in A\) oraz \(b\in B\) mają niezerową wspólną powierzchnię; równoważnie – gdy można wbić gwóźdź przebijający jednocześnie klocki \(a\) i \(b.\) Graf ten spełnia warunek (H) dla zbioru \(A,\) więc ma skojarzenie nasycające zbiór \(A.\) Jest to skojarzenie pełne, gdyż \(|A|=|B|.\)
7. Rozważmy graf dwudzielny o dwupodziale \((A,B),\) w którym \[\min_{a\in A}\deg(a) \ge \max_{b\in B}\deg(b).\] Dowieść, że ten graf ma skojarzenie nasycające zbiór \(A\) (uogólnione twierdzenie o małżeństwach).
Istnieje taka liczba naturalna \(d,\) że \(\deg(a)\ge d \ge \deg(b)\) dla wszystkich \(a\in A\) oraz \(b\in B.\) Dla niepustego \(S\subseteq A\) mamy \(d|N(S)| \ge \sum_{w\in N(S)}\deg(w) = \sum_{v\in S}\deg(v) \ge d|S|,\) więc zachodzi warunek (H).
8. Dowieść, że niepusty regularny graf dwudzielny jest sumą krawędziowo rozłącznych pełnych skojarzeń.
Rozważmy \(d\)-regularny graf dwudzielny \(G\) o dwupodziale \((A,B).\) Ze względu na regularność mamy \(|A|=|B|.\) Na mocy poprzedniego zadania graf \(G\) ma skojarzenie pełne \(M.\) Graf \(G',\) powstały przez usunięcie z \(G\) krawędzi należących do \(M,\) jest \((d-1)\)-regularny, więc wystarczy skorzystać z indukcji. Dla \(d=1\) twierdzenie jest oczywiste.
9. Niech \(\Delta\) będzie największym stopniem wierzchołka w grafie dwudzielnym \(G.\) Dowieść, że graf \(G\) jest sumą \(\Delta\) rozłącznych krawędziowo skojarzeń (twierdzenie Königa).
Wystarczy wykazać, że \(G\) jest podgrafem pewnego \(\Delta\)-regularnego grafu dwudzielnego, i skorzystać z poprzedniego zadania. Rozważmy graf dwudzielny \(G=G_0\) o dwupodziale \((A_0,B_0).\) Graf \(G_{t+1}\) o dwupodziale \((A_{t+1},B_{t+1})\) będziemy tworzyć z grafu \(G_t\) o dwupodziale \((A_t,B_t)\) w następujący sposób. Niech \(G_t'\) o dwupodziale \((A_t',B_t')\) będzie kopią grafu \(G_t.\) Przez \(\delta_t\) oznaczmy najmniejszy stopień wierzchołka w grafie \(G_t,\) przy czym \(\delta=\delta_0.\) W grafie \(G_{t+1}\) określamy: \(A_{t+1}=A_t\cup B_t',\) \(B_{t+1}=A_t'\cup B_t.\) Krawędzie prowadzimy tak, jak były w grafach \(G_t\) i \(G_t',\) a dodatkowo łączymy wszystkie wierzchołki stopnia \(\delta_t\) z grafu \(G_t\) z ich odpowiednikami w grafie \(G_t'.\) Jest jasne, że \(\delta_{t+1}=\delta_t+1.\) Graf \(G_{\Delta-\delta}\) jest poszukiwanym grafem.
10. Niech \(n>m\) będą liczbami naturalnymi. W tablicy kwadratowej \(n\times n\) wybrano \(m\) wierszy, a następnie w każdym z nich wpisano, w pewnej kolejności, liczby \(1,2,\ldots,n.\) Wiadomo, że w każdej kolumnie występuje \(m\) różnych liczb. Wykazać, że można uzupełnić tę tablicę do kwadratu łacińskiego \(n\times n.\)
Niech \(A=\{a_1,a_2,\ldots,a_n\}\) i \(B=\{b_1,b_2,\ldots,b_n\}.\) W grafie o dwupodziale \((A,B)\) istnieje krawędź \(a_ib_j\) wtedy i tylko wtedy, gdy w \(i\)-tej kolumnie tablicy z zadania jest liczba \(j.\) Wówczas każdy wiersz odpowiada za skojarzenie pełne w grafie \(K_{n,n}\) (każdy wierzchołek z \(A\) połączony z każdym z \(B\)). Do uzupełnienia pozostaje podział na skojarzenia pełne w grafie dwudzielnym \((n-m)\)-regularnym, a taki istnieje na mocy zadania 8.