Matematyka Dyskretna (M) - Lista 9.
Zadanie 1.
Legenda:
w - wolf (wilk)
c - cabbage (kapusta)
g - goat (koza)
Zadanie 2.
Zadanie 3.
Zadanie 4.
Z handshake lemma wiemy, że suma stopni wierzchołków musi być parzysta.
Wiemy też, że jak jakiś wierzchołek ma stopień n to musi istniec n wierzchołków o stopniu conajmniej jeden(to sie odpowiednia zwiększa, jak mamy wiecej n stopniowych wierzchołków.
3 wierzchołki
Jedyne parzyste sumy stopni wierzchołków mniejszych lub równych 2:
(0,0,0)
(0,1,1)
(0,2,0) odpada, bo nie ma drugiego wierzchołka, do którego ten ze stopniem 2 miałby krawędź
(2,1,1)
(2,2,0) odpada, bo nie ma dwóch wierzchołków, do którego ten ze stopniem 2 miałby krawędzie
(2,2,2)
Więc są 4.
4 wierzchołki
Jedyne parzyste sumy stopni wierzchołków mniejszych lub równych 3:
(0,0,0,0)
(0,0,1,1)
(0,0,0,2)
(0,0,2,2) odpada
(0,1,1,2)
(1,1,1,1)
(0,0,3,1) odpada
(2,2,1,1)
(2,2,2,0)
(3,3,0,0) odpada
(3,1,2,0) odpada
(3,1,1,1)
(2,2,2,2)
(3,1,3,1) odpada
(3,3,3,1) odpada
(3,3,2,2)
(3,3,3,3)
Jest ich 11
Zadanie 5.
Zadanie 6.
Zadanie 7.
Zadanie 8.
Graf dwudzielny ma 2 grupy wierzchołków, które nie mają wspólnych krawędzi wewnątrz grup.
n elementowy graf G dzielimy na:
A - grupę a elementową,
B - grupę n-a elementową.
Maksymalna ilość krawędzi to |V(A)|\cdot|V(B)|, czyli ilość wierzchołków A razy ilość wierzchołków B.
f(a) = (n-a)a = na - a^2
Ta funkcja ma 2 miejsca zerowe:
a_0 = 0
a_1 = n
Parabola ramionami w dół, więc maksimum tej funkcji znajduje się w \frac 1 2 n.
Dla parzystych n:
a=\frac 1 2 n, bo tak uzyskamy najwięcej krawędzi
E(G)= (n-\frac 1 2 n)\frac 1 2 n = \frac {n^2} 4 = \lfloor \frac {n^2} 4 \rfloor
Dla nieparzystych n:
a=\lfloor \frac 1 2 n \rfloor
E(G)=(n-\lfloor \frac 1 2 n \rfloor)\lfloor \frac 1 2 n \rfloor=
\lceil \frac 1 2 n \rceil \cdot \lfloor \frac 1 2 n \rfloor=
(\frac 1 2 n + \frac 1 2) \cdot (\frac 1 2 n - \frac 1 2 )=
\frac {n^2} 4 - \frac 1 4
n^2 jest nieparzysta, więc nigdy nie jest podzielna przez 4 bez reszty, z tego wynika że:
\lfloor \frac {n^2} 4 - \frac 1 4 \rfloor = \lfloor \frac {n^2} 4 \rfloor
Zadanie 9.
Rozważmy 2 przypadki:
G jest spójny. Zachodzi trywialnie.
G nie jest spójny.
To znaczy, ze w grafie istnieja 2 grupy wierzchołków A i B, że nie istnieje żadna krawędź w postaci \{a,b\} gdzie a \in A \wedge b \in B.
Czyli w \hat{G} istnieja wszystkie możliwe krawędzie, które są w postaci \{a,b\} gdzie a \in A \wedge b \in B.
Weźmy dowolne a \in A i b \in B.
a ma krawędzie z każdym elementem z B. b ma krawędzie z każdym elementem z A. W szczególności oba są incident z krawędzią \{a,b\}. Więc da sie dojść z każdego punktu do każdego, bo jeżeli chcemy dojść z punktu w A do punktu w B to istnieje bezpośrednia krawędź, a jeśli z punktu w A do punktu w A to przechodzimy do wczesniej wybranego punktu b (on ma krawędź z każdym punktem z A) i potem z b do naszego docelowego punktu. Analogicznie pozostałe przypadki.
Zadanie 10.
Zadanie 11.
Niech istnieją dwie najdłuższe drogi rozłączne, wtedy z tego, że jest spójny jest jakieś połączenie pomiędzy tymi drogami (długości e) i niech to połączenie dzieli długości tych dróg odpowiednio na a+b i c+d. BSO zakładamy, że a⇐b i c⇐d czyli 2a ⇐ a+b ⇐ c+d ⇐ 2d, stąd a+b ⇐ b+d < b+d+e. Sprzeczność bo nie wybraliśmy w takim razie dwóch najdłuższych dróg. (src: yebood)
Zadanie 12.
http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_12:_Grafy (twierdzenie 12.2)
