# Lista 2

| 1(0) | 2 | 3 | 4(1.5) | 5(2) | 6(2) | 7(2) | 8(2) | 9(2) | 10Z(2) |
|:----:|:---:|:---:|:------:|:----:|:----:|:----:|:----:|:----:|:------:|
| X | X | X | | X+ | X | | | | |

## Zadanie 2

1. Sort segments <p1,k1>, <p2,k2>, ... , <pn,kn> so that for each 1 <= i < j <= n: 
    ki <= kj

Niech `I` to lista posortowanych odcinków. `S` - zbiór odcinków nieprzecinających się o największej mocy.

add I[1] to S.
card <- 1

while i <- 2 to n
    if I[i].p >= S[card].k
        add I[i] to S.
        card <- card + 1

Dowód:
Niech `S` będzie uporządkowanym (względem końców) zbiorem odcinków wybranych poprzez algorytm z listy `I`.

Załóżmy nie wprost, że istnieje uporządkowany (względem końców) zbiór odcinków `Z` z listy `I` o większej mocy niż `S`.

Weźmy pierwsze odcinki, takie że`S[i] != Z[i]`.

Rozpatrzmy przypadki:

- `Z[i].k < S[i].k`

Mamy sprzeczność. Wiemy, że zarówno odcinek `Z[i]` jak i `S[i]` zaczynają się nie później niż `S[i-1]` (i>1). Lista odcinków była posortowana - skoro tak, to w naszym zbiorze znalazłby się odcinek `Z[i]`.

- `Z[i].k > S[i].k`

Skoro `Z[i]` kończy się dalej niż `S[i]` to oznacza, iż do do końca odcinka `Z[i]` zbiór `S` zawiera więcej lub tyle samo elementów.

- `Z[i].k = S[i].k`

W tym wypadku pomimo wybrane odcinki są równoważne. Nie mają one wpływu na różnicę w liczbie elementów w każdym ze zbiorów.

## Zadanie 3


$$
\frac{a}{b} =
\frac{a \lceil\frac{b}{a}\rceil }{b\lceil\frac{b}{a}\rceil}=
\frac{b - b + a \lceil\frac{b}{a}\rceil }{b\lceil\frac{b}{a}\rceil}=
\frac{b}{b\lceil\frac{b}{a}\rceil} + \frac{ - b + a \lceil\frac{b}{a}\rceil }{b\lceil\frac{b}{a}\rceil} \stackrel{(*)}{=}\\
\frac{1}{\lceil\frac{b}{a}\rceil} + \frac{-b \mod{a}}{b\lceil\frac{b}{a}\rceil}
$$

$$
(*) (-x \mod y) =
-x - y \Big\lfloor \frac{-x}{y} \Big\rfloor =
-x + y \Big\lceil \frac{x}{y} \Big\rceil
$$

Niech `L` to lista ułamków o liczniku jeden sumujących się do `a/b`

if a is equal to 1
    return a/b
    
while a not eaqual to 1
    x <- ceil(b/a)
    Add 1/x to L
    d <- b
    a <- -b mod a
    b <- d * x

Poprawny wynik otrzymamy zawsze, gdy algorytm się skończy.
Niech $a_i$ oznacza wartość licznika w $i$-tej iteracji.
Zauważmy, że $a_{i+1} = -b \mod a_i < a_i$. Skoro $a,b$ są liczbami naturalnymi oraz $a$ maleje z każdą iteracją dopóki nie będzie równe jeden, tzn że obliczenia się zakończą.

Zatem zawsze otrzymamy rozwiązanie, nie jest jednak ono zawsze optymalne, kontrprzykład:
Według algorytmu:
$$
\frac{11}{28} = \frac{1}{3} + \frac{1}{17} + \frac{1}{1428}
$$
Ale możemy zapisać także:

$$
\frac{11}{28} = \frac{1}{4} + \frac{1}{7}
$$

## Zadanie 4

## Zadanie 5

Algorytm działa dla krawędzi o rónych wagach. Istotne jest to w przypadku gdy co najmniej dwie spójne składowe łączą różne krawędzie o takich samych wagach -- wtedy wybór krawędzi dla każdej ze spójnych składowych jest niedeterministyczny i mógłby utworzyć cykl.

Jeśli jednak otrzymamy graf z krawędziami o takich samych wagach możemy je zmodyfikować o np. dodanie indeksu albo zwiększenie każdej z tych wag o różne $\epsilon$.

Rozpatrywać zatem będziemy algorytm dla krawędzi o różnych wagach.
Zakładamy również, że podany graf jest spójny.

while G is not a component
    for each v in G
        chose (v, w) which is of minimal cost
        Connect (v,w) to v
    Create G' with vertices corespondent to each component in G
    and edges from G that are not yet part of any component so that if 
    vertex w of edge (w,x) belonged to Ci component, 
    Ci component should be connected with this edge and x vertex 
    (or another component) accordingly
    G <- G'

$(1)$ Po żadnej iteracji algorytmu nie powstanie cykl.
Rozpatrzmy przypadki, w których z acyklicznych spójnych składowych może powstać cykl:

Zauważmy, że jeśli spójna składowa $C$ była acykliczna to w następnym kroku algorytmu $C$ połączona z wybraną krawędzią nie stworzy cyklu ze względu na to, że nie rozpatrujemy krawędzi wewnątrz tej składowej.

- Cykl powstał poprzez połączenie dwóch superwierzchołków.

Oznacza to, że dla superwierzchołków $v_1,v_2$ wybrane zostały krawędzie $e_1,e_2$, które utworzyły cykl (przyjmijmy bez straty ogólności) $v_1 \rightarrow e_1 \rightarrow v_2 \rightarrow e_2 \rightarrow v_1$.

Skoro krawędź $e_1$ została wybrana dla $v_1$ oznacza to, że jest najmniejszą spośród krawędzi incydentnych do $v_1$, w tym $c(e_1) < c(e_2)$ (c -- funkcja wagi).

Jeśli natomiast $e_2$ wybrana została przez algorytm dla $C_2$ oznacza to, że $c(e_2) < c(e_1)$.

Mamy sprzeczność.

- Cykl powstał poprzez połączenie wielu superwierzchołków

Niech superwierzchołki $v_1,v_2,...,v_k$ $(k\geq 3)$ to kolejne wierzchołki zawierające się w cyklu $C$ powstałym po skończonej iteracji algorytmu.

$C$ jest postaci $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_i \rightarrow \cdots \rightarrow v_k \rightarrow v_1$.

Bez straty ogólności, przyjmijmy, że $c(\{v_1,v_2\}) < c(\{v_2,v_3\})$.

Zatem, najmniejszą krawędzią dla $v_2$ byłaby $\{v_1,v_2\}$, dalej, aby cykl mógł istnieć dla $v_3$ najmniejszą krawędzią musi być $\{v_2,v_3\}$, dla $v_4$ -- $\{v_3,v_4\}$ ... dla $v_i$ -- $\{v_{i-1},v_i\}$...

Aby algorytm wybrał krawędzie w taki sposób, musi zachodzić:
$c(\{v_1,v_2\}) < c(\{v_2,v_3\}) < c(\{v_3,v_4\}) < c(\{v_4,v_5\}) < ... < c(\{v_{k-1},v_k\}) < c(\{v_k,v_1\}) < c(\{v_1,v_2\})$

$(2)$ Zauważmy, że po każdej skończonej iteracji dostajemy las -- jak wiemy, żadna ze składowych spójnych nie może posiadać cyklu, czyli każda jest drzewem.

$(3)$ Każda ze składowych spójnych $C_i$ po skończonej iteracji jest drzewem spinającym dla odpowiedniego podgrafu z $G$ (gdzie $V = V(C), E=\{\{v,w\} \in E(G) | v,w \in V(C)\}$ . Jeśli tak by nie było, oznaczałoby to, że:
- ze spójnej składowej usunięta została krawędź -- nie jest to możliwe, gdyż z każdej spójnej składowej po zakończeniu dobierania krawędzi "składamy" je w superwierzchołki i nie mamy dostępu do połączonych już krawędzi.
- do spójnej składowej dodaliśmy wierzchołek, ale nie krawędź incydentną do tego wierzchołka i spójnej składowej -- jest to niemożliwe ze względu na to, że w momencie przyłączania krawędzi rozpatrujemy tylko krawędzie incydentne do danej sk.s. i za każdym razem do sk.s. dodajemy dokładnie jedną krawędź i dokładnie jeden wierzchołek.

$(4)$ Po każdym zakończeniu dobierania krawędzi dla wszystkich wierzchołków w $G$ każda ze spójnych składowych będzie tworzyć minimalne drzewo rozpinające dla podgrafów grafu $G$ zawierających wierzchołki z danej spójnej składowej i krawędzie incydentne do tych wierzchołków z grafu $G$.

Weźmy taką składową spójną $C$ i odpowiadający jej podgraf z $G$ --> $G_c$.
Z $(3)$ wiemy, że $C$ jest drzewem spinającym dla $G_c$. Załóżmy nie wprost, że nie jest jednak minimalnym drzewem spinającym dla $G_c$. Niech $T$ będzie MST dla $G_c$.

Istnieje zatem conajmniej jedna krawędź, którą należy do $V(C)$ i nie należy do $T$. Nazwijmy ją $e_i$.

Dodajmy teraz krawędź $e_i$ do $T$. W rezultacie otrzymamy cykl w grafie $T$. Skoro w grafie $T$ jest cykl, oznacza to, że do danego wierzchołka $v$ incydentne są krawędzie $e_i$ oraz $e_j$. Zatem w momencie wybierania krawędzi dla wierzchołka $v$ do $C$ dodaliśmy krawędź o mniejszej wadze, stąd $e_i < e_j$. Zatem usuwając krawędź $e_j$ z $T$ otrzymamy drzewo spinające o mniejszej sumie wag. Sprzeczność.

Załóżmy zatem, że przed rozpocząciem kolejnej iteracji superwierzchołki są minimalnymi drzewami spinającymi. Załóżmy nie wprost, że po skończeniu tej iteracji, na skutek złączenia dwóch MST otrzymaliśmy drzewo nie będące MST dla danego podgrafu.

Niech drzewem spinającym otrzymanym przez algorytm będzie $C = (V,E_C)$, a MST dla tego podgrafu będzie $T = (V, E_T)$. Niech zbiór $E_1$ będdzie zbiorem krawędzi przed połączeniem MST. Skoro $E_T \neq E_C$ to istnieje jakaś krawędź $e$, taka że $e \in E_C$ oraz $e \not\in E_T$.

Zauważmy, że krawędź $e$ jest krawędzią dodaną podczas wywołania, w którym dwa drzewa MST złączyły się w jedną składową spójną. Wpp. oznaczałoby to, że któreś z drzew MST nie byłoby MST, co jest sprzeczne ze wcześniejszymi rozważaniami.

Analogicznie, dodajmy krawędź $e$ do $T$. Obserwujemy cykl w $T$, musi zatem istnieć krawędź $f$ incydentna do tego samego superwierzchołka co $e$. Mamy zatem $c(e) < c(f)$, możemy usunąć zatem krawędź $f$ z $T$ i otrzymać mniejsze drzewo spinające, sprzeczność.

## Zadanie 6

Niech $e = \{v,w\}$;

cost = 0

check_MST(G,v,w):    
    mark v visited
    if v == w
        return
    for each u in N(v)
        if u not visited and c(u) < cost
            check_MST(G, u, w)
            
Alg():
    cost = c({v,w})
    remove {v,w} from G
    check_MST(G, v, w)
    
    if w was visited
        return success
    return failure

Złożoność O(|E|+|V|) ponieważ taka sama złożoność jak DFS.

Aby krawędź należała do MST musi:
- nie leżeć na cyklu w $G$$^{(1)}$,
- wpp. nie może być największą krawędzią w tym cyklu$^{(2)}$.

$(1)$ - tzn musi mostem, więc aby skonstruować MST należy dodać tą krawędź,

$(2)$ - Załóźmy nie wprost że MST - $M$ zawiera najcięższą krawędź $e$ cyklu $C$ z grafu $G$. Usunięcie krawędzi $e$ z $M$ powoduje rozpad drzewa na dwa poddrzewa, ale skoro jest cykl to istnieje druga krawędź oparta na innych wierzchołkach nazwijmy ją $e′$ oraz nowo powstałe drzewo rozpinające $D$ które jest o mniejszych wagach niż $M$ (bo zawiera leżejszą krawędź cyklu), czyli dochodzimy do sprzeczności bo $M$ nie jest MST.


###### tags: `aisd`