====== Matematyka Dyskretna (M) - Lista 9. ======

===== Zadanie 1. =====
{{:matematyka_dyskretna:8.1.jpeg|}}
Legenda:\\
w - wolf (wilk)\\
c - cabbage (kapusta)\\
g - goat (koza)\\
| - rzeka

===== Zadanie 2. =====
http://img101.imageshack.us/img101/6497/61717053zc2.jpg

===== Zadanie 3. =====
http://img101.imageshack.us/img101/6497/61717053zc2.jpg

===== 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. =====
{{:matematyka_dyskretna:8.5.jpeg|}}

===== Zadanie 6. =====
http://img381.imageshack.us/img381/5295/48503512hi0.jpg

===== 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)

===== Zadanie 13. =====
http://img101.imageshack.us/img101/6799/37952967jk3.jpg

===== Zadanie 14. =====
===== Zadanie 15. =====