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

## Zadanie 2
Chcemy pokazać że:
graf spójny zawiera cykl eulera $\iff$ każde minimalne cięcie zawiera parzystą liczbę krawędzi
- $\implies$
Mamy graf spójny eulerowski, wybierzmy dwie dowolne spójne składowe $X$ oraz $V\setminus X$ poniważ jest to graf spójny cięcie będzie zawierało co najmniej jedną krawędź. Jeśli przejdziemy nią z jednej spójnej składowej do drugiej to potrzebujemy drugiej aby wrócić do spójnej z której startowaliśmy. Dlatego aby istniał cykl eulerowski (z założenia wiemy że istnieje) zawsze musi istnieć parzysta liczba krawędzi między dwiema spójnymi składowymi. Te krawędzie to minimalne cięcie.
- $\Longleftarrow$
Wybierzmy w grafie dowolny wierzchołek $v$ i podzielmy graf na spójne składowe $g_1,g_2,g_3,g_4$. Aby rozspójnić graf musimy usunąć parzystą liczbę krawędzi (z załozenia że minimalne cięcie jest parzyste) co oznacza że co oznacza że każdy wierzchołek w grafie ma parzysty stopień czyli graf zawiera cykl eulera.


## Zadanie 3

Mamy dwa zbiory osób A i B wiemy że każda z osób a chce poślubić $n_a \geq 1$ osób, które zna z zbioru B. Chcemy znać warunek dostateczeny i konieczny aby istniało rozwiązanie problemu. Jeśli sklonujemy osoby $a_i$ razem z ich znajomościami (krąwędziami) tyle razy ile chcą mieć żon tzn. $\{a_1,a_2,a_3,...a_n\}\to\{a_1,a_1,a_1,a_2,a_2,a_3,...,a_n,a_n,a_n,a_n\}$
to otrzymamy zwykły problem kojarzenia małżeństw, który opisuje twierdzenie Halla. Wtedy warunek koniecznny i dostateczny aby istaniało rozwiązanie problemu to istnienie dla dowolnej $B_i \subseteq B$ w której znajduje się $k$ osób podgrupy znajomości(sąsiadów) $A_i$ t.ż. $|A_i| \geq |B_i|$.

## Zadanie 4

Graf w którym każdy wierzchołek ma 1 krawędź wchodzącą i 1 wychodzącą możemy przedstawić w sposób pokazany poniżej(nie zmieniając krawędzi tylko przestawiając wierzchołki aby krawędzie się nie krzyżowały):


Jak widać graf jest (w założeniu miał tak wyglądać) okręgiem. Obracanie koła nie zmienia ustawienia wierzchołków, więc możemy wybrać jeden stały wierzchołek i względem niego ustawiać resztę wierzchołków. Jeśli ustawimy wierzchołki w ciąg z jednym punktem stałym(w naszym przykładzie wybieramy 0 ) będzie wyglądał on tak 0,1,2....,(n-2),(n-1) jeśli zero jest punktem stałym to mamy n-1 miejsc na które możemy wstawić dowolny wierzchołek z pozostałych co daje $(n-1)!$ możliwych grafów.

## Zadanie 10

Przykładowy prostokąt łaciński:


Aby udowodnić że można rozszerzyć dowolny prostokąt łaciński t.ż. liczba wierszy$(m)$ < liczba kolumn$(n)$, rozważmy liczby których nie ma w danej kolumnie.

Możemy przedstawić to za pomocą grafu gdzie wierzchołek $c_i$ to kolumna o numerze $i$ a $N_i$ to liczba $i$ której brakuje w tej kolumnie. Wtedy graf dla przykładowego prostokąta może wyglądać tak:


Graf ten zawiera $2n$ wierzchołków gdzie każdy wierzchołek $c_i$ ma $n-m$ sąsiadów bo w każdej kolumnie jest $m$ liczb. Również każdy wierzchołek ma $n-m$ sąsiadów bo w każdym wierszu liczba $i$ występuje tylko raz. Tak więc mamy graf dwudzielny regularny w którym każdy wierzchołek ma ten sam stopień. Z twierdzenia Halla wiemy że istnieje skojarzenie doskonałe, czyli możemy utworzyć kolejny wiersz.