algorytm kodowania i wyznaczania drzewa jest taki:
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Kod_Pr%C3%BCferapotrzebuję dowodu, że podczas wyznaczania drzewa z kodu nie powstanie cykl.
Sam dochodzę do takiego faktu:
Za każdym razem gdy dodajemy jakąś nową krawędź powstaje nam struktura która niekoniecznie jest drzewem (jest lasem). Tworząc drzewo dodajemy do lasu za każdym jeden nowy wierzchołek albo dwa nowe wierzchołki albo łączymy krawędzią dwa już istniejące wierzchołki. Cykl może powstać tylko w tym ostatnim przypadku. Musiałyby należeć do jednej składowej lasu (do jednego drzewa) więc należy wykazać, że należą do dwóch różnych drzew tego lasu. W tym miejscu nie wiem jak to dalej ruszyć. Może jest jeszcze inna droga na udowodnienie tego? Jeśli znacie jakąś książkę w której byłoby to opisane to proszę o tytuł.
Pozdrawiam
