Indeks w K n,n

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
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

Post autor: mol_ksiazkowy »

Udowodnic, że indeks chromatyczny grafu \(\displaystyle{ K_{n,n}}\) jest równy \(\displaystyle{ n}\).
Awatar użytkownika
kerajs
Użytkownik
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

Post autor: kerajs »

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