Sortujemy odcinki wg k_j, rosnaco. Wybieramy pierwszy, potem kolejny, ktory sie zmiesci po pierwszym.
Dowod: Mamy uporzadkowanie wg algorytmu: U. Zalozmy, ze istnieje lepsze, optymalne uporzadkowanie odcinkow O. Wezmy wtedy pierwszy odcinek, ktory jest rozny w tych dwoch uporzadkowaniach O_i \ne U_i. Jesli odcinek O_i konczy sie wczesniej niz U_i to bysmy go wybrali algorytmem. Jesli konczy sie w tej samej pozycji, to nieistotne gdzie sie zaczyna. Jesli konczy sie pozniej to moze albo zmniejszyc rozmiar zbioru, albo go nie zmienic. Rozwiazanie algorytmem jest wiec najlepsze.
Wytwarzanie ulamka egipskiego mniejszego od \frac{x}{y} o najwiekszym mianowniku: \frac{x}{y} \rightarrow \frac{1}{\lceil y/x \rceil}
Licznik \frac{x}{y} - \frac{1}{\lceil y/x \rceil} bedzie malal, i bedzie \ge 0, wiec algorytm yieldowania ulamkow sie zatrzyma: \frac{x}{y} - \frac{1}{\lceil y/x \rceil} = \frac{x \lceil y/x \rceil - y}{x\lceil y/x \rceil},
sprawdzmy, czy x \lceil y/x \rceil - y < x: x \lceil y/x \rceil - y < x \Leftrightarrow x \lceil y/x \rceil - x < y \Leftrightarrow \lceil y/x \rceil - 1 < y/x - x byl rozny od zero,
bo gdyby byl zerem to algorytm by sie zatrzymal wczesniej. Also: x \lceil y/x \rceil - y \ge 0
Dane = $\{Leaf(w_i)\}$
minEL(X) - to funkcja która zwraca drzewo ze zbioru X, o najmniejszej wartości EL(X)
while(Dane.size > 1){
Z = {Node(a,b) : $a,b \in Dane \ \wedge \ a \not= b$}
Node(x,y) = minEL(Z)
Dane = Dane \ {x,y}
Dane u= {Node(x,y)}
}
return Dane[0]
D-d v3: Niech Z będzie drzewem zwórconym przez algorytm zachłanny. Niech O będzie drzewem optymalnym.
NIEWPROST: O \not= Z
Niech D_i oznacza zawartość zmiennej Dane z algorytmu zachłannego w i-tej iteracji pętli while, czyli D_i jest lasem.
Weźmy najmniejsze takie j że \exists_{d \in D_j} d nie jest poddrzewem O. Zaówżmy że istnieje dokładnie jedno takie d \in D_j gdyż w każdej iteracji algorytm zachłanny dodaje tylko jedno nowe drzewo do zmiennej Dane.
Niech Node(a,b) = d.
Wiemy że a, b \in D_{j-1} i a,b są poddrzewami O. [i]j > 0 bo D_0 musi się zawierać w O[/i]
Niech x,y będą poddrzewami z O takimi że t=Node(a,x), t'=Node(b,y) też są poddrzewami z O.
Niech m będzie głębokość poddrzewa t w O, a m' poddrzewa t' w O. Bez straty ogólności załóżmy że m \ge m'
Zbudujmy sobie drzewo O', które będzie takie samo jak O z tym że w miejscu t wstawmy Node(a,b), a w miejscu t' wstawmy Node(x,y).
Ponieważ EL(Node(a,b)) < EL(Node(a,x)) oraz x znalazło się wyżej w drzewie, a y nie zmieniło pozycji więc: EL(O) > EL(O') SPRZECZNOŚĆ