---
title: MDL Lista 13
tags: MDL
author: Mateusz Reis
---
# MDL LISTA 13

## Zadanie 1
Ponieważ istnieje kolorowanie optymalne, to jeśli je znamy i oznaczymy kolory liczbami to jeśli ustawimy je w kolejności od wierzchołków z kolorem o najmniejszej liczbie do wierzołków o największej liczbie to algorytm przypisze kolory w tej kolejności więc znajdzie kolorowanie optymalne.

## Zadanie 3


Ponieważ grafy Mycielskiego możemy tworzyć w sposób rekurencyjny (dla każdego wierzchołka $v_i$ w $M_k$ dokładamy wierzchołek $u_i$ z krawędziami do jego sąsiadów oraz wierzchołek $w$ z krawędziami do wszystkich $u_i$), pokażemy przez indukcje że graf $M_k$ nie zawiera trójkątów.
- podstawa
graf Mycielskiego o k = 2 w sposób oczywisty nie zawiera trójkątów ponieważ ma tylko 2 wierzchołki
- krok
Załóżmy że graf $M_k$ nie zawiera trójkątów, pokażemy że $M_{k+1}$ również nie zawiera trójkątów. Aby stworzyć $M_{k+1}$ do $M_k$ dokładamy $n$ wierzchołków $\{u_1,u_2,....,u_{n}\}$ oraz jeden wierzchołek $w$. Ponieważ każdy wierzchołek $u_i$ jest połączony z $w$ ale nie jest połączony z żadnym z $\{u_1,u_2,...,u_n\}$ to w oczywisty sposób nie stworzymy trójkąta z wierzchołków które dodajemy. Wierzchołek $w$ nie ma żadnego sąsiada $v_i$ więc nie stworzy trójkąta. Pozostaje potencjalny trójkąt z wierzchołków $\{v_i,v_k,u_j\}$. Jednak nigdy on nie powstanie ponieważ $u_i$ nie łączy dwóch sąsiednich wierzchołków $v_i$.

Kolorowanie
- podstawa
dla k = 2 w oczywisty sposób pokolorujemy te wierzchołki na 2 rózne kolory
- krok
założmy że $\chi(M_k)=k$, $M_{k+1}$ stworzony z $M_k$ pokolorujemy w następujący sposób:
- $c(v_i)=c(u_i)$ (te wierzchołki nie są połączone)
- $c(w)=k+1$ (dla każdego $u_i$ zużyliśmy $i$-ty kolor więc dla $w$ musimy dobrać nowy kolor)

Spróbujmy pokolorować $M_{k+1}$ na $k$ kolorów, użyjemy pierwszego koloru dla $w$ wieć zostaje nam $k-1$ kolorów których użyjemy dla $u_i$, ale ponieważ $f(v_i)=f(u_i)$ czyli do pokolorowania wszystkich $v_i$ uzyjemy $k-1$ kolorów co jest sprzeczne z załozeniem. Tak więc $\chi(M_{k+1})=k+1$

## Zadanie 6

Graf $G$ stworzymy z dwóch grafów $V$ oraz $U$ gdzie ich $n$ wierzchołków nie są połączone, a krawędź $(v_i,u_j)$ istnieje tylko jeśli $i\not=j$. (Wyjątkiem będzie $n=1$ bo $V$ i $U$ muszą być połączone).


Dla każdego pozostałego $n$ graf będzie wyglądał tak:


Zaczynamy od dowolnego wierzchołka $v_i$ a potem kolorujemy wierzchołek $u_i$, alogrytm za każdym razem użyje dokładanie $n$ kolorów bo każdy wierzchołek ma $n-1$ sąsiadów, z których każdy ma inny kolor.

## Zadanie 8

Mamy graf prosty o $2n$ wierzchołkach (bo nikt nie przyjaźni się sam z sobą ani nie przyjaźni się z nikim podwójnie) więc możemy skorzystać z tw. Diraca bo $deg(v_i)\geq n$. Tak więc w naszym grafie znajduje się cykl Hamiltona, jeśli przejdziemy po cyklu na zmiane wybierając i odrzucając krawędzie to znajdziemy ustawienie uczniów w ławkach. Jeśli $n\geq 2$ to drugie ustawienie znajdziemy zaczynając od odrzucenia krawędzi.


Dla pierwszego ustawienia wybieramy :red_circle: krawędzie a dla drugiego je odrzucamy i wybieramy :large_blue_circle:

## Zadanie 10

Mamy graf
$$
n=5, min\{deg(v)\}=2, \frac{n-1}{2}
$$

Jak widać słabszy warunek zachodzi ale nie mamy cyklu Hamiltona.