Delta 9/2024

Skojarzenia – część 1

Bartłomiej Bzdęga

Zachęcam Czytelnika, który jeszcze tego nie zrobił, do zapoznania się z poprzednim kącikiem – są tam wprowadzone podstawowe definicje i oznaczenia, których będę tu używał. Ponadto, jeśli wierzchołki $v$ i $w$ danego grafu są połączone krawędzią, będziemy pisać $v \sim w .$ Graf nazwiemy $d$ -regularnym, jeśli wszystkie jego wierzchołki mają stopień $d .$

Skojarzeniem nazywamy każdy $1$ -regularny podgraf danego grafu. Mówiąc prościej – skojarzenie tworzy kilka par wierzchołków, przy czym każda para jest połączona krawędzią. Jeśli do skojarzenia należą wszystkie wierzchołki danego grafu, to nazywamy je pełnym albo doskonałym.

Pokolorujmy każdą krawędź grafu na jakiś kolor, przy czym krawędzie mające wspólny wierzchołek muszą mieć inne kolory. Takie kolorowanie nazywamy właściwym. Krawędzie każdego z kolorów tworzą skojarzenie. Jeśli każdemu kolorowi odpowiada skojarzenie pełne, to mówimy, że te skojarzenia tworzą faktoryzację grafu.

Zadania

1. W każdym z wielościanów foremnych znajdź skojarzenie pełne albo wykaż, że takiego nie ma.

Wskazówka

2. Klasa licząca $n$ osób otrzymała zestaw $n$ zadań domowych. Chcemy zorganizować lekcję w taki sposób, by każdy uczeń pokazał przy tablicy rozwiązanie jednego zadania, które zrobił w domu, ale każdy uczeń ma zaprezentować rozwiązanie innego zadania. Rozstrzygnąć, czy zawsze jest to możliwe, jeśli:

(a) każdy uczeń rozwiązał dokładnie dwa zadania, a każde zadanie zostało rozwiązane przez dokładnie dwóch uczniów;
(b) każdy uczeń rozwiązał co najmniej dwa zadania, a każde zadanie zostało rozwiązane przez co najmniej dwóch uczniów.

Wskazówka

3. Wykazać, że graf bez cykli ma co najwyżej jedno skojarzenie pełne.

Wskazówka

Niech $G = (V, E)$ będzie danym grafem. Przeprowadzimy indukcję ze względu na $| E | .$ Jeśli $| E | = 0,$ to teza zachodzi. W przeciwnym razie graf ma wierzchołek $v$ stopnia $1$ (np. koniec najdłuższej ścieżki); niech $w$ będzie jedynym sąsiadem wierzchołka $v .$ Krawędź $v w$ musi należeć do skojarzenia. W grafie $G^{'},$ powstałym przez usunięcie z grafu $G$ wierzchołków $v$ i $w$ oraz wszystkich krawędzi, które z nich wychodzą, istnieje co najwyżej jedno skojarzenie pełne na mocy założenia indukcyjnego.

4. Udowodnić, że dla każdego $c$ istnieje graf, który ma dokładnie jedno skojarzenie pełne oraz co najmniej $c$ cykli.

Wskazówka

5. Niech $n$ będzie liczbą całkowitą dodatnią. Udowodnić, że następujące grafy mają faktoryzację:

(a) $K_{2 n}$ – każdy z $2 n$ wierzchołków jest połączony z każdym innym (graf pełny);
(b) $K_{n, n}$ – taki, w którym można zapisać $V = {a_{1}, a_{2}, \dots, a_{n}, b_{1}, b_{2}, \dots, b_{n}}$ oraz $E = {a_{i} b_{j} : i, j \in {1, 2, \dots, n}}$ (graf dwudzielny pełny).

Wskazówka

(a) Nazwijmy wierzchołki $v_{1}, v_{2}, \dots, v_{2 n} .$ Dla $j = 1, 2, \dots, 2 n - 1$ w $j$ -tym skojarzeniu znajdą się krawędzie $v_{j} \sim v_{2 n}$ oraz $v_{j - i} \sim v_{j + i}$ przy $i = 1, 2, \dots, n - 1$ (przyjmujemy, że $v_{t} = v_{t^{'}}$ dla $t^{'} \equiv t (\mod 2 n - 1)$ ).
(b) Dla $j = 1, 2, \dots, n$ w $j$ -tym skojarzeniu znajdą się krawędzie $a_{i} \sim b_{i + j}$ przy $i = 1, 2, \dots, n$ (przyjmujemy, że $b_{t} = b_{t^{'}}$ dla $t^{'} \equiv t (\mod n)$ ).

6. Niech $n$ będzie całkowite dodatnie. Dany jest $(2 n)$ -elementowy zbiór liczb rzeczywistych o nieujemnej sumie elementów. Udowodnić, że ma on co najmniej $2 n - 1$ dwuelementowych podzbiorów o nieujemnej sumie elementów.

Wskazówka

Niech $A = {a_{1}, a_{2}, \dots, a_{2 n}}$ będzie danym zbiorem. Rozważmy faktoryzację grafu pełnego o wierzchołkach $v_{1}, v_{2}, \dots, v_{2 n} .$ Z każdego skojarzenia wybieramy krawędź $v_{i} v_{j},$ dla której suma $a_{i} + a_{j}$ jest największa.

7. W klasie maturalnej jest $n$ chłopców i $n$ dziewcząt, niektórzy się przyjaźnią i wszystkie przyjaźnie są odwzajemnione. Wiadomo, że każdy ma co najmniej $n / 2$ przyjaciół płci przeciwnej. Dowieść, że ta klasa może zatańczyć na studniówce poloneza w taki sposób, żeby w każdej z $n$ par tańczyli zaprzyjaźnieni dziewczyna i chłopak.

Wskazówka

Niech $a_{1}, \dots, a_{n}$ będą dziewczętami, a $b_{1}, \dots, b_{n}$ – chłopcami. Zacznijmy od dowolnej zaprzyjaźnionej pary. Powiedzmy, że mamy już pary, bez straty ogólności, $a_{1} \sim b_{1}, \dots, a_{m} \sim b_{m}$ i $1 \leq m < n .$ Jeśli którakolwiek z pozostałych dziewcząt przyjaźni się z którymkolwiek z pozostałych chłopców, to mamy kolejną parę. W przeciwnym razie dowolna dziewczyna $a \neq a_{1}, \dots, a_{m}$ i dowolny chłopiec $b \neq b_{1}, \dots, b_{m}$ dla pewnego $j \in {1, 2, \dots, m}$ spełniają relacje $a \sim b_{j}$ i $b \sim a_{j} .$

8. Do grupy przedszkolnej uczęszcza $2 n$ dzieci. Każde dziecko ma w tej grupie co najmniej $n$ przyjaciół, przy czym relacja bycia przyjacielem jest symetryczna. Udowodnić, że grupa ta może pójść na wycieczkę parami tak, żeby każdy szedł w parze ze swoim przyjacielem.

Wskazówka