Indeks w K n,n
- mol_ksiazkowy
- Użytkownik
- Posty: 11266
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3143 razy
- Pomógł: 747 razy
Indeks w K n,n
Udowodnic, że indeks chromatyczny grafu \(\displaystyle{ K_{n,n}}\) jest równy \(\displaystyle{ n}\).
- kerajs
- Użytkownik
- Posty: 8570
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 306 razy
- Pomógł: 3347 razy
Re: Indeks w K n,n
Skoro z każdego wierzchołka wychodzi \(\displaystyle{ n}\) krawędzi, to do ich pomalowania potrzeba \(\displaystyle{ n}\) kolorów, a indeks chromatyczny grafu jest niemniejszy niż \(\displaystyle{ n}\). Wystarczy teraz pokazać, że istnieje kolorowanie krawędzi tego pełnego grafu dwudzielnego tylko \(\displaystyle{ n}\) kolorami.
Niech wierzchołkami pierwszego zbioru będą \(\displaystyle{ A_1, A_2, \ ... \ , A_n}\) , drugiego \(\displaystyle{ B_1, B_2, \ ... \ , B_n}\) , a używane kolory mają numery od 1 do n.
Przykładowe kolorowanie krawędzi tylko \(\displaystyle{ n}\) kolorami:
Krawędź między \(\displaystyle{ A_i}\) i \(\displaystyle{ B_j}\) malowana jest kolorem \(\displaystyle{ j-i+1}\) jeśli \(\displaystyle{ j-i+1>0}\) lub kolorem \(\displaystyle{ n+j-i+1}\) jeśli \(\displaystyle{ j-i+1 \le 0}\)
Niech wierzchołkami pierwszego zbioru będą \(\displaystyle{ A_1, A_2, \ ... \ , A_n}\) , drugiego \(\displaystyle{ B_1, B_2, \ ... \ , B_n}\) , a używane kolory mają numery od 1 do n.
Przykładowe kolorowanie krawędzi tylko \(\displaystyle{ n}\) kolorami:
Krawędź między \(\displaystyle{ A_i}\) i \(\displaystyle{ B_j}\) malowana jest kolorem \(\displaystyle{ j-i+1}\) jeśli \(\displaystyle{ j-i+1>0}\) lub kolorem \(\displaystyle{ n+j-i+1}\) jeśli \(\displaystyle{ j-i+1 \le 0}\)