Delta 10/2024

Skojarzenia – część 2

Bartłomiej Bzdęga

Zachęcam Czytelnika, żeby przed przystąpieniem do rozwiązywania zadań zapoznał się z poprzednim kącikiem (nr 69 w $Δ_{24}^{9}$ ) oraz z artykułem o twierdzeniu Tutte’a i twierdzeniu Halla $(⋆),$ zamieszczonym w niniejszym numerze. Znajdują się w nim definicje takich pojęć i oznaczeń, jak ścieżka powiększająca, graf dwudzielny czy $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).

Wskazówka

Implikacja ( $\Leftarrow$ ) to lemat o ścieżce naprzemiennej z artykułu $(⋆)$ .
( $\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).

Wskazówka

Trzeba wykazać, że spełniony jest warunek (T) z artykułu. Niech $S ⊊ 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 ∤ l,$ bo stopnie wierzchołków należących do $N$ oraz ich liczba są nieparzyste. Wynika stąd, że $l \geq 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.

Wskazówka

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 $\begin{matrix} (D) & \underset{v \in V}{\forall} O (T - v) = 1. \end{matrix}$

Wskazówka

( $\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 | \geq 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 \notin 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ą $u v$ 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 $O (G - S) \leq | S | .$ Graf $G$ spełnia zatem warunek Tutte’a, a więc ma skojarzenie pełne.

Wskazówka

Dla nieparzystych $| V |$ mamy $O (G - \emptyset) = 1 ⪇ | \emptyset | .$

6. Niech $a, b \geq 3$ będą liczbami naturalnymi. Z $2 n$ 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.

Wskazówka

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ź $a b$ 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) \geq max_{b \in B} \deg (b) .$ Dowieść, że ten graf ma skojarzenie nasycające zbiór $A$ (uogólnione twierdzenie o małżeństwach).

Wskazówka

Istnieje taka liczba naturalna $d,$ że $\deg (a) \geq d \geq \deg (b)$ dla wszystkich $a \in A$ oraz $b \in B .$ Dla niepustego $S \subseteq A$ mamy $d | N (S) | \geq \sum_{w \in N (S)} \deg (w) = \sum_{v \in S} \deg (v) \geq d | S |,$ więc zachodzi warunek (H).

8. Dowieść, że niepusty regularny graf dwudzielny jest sumą krawędziowo rozłącznych pełnych skojarzeń.

Wskazówka

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 $Δ$ będzie największym stopniem wierzchołka w grafie dwudzielnym $G .$ Dowieść, że graf $G$ jest sumą $Δ$ rozłącznych krawędziowo skojarzeń (twierdzenie Königa).

Wskazówka

Wystarczy wykazać, że $G$ jest podgrafem pewnego $Δ$ -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 $δ_{t}$ oznaczmy najmniejszy stopień wierzchołka w grafie $G_{t},$ przy czym $δ = δ_{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 $δ_{t}$ z grafu $G_{t}$ z ich odpowiednikami w grafie $G_{t}^{'} .$ Jest jasne, że $δ_{t + 1} = δ_{t} + 1.$ Graf $G_{Δ - δ}$ 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, \dots, 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 .$

Wskazówka

Niech $A = {a_{1}, a_{2}, \dots, a_{n}}$ i $B = {b_{1}, b_{2}, \dots, b_{n}} .$ W grafie o dwupodziale $(A, B)$ istnieje krawędź $a_{i} b_{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.