WSZYSTKIE drzewa rozpinające!

0

Witam!
Mam taki dość niemały problem. Potrzebuję wygenerować wszystkie możliwe drzewa rozpinające dowolnego grafu (tak wiem, tego jest mnóstwo … ). Znalazłem w jednej książce („Algorytmy kombinatoryczne”) zarys tego problemu, ale to mi nie wiele mówi (kilka godzin siedzenia nad tym do niczego mnie nie zaprowadziło ;-P). W razie jakby ktoś potrzebował skojarzenia to: chodzi mniej więcej o to żeby graf podzielić na 2 drzewa (jedno zawiera pewną gałąź, drugie jej nie zawiera), czynność tą powtarzamy rekurencyjnie…. (w drzewie w którym gałąź zostaje tworzymy tzw. „superwierzchołek” (poprzez złączenie wierzchołków nią łączonych)). Tak to mniej więcej wygląda w tej książce, jest jeszcze wzmianka o metodzie podziału i ograniczeń. Próbowałem coś z tego wyczaić, ale jakoś nie bardzo … Jakby ktoś znał, znalazł albo wymyślił dokładniejszy pseudokod to byłoby gites. (pełny kod programu też mile widziany :-D) Oczywiście może być też zupełnie inny algorytm, ważne żeby robiło to, co w temacie. A ha, jeśli chodzi o generowanie losowych drzew i potem przesiewanie ich – to wiem jak to zrobić, potrzebuję raczej algorytmu „przeszukującego”…. A ha, próbowałem jeszcze przerobić procedurę rekurencyjna DFS – ale się zakręciłem i zastanawiam się czy to w ogóle jest możliwe w taki sposób :-P.

0

Ile jest wszystkich drzew rozpinających w klice?

0

n^(n-2)

0

Witam. Znalazłem gdzieś, że taki algorytm opracowali: AKIYOSHI SHIOURA, AKIHISA TAMURA, AND TAKEAKI UNO. Niestety ten algorytm jest opisany po angielsku i cieżko go nieco zrozumieć zwłaszcza, że nie mało tego jest :P. http://www.cs.caltech.edu/~astern/project/SpanningTrees.pdf
pozdro
Piotrek

1 użytkowników online, w tym zalogowanych: 0, gości: 1