Złożoność algorytmu LF

2010-12-19 00:38
0

Witam.

Mam problem ze zrozumieniem, jakim sposobem algorytm kolorowania grafu Largest-First ( http://pl.wikipedia.org/wiki/Kolorowanie_grafu#AlgorytmLF.28largest_first.29 ) może mieć złożoność O(n+m) 1 (m - liczba krawędzi, n - liczba wierzchołków).

Już samo sortowanie nierosnąco ma złożoność od O(n*logn) do O(n2) (w zależności od algorytmu). Na myśl przychodzi mi jeszcze sposób bez sortowania: znaleźć stopnie wierzchołków i n razy wybrać wierzchołek o maksymalnym stopniu (O(n)) oznaczając stopień wybranego wierzchołka jako -1. Niestety to również daje O(n2), nie mówiąc nawet o kolorowaniu zachłannym.

Byłbym wdzięczny za wytłumaczenie skąd taka złożoność.

1 źródło: "Optymalizacja dyskretna: modele i metody kolorowania grafów", pod red. M. Kubale

Pozostało 580 znaków

2010-12-19 01:05
1

Da się sortować liniowo i tutaj akurat countingsort mógłby faktycznie mieć zastosowanie, bo liczby na których operujemy są relatywnie małe.
Mamy więc O(n) na posortowanie wierzchołków wg ich stopnia. Następnie kolorujemy każdą krawędź (i to każdą raz) co daje nam O(m) na kolorowanie. To by nam dalo O(n+m)
Ciekawostka:
gdyby założyć że samo sprawdzenie czy krawędź jest już pokolorowana zajmuje tyle samo czasu co jej faktycznie pokolorowanie to mielibyśmy pesymistycznie O(n+nm) = O(nm) dla pełnego grafu, bo dla każdego wierzchołka musielibyśmy przeglądnąć wszystkie krawędzie


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2010-12-19 01:56
0

Dzięki, zaczynam łapać. A to kolorowanie w czasie O(m) to na jakiej reprezentacji grafu byłoby możliwe?

edytowany 1x, ostatnio: undrcvr, 2010-12-19 02:02

Pozostało 580 znaków

2010-12-19 02:14
1

Na przykład na liście sąsiedztwa. Jeśli to graf nieskierowany to miałbyś kolorowanie w O(2*m) = O(m), dla skierowanego po prostu O(m)
Zresztą w każdej innej reprezentacji, czy to macierzy adiacencji czy incydencji byłoby tak samo, jeśli zakładamy że nie bierzemy pod uwagę kosztu sprawdzenia czy krawędź istnieje oraz czy jest już pokolorowana czy nie.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2010-12-19 02:17

Pozostało 580 znaków

Liczba odpowiedzi na stronę

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