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

# Lista 10

## 1

Wpisujemy wszystkie krawędzie G1 do wektora sąsiedztwa M1 oraz G2 do wektora sąsiedztwa M2

Przykładowy algorytm napisany w języku Python

V = {0}*n

for i in range(n):

    licznik = 0;
    
    for j in M1[i]:
        licznik = licznik + 1;
        V[j] = 1;
        
    for j in M2[i]:

        if V[j] == 0:
            return False;
            
        licznik = licznik - 1;
        V[j] = 0;


    if licznik > 0:
        return False;
        
return True;   

Złożoność $O(n+m)$

## 2
### a)
Nie istnieje, ponieważ $\displaystyle\sum_{k=1}^{5}deg(v_k) = 2n$, gdzie
$n\in N$. $1+2+2+3+3=11$ co nie jest podzielne przez $2$ (każda krawędź musi mieć swój początek i koniec).

### b)
Nie istnieje. Weźmy dowolny wierzchołek i poprowadźmy od niego 4 krawędzie. Wtedy wiedząc, że ten graf ma 5 wierzchołków od jednego wierzchołka będą poprowadzone 4 krawędzie, od czterech kolejnych po jednej. Musimy jeszcze doprowadzić z jednego wierzchołka 2 krawędzie lecz jest to niemożliwe, ponieważ wszystkie pozostałe wierzchołki nie mogą już mieć żadnych poprowadzonych krawędzi.

### c)
Po wzięciu takiego grafu rozważmy 2 przypadki.

$1^\circ$ W jednej grupie wierzchołków jest 1 wierzchołek
Wtedy w drugiej grupie są 4 wierzchołki, a skoro z każdego wychodzą po 2 krawędzie otrzymujemy sprzeczność, ponieważ w tej drugiej grupie znajduje się tylko 1 wierzchołek.

$2^\circ$ W jednej grupie są 2 wierzchołki
Wtedy w drugiej grupie znajdują się 3 wierzchołki. Aby z każdego wychodziły 2 krawędzie musimy poprowadzić łącznie z tej grupy 6 krawędzi. Wtedy z drugiej grupy również musi wychodzić 6 krawędzi. Jest to jednak niemożliwe bo mamy tam 2 wierzchołki, z których wychodzą po 2 krawędzie ($4\neq6$).

## 4
Weźmy wierzchołek $v$, dla którego $deg(v)=n-2$. Wtedy istnieje jakiś wierzchołek $w$, który nie jest połączony z $v$, więc jest połączony z innym punktem ($d(G)=2$), który jest sąsiadem $v$. Po połączeniu tych punktów możemy zobaczyć, że odległość $w$ od sąsiada $v$, który nie jest połączony z $w$ wynosi 3 (a powinno maksymalnie 2). Więc musimy połączyć tak każdego sąsiada v z wierzchołkiem $w$ (inaczej średnica tego grafu nadal wynosiłaby 3). Czyli z wierzchołka $v$ wychodzi $n-2$ krawędzi, a z wierzchołka $w$ również $n-2$ krawędzi. Wiedząc, że $w$ i $v$ nie są połączone bezpośrednio krawędzią, otrzymujemy $2n - 4$ krawędzi. Czyli minimalna ilość tych krawędzi, aby były zachowane założenia za
dania wynosi $2n-4$, czyli $m\leq2n-4$ co należało pokazać.

## 5
### a)
$r(G) \leq d(G) \leq 2\times r(G)$

$1^\circ$ $r(G) \leq d(G)$
$r(G)$ jest odległością między
dwoma wierzchołkami w grafie $G$ więc musi być mniejsza równa od największej takiej odległości.

$2^\circ$ $d(G) \leq 2\times r(G)$

$r(G)$ jest największą odległością wierzchołka centralnego od wierzchołka w grafie. Musi być więc być ona równa co najmniej $\frac{d(G)}{2}$.
Więc mamy
$\frac{d(G)}2 \leq r(G)$ Czyli
$d(G) \leq 2\times r(G)$ co należało pokazać

### b)

Indukcja po $n = d(G)$.

$1^\circ$
Dla $n=0$
Mamy 1 punkt, który jest wierzchołkiem centralnym.

Dla $n=1$

Mamy 2 wierzchołki połączone ze sobą, czyli mamy 2 wierzchołki centralne.

$2^\circ$ Weźmy drzewo, które ma $d(G)>1$
Wtedy jak zabierzemy wszystkie liście z definicji średnicy zmniejszy się ona o 2 nie zmieniając przy tym wierzchołków centralnych. Z założenia inducyjnego wiemy, że taki pomniejszony graf ma 1 lub 2 wierzchołki centralne.

Na podstawie indukcji matematycznej pokazałem, że graf ma 1 lub 2 połączone ze sobą krawędzią wierzchołki centralne.

### c)

Algorytm:
Powtarzaj dopóki w grafie jest więcej niż 2 nieodznaczone wierzchołki:
$\qquad$odznacz wszystkie liście i potraktuj rodziców tych liści jako liście przy następnej iteracji pętli.

Czasowo jest to algorytm liniowy. Czyli $O(n)$

## 6
Mamy drzewo złożone z 4 wierzchołków. Wtedy, aby drogi a z b i c z d były rozłączne, muszą być połączone bezpośrednią krawędzią. Załóżmy nie wprost, że drogi a z b i c z d są rozłączne oraz a z c i b z d również. Wtedy jedyną możliwością jest aby graf ten wyglądał jak na rysunku
Nie jest to jednak drzewo co przeczy założeniu, czyli otrzymaliśmy sprzeczność.

Czyli teza jest prawdziwa co kończy dowód.

## 11

Wszystkich drzew jest $n^{n-2}$ z twierdzenia Cayley'a.
Wszystkich drzew mających $n-1$ wierzchołków (bez wierzchołka nr 1) jest $(n-1)^{n-3}$. Aby uzyskać wszystkie drzewa, w których wierzchołek 1 jest liściem to musimy "dokleić" go w dowolnym miejscu jedną krawędzią, wtedy zawsze będzie liściem. Można to zrobić na $n-1$ sposobów. Więc wszystkich takich zdarzeń, że wierzchołek 1 jest liściem jest $(n-1)\times(n-1)^{n-3}=(n-1)^{n-2}$

Czyli prawdopodobieństwo wynosi $\frac{(n-1)^{n-2}}{n^{n-2}}$

$\displaystyle\lim_{n\rightarrow\infty}(\frac{n-1}{n})^{n-2}=\displaystyle\lim_{n\rightarrow\infty}((\frac{n}{n-1})^{n-2})^{-1}=$
$=\displaystyle\lim_{n\rightarrow\infty}((1 + \frac{1}{n-1})^{n-2})^{-1}=e^{-1}=\frac{1}{e}$

## 13

Indukcja po n - ilośći wierzchołków

$1^\circ$ dla $n=0, n=1, n=2$
$n=0, n=1$ nie ma krawędzi

$n=2$ maksymalnie 1 krawędź $\leq \lfloor\frac{2^2}{4}\rfloor=1$

$2^\circ$ dla $n+2$ wierzchołków
Weźmy dowolny graf $G$, który ma $n+2$ wierzchołków oraz nie ma żadnego cyklu długości 3. Wtedy weźmy dowolne 2 wierzchołki połączone krawędzią, nazwijmy je $v,w$. Wtedy usuńmy $v,w$ z grafu usuwając przy tym wszystkie krawędzi powiązane z nimi. Dostaliśmy graf, który ma n wierzchołków i nie ma żadnego cyklu długości 3. Czyli z założenia indukcyjnego wiemy, że ten graf ma $\leq \lfloor\frac{n^2}4\rfloor$ krawędzi.

Wtedy jak będziemy chcieli dołożyć ponownie te wierzchołki, to możemy zauważyć, że z obu wierzchołków $v$ i $w$ (nie licząc tej jednej krawędzi pomiędzy $v$ i $w$) może wychodzić co najwyżej $n$ krawędzi, ponieważ z obu wierzchołków nie mogą zostać poprowadzone krawędzi do jednego wierzchołka (wtedy byśmy dostali cykl o długości 3). Czyli w tym grafie (o $n+2$ wierzchołkach) mamy dodatkowo max $n+1$ krawędzi (licząc też krawędź pomiędzy $v$ i $w$).
$|E_G| \leq \lfloor\frac{n^2}4\rfloor + n + 1 = \lfloor\frac{n^2}4\rfloor + \frac{4n+4}4 = \lfloor\frac{n^2 + 4n + 4}4\rfloor = \lfloor\frac{(n+2)^2}4\rfloor$

Na podstawie indukcji matematycznej pokazałem, że teza zachodzi.