Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
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.
Każdy ma.
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.
(a) Ten graf składa się z parami rozłącznych cykli parzystej długości.
(b) Wbrew pozorom to nie jest zawsze możliwe.
3. Wykazać, że graf bez cykli ma co najwyżej jedno skojarzenie pełne.
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ź \(vw\) 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.
5. Niech \(n\) będzie liczbą całkowitą dodatnią. Udowodnić, że następujące grafy mają faktoryzację:
(a) \(K_{2n}\) – każdy z \(2n\) 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,\ldots,a_n,b_1,b_2,\ldots,b_n\}\) oraz \(E=\big\{a_ib_j:i,j\in\{1,2,\ldots,n\}\big\}\) (graf dwudzielny pełny).
(a) Nazwijmy wierzchołki \(v_1,v_2,\ldots,v_{2n}.\) Dla \(j=1,2,\ldots,2n-1\) w \(j\)-tym skojarzeniu znajdą się krawędzie \(v_j\sim v_{2n}\) oraz \(v_{j-i}\sim v_{j+i}\) przy \(i=1,2,\ldots,n-1\) (przyjmujemy, że \(v_t=v_{t'}\) dla \(t'\equiv t \pmod{2n-1}\)).
(b) Dla \(j=1,2,\ldots,n\) w \(j\)-tym skojarzeniu znajdą się krawędzie \(a_i\sim b_{i+j}\) przy \(i=1,2,\ldots,n\) (przyjmujemy, że \(b_t=b_{t'}\) dla \(t'\equiv t \pmod n\)).
6. Niech \(n\) będzie całkowite dodatnie. Dany jest \((2n)\)-elementowy zbiór liczb rzeczywistych o nieujemnej sumie elementów. Udowodnić, że ma on co najmniej \(2n-1\) dwuelementowych podzbiorów o nieujemnej sumie elementów.
Niech \(A=\{a_1,a_2,\ldots,a_{2n}\}\) będzie danym zbiorem. Rozważmy faktoryzację grafu pełnego o wierzchołkach \(v_1,v_2,\ldots,v_{2n}.\) Z każdego skojarzenia wybieramy krawędź \(v_iv_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.
Niech \(a_1,\ldots,a_n\) będą dziewczętami, a \(b_1,\ldots,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, \ldots, a_m \sim b_m\) i \(1\le 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,\ldots,a_m\) i dowolny chłopiec \(b\neq b_1,\ldots,b_m\) dla pewnego \(j\in\{1,2,\ldots,m\}\) spełniają relacje \(a\sim b_j\) i \(b\sim a_j.\)
8. Do grupy przedszkolnej uczęszcza \(2n\) 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.
Wystarczy lekko zmodyfikować rozumowanie z poprzedniego zadania.
Uwaga. Można wykazać mocniejszą własność – taki graf musi mieć cykl
przechodzący przez wszystkie wierzchołki. Jest to treść twierdzenia
Diraca.