Złożoność algorytmu LF

0

Witam.

Mam problem ze zrozumieniem, jakim sposobem algorytm kolorowania grafu Largest-First ( http://pl.wikipedia.org/wiki/Kolorowanie_grafu#Algorytm_LF_.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

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

0

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

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.

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