# AiSD lista 2 - Wojciech Adamiec
## Zadania Deklarowane: 2, 4, 5, 6

### Zadanie 2.
:::info
:::

def policz(I[1...n]):
    S = {}
    koniec = -INF
    I.sortuj(dla par <p, k> -> k.rosnąco)
    Dla każdego <p, k> w I:
        Jeśli (p >= koniec):
            S.dodaj(<p, k>)
            koniec = k
    Zwróć S

Nasz algorytm zwraca zbiór $S$. Załóżmy, że $S'$ jest zbiorem optymalnym zbierającym najkrótsze odcinki. Rozpatrujemy pierwszą różnice patrząc od lewej strony.

Nasz algorytm wybrał odcinek $s$. Optymalny algorytm wybrał $s'$. Istnieją trzy przypadki:

1. $s.koniec > s'.koniec$ (Niemożliwe, idziemy po posortowanej tablicy)

2. $s.koniec < s'.koniec$

Przypadek nie może zajść, bo wówczas $S'$ nie spełniałby założeń: Mógłby wziąć odcinek $A$ zamiast $B$, a potem kontynuować bez zmian.

4. $s.koniec = s'.koniec$ (dostaniemy rozwiązanie inne, ale również optymalne)

**Złożoność czasowa**:
$O(n \log n)$

**Złożoność pamięciowa**:
$O(n)$

### Zadanie 4.


Wprowadźmy pojęcie warstwy drzewa $t$:

Warstwa $0$ - wszystkie liście drzewa $t$
Warstwa $1$ - wszystkie liście drzewa $t$ po obcięciu od $t$ wierzchołków z warstwy 0
Warstwa $n$ - wszystkie liście drzewa $t$ po obcięciu od $t$ z warstw $0, 1, ..., n-1$

Załóżmy na chwilę, że $k$ jest parzyste.

Będziemy chcieli pokolorować $\frac{k}{2}$ warstw zaczynając od warstwy $0$. W ten sposób dowolna ścieżka prosta w grafie będzie zawierać nie więcej niż $k$ pokolorowanych wierzchołków.

Dlaczego tak jest?

Każda ścieżka prosta może wejść w obszar pomalowanych wierzchołków w co najwyżej 2 miejscach (przez obszar rozumiemy pomalowane warstwy) - na początku ścieżki i jej końcu. W każdym takim obszarze jest co najwyżej $\frac{k}{2}$ pomalowanych wierzchołków.

Poniżej przykład dla $k=4$.


Kla $k$ nieparzystego będziemy chcieli pokolorować $\lfloor \frac{k}{2} \rfloor$ warstw. Następnie będziemy chcieli pokolorować jeszcze jeden dodatkowy wierzchołek.

Łatwo zauważyć, że to może być dowolny wierzchołek - wtedy ścieżka z największa ilością pomalowanych wierzchołków może ich mieć co najwyżej $\lfloor \frac{k}{2} \rfloor + \lfloor \frac{k}{2} \rfloor + 1 = k$

Jednocześnie zauważamy, że jeśli pomalowalibyśmy więcej niż 1 dodatkowy wierzchołek -- wówczas można by wskazać ścieżkę, która zawierałaby $k + 1$ pomalowanych wierzchołków (przechodziłaby przez oba pomalowane wierzchołki oraz wchodziła początkiem i końcem w pomalowane warstwy), co burzy nam założenia zadania.

**Algorytm**:

Załóżmy, że mamy drzewo w postaci listy sąsiedztwa.

Niech N(v) będzie oznaczać wszystkich sąsiadów v

L, R - puste listy
Dla każdego v:
    Jeśli |N(v)| = 1
    L.dodaj(v)

Zrób k/2 razy:
    Dla każdego wierzchołka v z L:
        pokoloruj v
        Dla ojca p wierzchołka v (czyli jedyny wierzchołek z N(v)):
            N(p).usuń(v)
            Jeśli |N(p)| = 1
                R.dodaj(p)
    L = R
    R = []

Jeśli k mod 2 == 1:
    Pomaluj dowolny niepomalowany wierzchołek (jeśli istnieje)
        

**Złożoność czasowa**:
$O(n)$ # Każdy wierzchołek pokolorujemy co najwyżej raz

**Złożoność pamięciowa**:
$O(n + m)$ # Graf i dwie listy

### Zadanie 5.


Zacznijmy od wprowadzenia, że każda krawędź jest unikalna. Jeśli nie to łatwo to zagwarantować. (jakaś wartość unikalna po przecinku związana z id).

Algorytm:

Zauważmy, że skoro krawędzie są unikalne to jeśli jakiś wierzchołek $A$ (superwierzchołek) wybierze krawędź prowadzącą do $B$ to wówczas $B$ wybierze tą samą krawędź.

Spojrzymy na ten algorytm nieco inaczej - dla nas pojedynczym krokiem będzie wybranie jednej krawędzi.

Będziemy chcieli przeprowadzić indukcję względem iteracji. Niezmiennikiem pętli będzie dla nas to, że mamy do czynienia z lasem drzew MST. W każdym kroku (w każdym realnym kroku, to znaczy pomijając te, które wybierają krawędź już wybraną) w naszym lesie będzie o jedno drzewo mniej.

**Dowód:**

Weźmy dowolny graf $n$ wierzchołkowy o unikalnych krawędziach.

**Baza:**

Mamy las $n$ drzew (wierzchołków). Każde z nich jest poprawnym drzewem MST.

**Krok:**

Założmy, że po $n$ iteracjach dalej mamy do czynienia z lasem drzew MST (drzew jest teraz $n$ mniej).

W tym kroku algorytm weźmie jakieś 2 drzewa MST i znajdzie najmniejszą krawędź między nimi. Od teraz algorytm będzie traktował te dwa drzewa i tą krawędź jako nowe drzewo. Widzimy, że ilość drzew w lesie zmalała o 1.

Pokażemy, że połączone ze sobą w ten sposób drzewa MST dalej tworzą drzewo MST. Skorzystamy tutaj z **cut property**:


Własność ta mówi, że dla każdego cięcia, jeśli krawędź $e$ jest najmniejszą krawędzią tego cięcia to wówczas musi należeć do MST. W naszym przypadku krawędzie są unikalne, a co za tym idzie istnieje tylko jedno drzewo MST.

Zauważmy, że jeśli potrakujemy wierzchołki z podrzew, które chcemy połączyć jako zbiór wierzchołków grafu, to wówczas cięciem są wszystke krawędzie które łączą jedno drzewo z drugim. Nasz algorytm wybiera najmniejszą z nich, a zatem właśnie tą, która na mocy **cut property** musi znaleźć się w naszym MST.

Zatem istotnie po tym kroku będziemy mieli nadal do czynienia z lasem drzew MST pomniejszonym o 1 drzewo.

W ostatniej iteracji połączymy ze sobą ostatnie dwa drzewa MST i na mocy tego samego lematu wiemy, że powstałe w ten sposób drzewo również jest MST - tym razem jest to drzewo rozpięte na całym naszym grafie.

Zmniejszająca się ilość drzew w lesie gwarantuje nam, że algorytm się zakończy.

### Zadanie 6.


Zacznijmy od krótkich lematów:

**Lemat 1:**

Dla dowolnego cyklu $C$ i krawędzi $e \in C$ w grafie, jeśli waga $e$ jest większa, niż waga wszystkich innych krawędzi w cyklu $C$, to $e$ nie należy do żadnego minimalnego drzewa spinajacego w grafie.

**Dowód:**

Załóżmy nie wprost, że $e \in MST$. Usunięcie $e$ spowoduje rozspójnienie $MST$ na dwa poddrzewa $T_1$ i $T_2$. Skoro $e \in C$ to istnieje jakaś krawędź $e'$, taka, że $e'\in C$ i końce $e'$ leżą odpowiednio w $T_1$ i $T_2$. Z założenia wiemy, że $e$ jest krawędzią o największej wadze w $C$, zatem $e'$ ma mniejszą wagę niż $e$. Możemy wówczas połączyć drzewa $T_1$ i $T_2$ krawędzią $e'$. Dostaniemy dzięki temu nowe drzewo rozpinające o wadze mniejszej niż $MST$. Doszliśmy zatem do sprzeczności.

**Lemat 2:**

Jeśli w każdym cyklu $C$ takim, że $e \in C$ istnieje krawędź cięższa od $e$ to wówczas istnieje takie $MST$, że $e \in MST$.

**Dowód:**

Załóżmy nie wprost, że $e$ nie należy do żadnego minimalnego drzewa rozpinającego. Weźmy dowolne takie drzewo i nazwijmy je $M$. Wówczas $M \cup \{e\}$ zawiera cykl. Jednocześnie wiemy, że w tym cyklu jest jakaś inna cięższa od $e$ krawędź. Możemy wyrzucić tą krawędź otrzymując MST o mniejszej wadze niż $M$ co powoduje sprzeczność.

**Algorytm:**

Niech krawędź $e$ łączy wierzchołki $v$ i $u$. Usuńmy krawędź $e$ z grafu $G$ tworząc graf $G'$.

Za pomocą algorytmu DFS, w którym będziemy rozważać tylko krawędzie o mniejszej wadze niż waga $e$ sprawdźmy czy istnieje połączenie między $v$ i $u$.

Jeśli takie połączenie istnieje wówczas wiemy, że w grafie $G$ znajdował się cykl $C$, a krawędź $e \in C$ była najcięższą krawędzią tego cyklu. Z lematu wiemy wówczas, że krawędź $e$ nie należy do żadnego drzewa rozpinającego grafu $G$.

Jeśli takie połączenie nie istnieje wówczas są dwie możliwości:

1. Cykl nie istnieje. Wówczas $e$ musi należeć do MST.
2. W każdym cyklu, w którym jest $e$ istnieje krawędź cięższa od $e$. Z lematu 2 wiemy, że $e$ należy do jakiegoś MST.

**Złożoność czasowa**:
$O(n + m)$ # DFS

**Złożoność pamięciowa**:
$O(n + m)$ # Graf