Kolorowanie grafu: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
wikizacja, szablon, algorytmy kolorowania, ogólna redakcja |
drobne merytoryczne, poprawa linków |
||
Linia 13:
==Algorytmy kolorowania grafów==
Ze względu na bardzo szerokie zastosowania, kolorowanie grafów jest przedmiotem rozległych badań. Problem znalezienia optymalnego pokolorowania, a także znalezienia liczby chromatycznej jest [[Problem NP
===Algorytm ''LF'' (largest first)===
Linia 19:
#Uporządkuj wierzchołki grafu malejąco według ich [[stopień wierzchołka|stopni]] (liczby krawędzi z nich wychodzących).
#Koloruj wierzchołki [[algorytm zachłanny|zachłannie]], zgodnie z ustaloną wcześniej kolejnością (zaczynając od wierzchołka o największym stopniu).
Algorytm ''LF'' jest algorytmem ''statycznym'', gdyż raz ustalona kolejność wierzchołków nie zmienia się w trakcie jego działania. Najmniejszym dość trudnym grafem jest ścieżka <math>P_6</math>.
Linia 28:
# Znajdź wierzchołek o minimalnym [[stopień wierzchołka|stopniu]] i usuń go z grafu.
# Powtarzaj krok pierwszy tak długo, aż graf będzie pusty (zapamiętaj kolejność usuwanych wierzchołków).
# Koloruj wierzchołki [[algorytm zachłanny|zachłannie]], zgodnie z ustaloną wcześniej kolejnością (zaczynając od wierzchołków usuniętych później).
Algorytm ''SL'' jest ''statyczny'', jego złożoność wynosi <math>O(n+m)</math>, gdzie <math>n</math> - liczba wierzchołków, <math>m</math> - liczba krawędzi.
Linia 37:
'''dopóki''' ''istnieją nie pokolorowane wierzchołki'' wykonuj operacje:
{
znajdź wierzchołek o maksymalnym stopniu spośród wierzchołków o maksymalnym stopniu nasycenia
pokoloruj znaleziony wierzchołek zachłannie
}
'''Stopniem nasycenia''' wierzchołka nazwiemy tu ilość różnych kolorów incydentnych (sąsiednich) z tym wierzchołkiem. Złożoność algorytmu ''SLF'' wynosi <math>O(m \log n)</math>.
==Inne warianty kolorowania grafów==
| |||