Klika i graf
- mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Klika i graf
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...
\(\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...