Matematyka.pl

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.

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}}\)