###### tags: `Matematyka Dyskretna M`

# Lista 9

## 1

Najpierw mamy kozę na łodzi. Odstawiamy ją na drugi brzeg. Podjeżdżamy po kapustę(możemy również pójść inną drogą) zostawiamy ją na drugim brzegu jednocześnie biorąc kozę ze sobą. Zostawiamy kozę na pierwszym brzegu jednocześnie biorąc wilka. Zostawiamy wilka na drugim brzegu. Wracamy po kozę i zostawiamy ją na drugim brzegu. Takim sposobem mamy kapustę, kozę i wilka na drugim brzegu.


## 2
### a)
$|G|=|G_x|\times|O_x|$

$|O_x| = 4$ ponieważ x możemy "przenieść" na 4 wierzchołki, które oznaczyłem na czerwono poniżej.

$G_x=4$
Ponieważ, nie ruszając x mamy {(1,2), (4,5), (1,2) oraz (4,5), identyczność}, a zbiór ten ma moc 4.


### b)


$|O_x|=8$, bo mamy graf, w którym każdy wierzchołek ma ten sam stopień, więc nasze |O_x| jest równe liczbie wierzchołków.

$|G_x| = 3!=6$, ponieważ mamy 3 sąsiadów, których możemy permutować jak chcemy (reszta jest zależna od nich).

$|G|=|G_x|\times|O_x|=8\times6=48$

## 3


$|O_x|=10$, bo mamy graf, w którym każdy wierzchołek ma ten sam stopień, więc nasze |O_x| jest równe liczbie wierzchołków.

$|G_x| = 3!\times 2=12$, ponieważ x ma 3 sąsiadów, których możemy permutować oraz możemy zauważyć, że możemy również zamienić sąsiadów jednego z sąsiada x (nie będącego x), a reszta jest już zależna od poprzednich permutacji. Co daje nam $|G_x| = 3!\times2 = 12$

$|G|=|G_x|\times|O_x|=10\times12=120$

## 4
Maksymalna liczba krawędzi dla grafu o 3 wierzchołkach równa jest $\frac{3\times 2}{2}=3$
Czyli narysujmy wszystkie takie grafy, które mają maksymalnie 3 krawędzie oraz dokładnie 3 wierzchołki.


Jest ich dokładnie 4.
Jak byśmy spróbowali narysować piąty taki graf, to zależnie ile byśmy dobrali krawędzi w nim, byłby on identyczny z dokładnością do izomorfizmu z innym.

Maksymalna liczba krawędzi dla grafu o 4 wierzchołkach równa jest $\frac{4\times 3}{2}=6$
Czyli narysujmy wszystkie takie grafy, które mają maksymalnie 6 krawędzi oraz dokładnie 4 wierzchołki.


Jest ich dokładnie 11.
Jak byśmy spróbowali narysować dwunasty taki graf, to zależnie ile byśmy dobrali krawędzi w nim, byłby on identyczny z dokładnością do izomorfizmu z innym.

## 5
Wybierzmy jeden wierzchołek. Ten graf musi być 3-regularny, więc od tego wierzchołka musimy wyznaczyć 3 krawędzie, po wyznaczeniu ich zostały nam 2 wierzchołki, od których nie wychodzi ani jedna krawędź. Wtedy mamy 2 przypadki.

$1^\circ$
Te dwa wierzchołki nie będą połączone
Wtedy zarówno wierzchołek E, jak i F muszą być połączone krawędziami z wierzchołakmi B,C i D. Wtedy dostaniemy gotowy graf 3-regularny.


$2^\circ$
Te dwa wierzchołki są połączone

Z punktu E i F musimy poprowadzić po 2 krawędzie do punktów B,C,D, więc z zasady szufladkowej do jednego z tych punktów poprowadzimy krawędź z punktu zarówno z E, jak i F. Więc załóżmy, że to będzie punkt C (jak wybierzemy inny wierzchołek to ten graf będzie izomorficzny). Musimy jeszcze poprowadzić 2 krawędzie z wierzchołka B i 2 z wierzchołka D, z wierzchołka E jedną, z wierzchołka F również jedną. Więc jedyną możliwością, że je połączyć jest opcja na rysunku poniżej (w innym wypadku te grafy byłyby izomorficzne).


## 8

Wiemy, że w dwudzielnym grafie:
$E \subseteq V \times U$, gdzie
V, U to są rozłączne zbiory wierzchołków tego grafu, a E to są krawędzie.

Wtedy liczbę wierzchołków możemy zapisać jako

$|E| \leq |U|\times |V|$

Załóżmy, że $|U|= x$ oraz $|V| = n-x$

Wtedy $|E| \leq x\times(n-x)$

Weźmy $f(x)=x(n-x)$
$f'(x)=-2x+n$ co zeruje się dla $x = \frac n2$ (Jest to maksimum funkcji f).

Czyli $|E| \leq \frac n2\times(n-\frac n2) = \frac {n^2}4$ a wiemy, że liczba krawędzi jest całkowita, więc $|E| \leq \lfloor\frac {n^2}4\rfloor$

Co należało udowodnić.

## 9

Dla $G$ spójnego teza zachodzi.

Dla $G$ niespójnego rozważmy dopełnienie tego grafu.

Weźmy dowolną parę wierzchołków i nazwijmy je $v_1, v_2$. Mamy teraz 2 przypadki

$1^\circ$
Między wierzchołkami była ścieżka (czyli należały do spójnej składowej).
Wtedy ścieżka między nimi zostanie doprowadzona przez wyspę ($v_1$ nie miało połączenia z wyspą, tak jak $v_2$).

$2^\circ$

Między wierzchołkami nie było ścieżki.
Wtedy ta ścieżka zostanie poprowadzona w wyniku dopełnienia.

Czyli dla dowlonej pary wierzchołków, ścieżka między nimi będzie istniała. Czyli ten graf będzie spójny.

Co kończy dowód.