Liczba chromatyczna grafu \(\displaystyle{ G}\), oznaczana przez \(\displaystyle{ \chi (G)}\), to najmniejsza liczba \(\displaystyle{ k}\) taka, ze
istnieje poprawne kolorowanie wierzchołków grafu \(\displaystyle{ G}\) używajżce \(\displaystyle{ k}\) kolorów.
Dla danego grafu \(\displaystyle{ G}\)i uporządkowania jego wierzchołków \(\displaystyle{ v_1, . . . , v_n}\) algorytm kolorowania
First-Fit przyporządkowuje najmniejsze legalne kolory kolejnym wierzchołkom G według
podanego porządku.
Zadania:
1. Wykaż, że dla każdego grafu \(\displaystyle{ G}\) istnieje uporządkowanie wierzchołków dla którego
kolorowanie First-Fit używa \(\displaystyle{ \chi (G)}\) kolorów.
2. Wykaż, że dla każdego \(\displaystyle{ n \ge 1}\) istnieje graf dwudzielny i uporządkowanie jego
wierzchołków takie, ze algorytm First-Fit używa \(\displaystyle{ n}\) kolorów.
Kolorowanie grafów - First-Fit
-
flashion
- Użytkownik
- Posty: 113
- Rejestracja: 20 sty 2009, o 01:27
- Płeć: Mężczyzna
- Podziękował: 6 razy
- Pomógł: 7 razy
Kolorowanie grafów - First-Fit
Ostatnio zmieniony 8 cze 2012, o 13:34 przez Anonymous, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex]
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Kolorowanie grafów - First-Fit
1. Nie wystarczy wziąć jakiegokolwiek kolorowania za pomocą \(\displaystyle{ \chi (G)}\) kolorów i uporządkować wierzchołki według kolorów w tym kolorowaniu? Co prawda algorytm nie musi pokolorować grafu dokładnie tak samo jak w początkowym kolorowaniu, ale chyba nie zużyje więcej kolorów.
2. Na przykład dla \(\displaystyle{ n=3}\):
\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(3,-2){60}}
\multiput(0,-40)(0,-40){2}{\line(3,2){60}}
\put(0,-80){\line(3,4){60}}
\put(-10,2){$1$}
\put(-10,-42){$3$}
\put(-10,-86){$5$}
\put(65,2){$2$}
\put(65,-43){$4$}
\color{blue}\multiput(0,-40)(60,0){2}{\circle*{4}}
\color{red}\multiput(0,0)(60,0){2}{\circle*{4}}
\color{green}\put(0,-80){\circle*{4}}
\end{picture}}\)
2. Na przykład dla \(\displaystyle{ n=3}\):
\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(3,-2){60}}
\multiput(0,-40)(0,-40){2}{\line(3,2){60}}
\put(0,-80){\line(3,4){60}}
\put(-10,2){$1$}
\put(-10,-42){$3$}
\put(-10,-86){$5$}
\put(65,2){$2$}
\put(65,-43){$4$}
\color{blue}\multiput(0,-40)(60,0){2}{\circle*{4}}
\color{red}\multiput(0,0)(60,0){2}{\circle*{4}}
\color{green}\put(0,-80){\circle*{4}}
\end{picture}}\)