====== Matematyka Dyskretna (M) - Lista 10. ====== ===== Zadanie 1. ===== ===== Zadanie 2. ===== ====a==== Nie istnieje, z lematu o uściskach dłoni. ====b==== Nie istnieje, ponieważ jeżeli popatrzymy na wierzchołek o stopniu 4, to on ma krawędź z każdym innym. W tym momencie mamy ciąg stopni 1,1,1,1,4. Nie możemy stworzyć 2 krawędzi, aby jeden wierzchołek miał stopień o 2 większy, nie poruszając stopni innych wierzchołków. Nie zrobimy też cyklu, bo to graf prosty. ====c==== Jedyny prosty graf, o takim stopniu wierzchołków, to pięciokąt. Jest tam cykl o długości 5. Mamy twierdzenie mówiące, że każdy cykl w grafie dwudzielnym musi mieć długość parzystą. ===== Zadanie 3. ===== Mamy graf $G$, a w nim wyróżnione $x,y\in V(G):$\\ $\forall a,b\in V(G)\ \ d(x,y) \geq d(a,b)$, no i $d(x,y)>3$\\ Chcemy pokazać, że $\forall a,b \in V(\overline{G})\ .\ d(a,b)\leq 2$.\\ Weźmy dowolne $a,b \in V(\overline{G})$ i rozważmy dwa przypadki:\\ 1° $d(a,b)>1$ w $G$ - wtedy oczywiście $\{a,b\} \not\in E(G)$, a więc $\{a,b\} \in E(\overline{G})$, czyli w $\overline{G}$ jest $d(a,b)=1\leq 2$.\\ 2° $\{a,b\} \in E(G)$. Wiemy, że w $G$ na pewno nie istnieją drogi $x-a-b-y$, $x-b-a-y$, ani tym bardziej $x-a-y$ czy $x-b-y$, gdyż łączyłyby one $x$ z $y$ za pomocą nie więcej niż 3 krawędzi. Wobec tego w $\overline{G}$ musi istnieć po co najmniej jednej krawędzi ze zbiorów: $\{xa,by\},\ \{xb,ay\},\ \{xa,ya\},\ \{xb,yb\}$. I w efekcie powstanie nam droga $a-x-b$ lub $a-y-b$. Tak więc $d(a,b)\leq 2$. ===== Zadanie 4. ===== ===== Zadanie 5. ===== ===== Zadanie 6. ===== Załóżmy nie wprost, że mamy drzewo, w którym istnieje para rozłącznych wierzchołkowo dróg $a-b$ i $c-d$, a także para rozłącznych dróg $a-c$ i $b-d$.\\ Zobaczmy, czy istnieje dokładnie jedna droga z $a$ do $d$ (drzewo to graf spójny bez cykli).\\ Załóżmy, że korzysta ona z drogi $a-b$ (to jest drzewo i z $a$ do $b$ można dojśc dokładnie jedną drogą).\\ Wtedy, nie możemy znaleźć się w $c$ przed osiągnięciem $b$, ponieważ droga $a-b$ jest rozłączna z $c-d$.\\ Z $b$ możemy teraz dojść do $d$, nie przechodząc przez $c$. Możemy iść dalej nie przechodząc już nigdy więcej przez $b$, drogą $d-c$, a następnie $c-a$. Znaleźliśmy się w $a$.\\ Cykl. Sprzeczność. ===== Zadanie 7. ===== ===== Zadanie 8. ===== ===== Zadanie 9. ===== ===== Zadanie 10. ===== ===== Zadanie 11. ===== Wszystkich drzew o rozróżnialnych wierzchołkach jest $n^{n-2}$ (Twierdzenie Cayleya, 1889*), więc dla $n-1$ wierzchołków - $(n-1)^{n-3}$. Czyli weźmy takie $n-1$ wierzchołkowe drzewo (etykiety od $2$ do $n$) i doczepmy do niego wierzchołek o etykiecie "$1$" (na $n-1$ różnych sposobów, bo doczepialmy do wierzchołka). $ \displaystyle P = \frac {(n-1)\cdot(n-1)^{n-3}} {n^{n-2}} $\\ $ \displaystyle \lim_{n\rightarrow \infty} \frac {(n-1)\cdot(n-1)^{n-3}} {n^{n-2}} = \lim_{n\rightarrow \infty} (1 - \frac 1 n)^{n-2} = \frac 1 e$ *http://matmauksw.ovh.org/dyskretna/MAD-w04.pdf, s. 3 ===== Zadanie 12. ===== ===== Zadanie 13. ===== ===== Zadanie 14. ===== Wskażemy odpowiednią ścieżkę definiując ją indukcyjnie. \\ Załóżmy, że istnieje ścieżka o długości $\displaystyle k < r$ tzn. $\displaystyle v_1\to v_2\to\ldots\to v_k$. \\ Wierzchołek $\displaystyle v_k$ ma co najmniej $\displaystyle r$ sąsiadów, musi więc mieć sąsiada $\displaystyle v_{k+1}$ poza $\displaystyle k$-elementowym zbiorem $\displaystyle \left\lbrace v_1,v_2,\ldots,v_k \right\rbrace$.\\ Skonstruowaliśmy więc ścieżkę $\displaystyle v_1\to v_2\to\ldots\to v_k\to v_{k+1}$ odwiedzającą $\displaystyle k+1$ wierzchołków. \\ Powtarzając tę czynność tak długo jak $\displaystyle k< r$ , otrzymujemy $\displaystyle r$-elementową ścieżkę:\\ $\displaystyle v_1\to v_2\to\ldots\to v_r$.\\ Wiemy więc, że ścieżka o możliwie największej długości ma $\displaystyle k\geq r$ wierzchołków.\\ Niech $\displaystyle w_1\to w_2\to\ldots\to w_k$ będzie taką ścieżką.\\ Z jej maksymalności wiemy, że wszyscy sąsiedzi $\displaystyle w_k$ są już na tej ścieżce, bo inaczej można by ją było przedłużyć. \\ Niech więc $\displaystyle w_i$ będzie sąsiadem $\displaystyle w_k$ o najmniejszym indeksie. \\ Ścieżka $\displaystyle w_i\to w_{i+1}\to\ldots\to w_k$ odwiedza $\displaystyle r$ sąsiadów wierzchołka $\displaystyle w_k$, więc jest długości co najmniej równej $\displaystyle r$. \\ Wraz z wierzchołkiem $\displaystyle w_k$ tworzy więc cykl: $\displaystyle w_i\to w_{i+1}\to\ldots\to w_k\to w_i$. o długości co najmniej $\displaystyle r+1$. ===== Zadanie 15. =====