Autor Wątek: Algorytm obliczający średnice podgrafów spójnych  (Przeczytany 2859 razy)

Offline Buyuk

  • Użytkownik
    • Mój blog ;]

# Listopad 13, 2011, 18:22:55
Hej,

Powiedzmy, że dany jest skierowany graf G.
Czy istnieje jakiś algorytm który pozwoli obliczyć
średnicę wszystkich spójnych składowych grafu G ?

Nie znalazłem żadnego algorytmu, a moje własne
pomysły wydają mi się zbyt czasochłonne.
Może zna ktoś jakieś rozwiązanie tego problemu ?

Pozdrawiam, Buyuk.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline SiwyEd

  • Użytkownik

# Listopad 13, 2011, 19:01:14
Rozdzielasz graf na spójne składowe a później liczysz dla każdej średnicę?

Offline Buyuk

  • Użytkownik
    • Mój blog ;]

# Listopad 13, 2011, 19:08:37
Tak, a pomijając rozkład na podgrafy. Jak policzyć średnicę ?
Jedyne co mi przychodzi, to znalezienie wszystkich par ścieżek i wybranie najdłuższej z nich,
jednak to wydaje mi się strasznie wolnym rozwiązaniem.

Offline Pan Hania

  • Użytkownik

# Listopad 13, 2011, 20:42:19
Średnicę drzewa można znaleźć w czasie liniowym, nie sprawdzałem czy ten algorytm daje się też rozszerzać na wszystkie grafy spójne (ale powinien działać).
1. ukorzeniasz graf G w dowolnym wierzchołku
2. G' = drzewo BFS G
3. G'' = G' ukorzenione w najodleglejszym liściu (jeżeli jest takich kilka to nie ma znaczenia)
4. średnica = odległość od korzenia G'' do najodleglejszego liścia
Czyli mniej-więcej robisz dwa "liczące odległości" BFS: jeden z dowolnego wierzchołka, drugi z wierzchołka który miał największą odległość w pierwszym BFS. Średnicą jest największa odległość w drugim BFS.
« Ostatnia zmiana: Listopad 13, 2011, 20:44:07 wysłana przez Mr. Hania »

Offline Buyuk

  • Użytkownik
    • Mój blog ;]

# Listopad 13, 2011, 20:49:00
O, dzięki, czegoś takiego mi było trzeba właśnie ;-)

Offline SiwyEd

  • Użytkownik

# Listopad 13, 2011, 23:17:37
Algortym podany przez Mr. Hania nie działa dla nie drzew, ogólnie z tego co wiem niema sensownego algorytmu znajdowania średnicy o złożoności lepszej niż o(n^3) (n to ilość wierzchołków)