[Teoria złożoności] Drzewa rozpinające, algorytm tour

buzzek90
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 30 maja 2014, o 14:00
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

[Teoria złożoności] Drzewa rozpinające, algorytm tour

Post autor: buzzek90 »

witam,
na poczatku chcialbym przedstawic problem, mianowicie chcialbym aby ktos moglby mi w prosty sposob(jak najbardziej sie da ) wytlumaczyc jak go rozwiazac, najlepiej krok po kroku ;p
Rozumiem w miare o co chodzi z grafami jednka srednia zlozonosc oblizeniowa to dla mnie czarna magia:D

Rozważmy graf spójny \(\displaystyle{ G = (V, E)}\), w którym \(\displaystyle{ |V| = n}\) oraz \(\displaystyle{ |E| = m}\), a stopień każdego
wierzchołka zapisano w zbiorze \(\displaystyle{ \{d_i : i \in V \}}\). Dla każdego takiego grafu poniższy algorytm tour
tworzy losowe drzewo rozpinające T w taki sposób, że prawdopodobieństwo uzyskania każdego
drzewa spośród wszystkich drzew rozpinających graf G jest takie samo.
tour(G)

Kod: Zaznacz cały

1 T := ∅
2 Wybierz dowolny wierzchołek i ∈ V
3 while nie wszystkie wierzchołki zostały odwiedzone do
4 przesuń się losowo do sąsiada J z prawdopodobieństwem 1/di
5 if wierzchołek J nie został jeszcze odwiedzony
6 then wstaw krawędź (i, J) do drzewa T
7 i := J
8 return T
Oszacuj średnią złożoność obliczeniową tego algorytmu.


inne zadanie, moze latwiejsze:D :
Przedstaw algorytm o złożoności obliczeniowej \(\displaystyle{ 0(max(n2,mn))}\), który sprawdza, czy podany graf
składający się z n wierzchołków i m krawędzi nie zawiera trójkąta (czyli trzech wierzchołków
połączonych każdy z każdym).

Z GORY DZIEKUJE ZA POMOC!
Ostatnio zmieniony 31 maja 2014, o 16:40 przez Afish, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
ODPOWIEDZ