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
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!