Lista 14 - HackMD

###### tags: `Matematyka Dyskretna M` # Lista 14 ## 2 Dowód przeprowadzę przez indukcję po k. **1$^\circ$** dla k=1 Wtedy mamy 2 wierzchołki połączone krawędzią, co daje jedną ścieżkę. **2$^\circ$** Załóżmy, że dla k zachodzi, sprawdźmy dla k+1: Wtedy do każdego wierzchołka dopisujemy jakiś bit 0 lub 1. Inaczej mówiąc z każdego ciągu k-bitowego robimy 2 ciągi k+1-bitowe. Weźmy dwa dowolne wierzchołki i nazwijmy je $v$ i $u$. Rozpatrzmy teraz przypadki: **1$^\circ$** rozpatrujemy drogi między wierzchołkami $v$ i $u$, które zostały stworzone z jednego ciągu: wtedy mamy k dróg o długości 3. $v$ jest połączony z wierzchołkiem, który ma różny bit na pozycji innej niż ostatnia, ten jest połączony z kolejnym, który ma inny ostatni bit, a ten jest połączony z $w$. $k+1$ drogą jest bezpośrednia krawędź między tymi wierzchołkami. **2$^\circ$** rozpatrujemy drogi między wierzchołkami, które nie zostały stworzone z jednego ciągu: W przypadku jak mają ostatnie bity różne. Weźmy z założenia indukcyjnego k-1 dróg rozłącznych, które wyglądają w następujący sposób. Weźmy ostatni bit $v$ i nazwijmy go b. Bit przeciwny będę oznaczał jako ~b. $v$ jest połączone z pierwszym wierzchołkiem drogi z założenia indukcyjnego, następnie jest ona połączona z wierzchołkiem z końcowym bitem równym ~b, który idzie drogą z założenia indukcyjnego aż do $w$. Mamy więc $k-1$ rozłączonych dróg ostatnie dwie powstają z $k$-tej drogi z założenia inducyjnego. $k$-ta droga to taka, która przechodzi ostatnią drogą z założenia indukcyjnego, która ma ostatni bit równy $b$, a $k+1$ po tej drodze z ostatnimi bitami ~b. W przypadku gdy mają takie same bity. $k$ dróg uzyskujemy z założenia indukcyjnego. $k+1$ drogę uzyskujemy przechodząc dowolną z tych ścieżek na przeciwnym końcowym bicie. Na podstawie indukcji matematycznej pokazałem, że teza zachodzi. ## 3 ### a) Dowód przeprowadzę przez indukcję po k. **1$^\circ$** dla k=2 Mamy jedną krawędź więc teza zachodzi. **2$^\circ$** Załóżmy, że dla k zachodzi, sprawdźmy dla k+1: Dodajemy wierzchołki i łączymy je z sąsiadami, co może dać minimalnie cykl długości 4, więc nie ma możliwości dostania trójkąta, a następnie łączymy nowo powstałe wierzchołki z kolejnym-nowym wierzchołkiem, a wiemy, że między nowo powstałymi wierzchołkami nie było połączeń, więc nie przyczyni się to do powstania trójkąta. Na podstawie indukcji matematycznej pokazałem, że teza zachodzi. ### b) Dowód przeprowadzę przez indukcję po k. **1$^\circ$** dla k=2 Mamy 2 wierzchołki i 2 kolory, co daje możliwość ich pokolorowania. **2$^\circ$** Załóżmy, że dla k zachodzi, sprawdźmy dla k+1: Przy tworzeniu $M_{k+1}$ zauważmy, że $v'_i$ łączymy z sąsiadami $v_i$, czyli każdy taki $v'_i$ można pokolorować kolorem $v_i$ (korzystając z założenia indukcyjnego), następnie $w$ kolorujemy nowym kolorem, czyli pokolorwaliśmy $M_{k+1}$ $k + 1$ kolorami. Na podstawie indukcji matematycznej pokazałem, że teza zachodzi. ## 6 Dodajmy $n-k$ chłopców znanych przez wszystkie dziewczyny. Wtedy z twierdzenia Halla wiemy, że warunkiem koniecznym i dostatecznym aby $n$ dziewczyn (każda dziewczyna) mogło sobie znaleźć męża jest, aby każda podgrupa dziewcząt licząca $r$ osób znała co najmniej $r$ chłopców. Po odjęciu tych $n-k$ chłopców znanych przez wszystkie dziewczyny dostajemy równoważność, że warunkiem koniecznym i dostatecznym, aby $n-(n-k)=k$ dziewczyn mogło sobie znaleźć męża jest, aby każda podgrupa dziewcząt licząca $r$ osób znała co najmniej $r-(n-k)=k+r-n$ chłopców, co należało pokazać. ## 7 Weźmy wszystke wierzchołki chłopców i "rozdzielmy" je na 4 zachowując zasadę, że jak jakaś dziewczyna znała tego chłopca to będzie znała wszystkie 4 wierzchołki tego chłopca. Z twierdzenia Halla wiemy, że warunkiem koniecznym i wystarczającym, aby każda dziewczyna mogła sobie znaleźć męża jest, aby każdy podzbiór tych dziewczyn był $\leq$ liczbie rozdzielonych chłopców, których znają. Po "scaleniu" wierzchołków chłopców równoważne jest zdanie, że warunkiem koniecznym i wystarczającym jest aby każda dziewczyna mogła sobie znaleźć męża, to każdy podzbiór tych dziewczyn musi być $\leq$ liczbie wierzchołków mężczyzn podzielonych przez 4 ($\frac k4$), których znają, co należało pokazać. ## 8 Indukcja po liczbie wierzchołków **1$^\circ$** **dla n=1** Mamy nieparzystą liczbę wierzchołków, więc pełne skojarzenie nie istnieje. **dla n=2** Mamy możliwość położenia tylko jednej krawędzi, co daje pełne skojarzenie. **2$^\circ$** Załóżmy, że dla $n$ teza zachodzi, sprawdźmy dla $n+2$ Weźmy drzewo mające $n+2$ wierzchołków. Weźmy dowolny liść. Jeżeli w takim drzewie istniałoby pełne skojarzenie to musiałby być połączony z rodzicem krawędzią w tym drzewie (w przeciwnym wypadku nie byłoby tam pełnego skojarzenia, więc wtedy teza zachodzi). Po usunięciu liścia i jego rodzica z tezy indukcyjnej wiemy, że jest tam maksymalnie jedno skojarzenie, więc po dodaniu tych dwóch wierzchołków, również będzie tam maksymalnie 1 pełne skojarzenie. Na podstawie indukcji matematycznej pokazałem, że teza zachodzi. ## 10 Weźmy dowolny podzbiór wierzchołków z jednej grupy wierzchołków w dowolnym grafie dwudzielnym d-regularnym i nazwijmy go $K$. Skoro jest on d-regularny to z każdego wierzchołka tej grupy wychodzi d krawędzi do drugiej grupy oraz każdy wierzchołek z drugiej grupy może "przyjąć" maksymalnie d krawędzi. Zbiór wszystkich wierzchołków, które są połączone bezpośrednio krawędzią z dowolnym wierzchołkiem z $K$ nazwijmy $W$. Zauważmy, że zachodzi nierówność $|W| \geq|K|$. Załóżmy nie wprost, że $|K| > |W|$. Z $K$ wychodzi dokładnie $d\times|K|$ krawędzi do $W$, co daje sprzeczność. Ponieważ $|W|$ może maksymalnie "przyjąć" $d\times |W|$ krawędzi (z założenia $|K| > |W|$). Czyli $|W| \geq|K|$. Z twierdzenia Halla wiemy, że w takim grafie znajduje się pełne skojarzenie, co kończy dowód. ## 11 Weźmy dowolny graf 3-regularny, w którym znajduje się cykl Hamiltona. Z lematu o uściskach dłoni wiemy, że taki graf ma parzystą liczbę wierzchołków. Przejdźmy tym cyklem jednocześnie kolorując każdą krawędź na zmianę kolorami. W taki sposób zużyliśmy dwa kolory i każdy wierzchołek ma po jednej wychodzącej krawędzi. W takiej sytuacji wystarczy, że pokolorujemy te pozostałe na trzeci kolor. Takim sposobem udało się pokolorować krawędzie takiego grafu 3 kolorami. Nie wystarczą nam 2 kolory, ponieważ w każdym takim grafie z wierzchołków wychodzą 3 krawędzie, więc z zasady szufladkowej Dirichleta musiałyby istnieć takie 2 krawędzie, które mają ten sam kolor, a taka sytuacja nie może się zdażyć. ## 13 Z każdego wierzchołka wychodzi $n-1$ krawędzi, więc indeks chromatyczny musi być $\geq n-1$ Dla $n$ nieparzystego: Weźmy taki graf i zauważmy i pokolorujmy go minimalną liczbą kolorów. Weźmy podgraf, który zawiera wszystkie wierzchołki i krawędzie pokolorowane jednym kolorem. Zauważmy, że taki graf ma maksymalnie $\lfloor\frac n2\rfloor$ krawędzi. Graf pełny ma krawędzi $\frac{n(n-1)}{2}$. Patrząc, że każdy taki podgraf reprezentuje jeden kolor to taki graf pełny nie można pokolorować mniejszą ilośćią kolorów niż $\frac{n(n-1)}{2\times\lfloor\frac n2\rfloor}=\frac{n(n-1)}{n-1}=n$ Dla dowolnego n: Pokolorujmy taki graf $n$ kolorami w taki sposób, że pomiędzy wierzchołkiem $v_i$ i $v_k$, jest krawędź ($v_i$,$v_k$) pokolorowana na kolor $i+k$ (jeżeli $i+k \geq n$ to wtedy ta krawędź jest pokolorowana kolorem $i+k-n$). Wyjątkiem jest kolorowanie krawędzi pomiędzy wierzchołkiem $v_0$. Wtedy krawędź $(v_0, v_i)$ jest pokolorowana na kolor $2\times i$ (chyba, że jak wyżej $2\times i \geq n$ wtedy na kolor $2\times i - n$) Czyli dowolny graf $K_n$ można pokolorować $n$ kolorami. Dla $n$ nieparzystego kończy to dowód. Dla $n$ parzystego: Spróbujmy dodać jeden wierzchołek do takiego grafu pokolorowanego wyżej. Zauważmy, że wierzchołek $v_i$ nie jest połączony z żadnym innym wierzchołkiem krawędzią pokolorowaną kolorem $i$. Więc połączmy go z nowo dodanym wierzchołkiem krawędzią pokolorowaną kolorem $i$. Wtedy nowy wierzchołek jest połączony z każdym innym, zachowując zasadę kolorowania krawędzi. Czyli dla $n$ parzystego pokolorowaliśmy taki graf używając $n-1$ kolorów, co kończy dowód.