Klika i graf

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: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Klika i graf

Post autor: mol_ksiazkowy »

:arrow: Udowodnić, że w grafie krytycznym nie ma zbioru rozcinającego, który jest kliką.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Klika i graf

Post autor: arek1357 »

Jeżeli założymy , że jest taki zbiór rozcinający , to po rozcięciu przez klikę \(\displaystyle{ K}\) rozetniemy go na dwie spójne składowe:

\(\displaystyle{ S_{1}, S_{2}}\)

Ale ponieważ G jest krytyczny okazuje się, że podgrafy:

\(\displaystyle{ K \cup S_{1}, K \cup S_{2}}\) są przynajmniej \(\displaystyle{ k-1}\) kolorowalne...

A ponieważ \(\displaystyle{ K}\), \(\displaystyle{ v_{1},v_{2},...,v_{r}}\) to wierzchołki pełnej kliki...

Można tak poprzestawiać kolory, że wierzchołek kliki o numerze \(\displaystyle{ i}\) będzie miał \(\displaystyle{ i }\) ty kolor...

Po połączeniu tych dwóch kolorowań otrzymamy całkowite zabarwienie grafu \(\displaystyle{ G}\) złożone o \(\displaystyle{ k-1}\) kolorach co przeczy, że graf jest \(\displaystyle{ k }\) - kolorowalny.

Oczywiście można rozszerzać robicie na kilka składowych S...
ODPOWIEDZ