Twierdzenie o minimalnym stopniu w grafie k-krytycznym
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Twierdzenie o minimalnym stopniu w grafie k-krytycznym
Znalazłem to zadanie między innymi pod taką nazwą jak w temacie. Należy pokazać, że każdy wierzchołek w grafie \(\displaystyle{ k}\)-krytycznym (tzn. takim, że \(\displaystyle{ \chi(G)=k}\) i usunięcie jakiegokolwiek wierzchołka zmniejsza liczbę chromatyczną) ma stopień równy co najmniej \(\displaystyle{ k-1}\).
-
- Użytkownik
- Posty: 44
- Rejestracja: 25 kwie 2015, o 12:24
- Płeć: Mężczyzna
- Podziękował: 11 razy
- Pomógł: 3 razy
Twierdzenie o minimalnym stopniu w grafie k-krytycznym
Zauważ, że każdy wierzchołek danego koloru musi być połączony z jakimkolwiek wierzchołkiem o innym kolorze. W przeciwnym razie można byłoby znaleźć lepsze kolorowanie. Tak więc tych kolorów (poza kolorem, którym pokolorwany jest rozpatrywany wierzchołek) jest \(\displaystyle{ k-1}\). Można też zrobić to nie wprost i wykorzystać k-krytyczność.
Niech \(\displaystyle{ v \in V}\) będzie wierzchołkiem o najmniejszym stopniu i załóżmy, że \(\displaystyle{ \delta(G) < k-1}\).
Wtedy liczba chromatyczna \(\displaystyle{ G-v}\) wynosi \(\displaystyle{ k-1}\) i oznaczmy zbiór kolorów \(\displaystyle{ A = \left\{ 1,2,...,k-1\right\}}\). Widać, że z zasady szufladkowej istnieje taki kolor \(\displaystyle{ j \in A}\), którym nie został pokolorowany żaden z wierzchołków incydentych z \(\displaystyle{ v}\). W takim razie kolorując \(\displaystyle{ v}\) kolorem \(\displaystyle{ j}\) otrzymujemy dobre pokolorowane grafu \(\displaystyle{ G}\) na \(\displaystyle{ k-1}\) kolorów. Sprzeczność.
Niech \(\displaystyle{ v \in V}\) będzie wierzchołkiem o najmniejszym stopniu i załóżmy, że \(\displaystyle{ \delta(G) < k-1}\).
Wtedy liczba chromatyczna \(\displaystyle{ G-v}\) wynosi \(\displaystyle{ k-1}\) i oznaczmy zbiór kolorów \(\displaystyle{ A = \left\{ 1,2,...,k-1\right\}}\). Widać, że z zasady szufladkowej istnieje taki kolor \(\displaystyle{ j \in A}\), którym nie został pokolorowany żaden z wierzchołków incydentych z \(\displaystyle{ v}\). W takim razie kolorując \(\displaystyle{ v}\) kolorem \(\displaystyle{ j}\) otrzymujemy dobre pokolorowane grafu \(\displaystyle{ G}\) na \(\displaystyle{ k-1}\) kolorów. Sprzeczność.
Ostatnio zmieniony 2 wrz 2016, o 21:45 przez Downonmyluck, łącznie zmieniany 4 razy.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Twierdzenie o minimalnym stopniu w grafie k-krytycznym
Dowód nie wprost. Załóżmy, że w tym grafie istnieje wierzchołek stopnia mniejszego niż \(\displaystyle{ k - 1}\). Z założenia jego usunięcie zmniejsza liczbę chromatyczną, czyli liczba chromatyczna grafu bez tego wierzchołka jest nie większa niż \(\displaystyle{ k - 1}\). Jest on połączony z co najwyżej \(\displaystyle{ k - 2}\) innymi wierzchołkami, więc można go pokolorować pozostałym \(\displaystyle{ k - 1}\)-szym kolorem, więc cały graf ma liczbę chromatyczną nie większą niż \(\displaystyle{ k - 1}\), sprzeczność.
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Twierdzenie o minimalnym stopniu w grafie k-krytycznym
Dziękuję za odpowiedzi, i to tak szybkie. Właściwie nie było to trudne. Za szybko się zniechęciłem.
Nie całkiem rozumiem. Chciałeś chyba powiedzieć tyle, że przy optymalnym kolorowaniu dla każdej pary kolorów istnieje krawędź, której końce są pomalowane tymi kolorami. Ale dlaczego "tych kolorów jest \(\displaystyle{ k-1}\)"? Tzn. właściwie których? Brzmi to tak, jakbyś podał jakiś pierwszy sposób rozwiązania, nie wykorzystujący \(\displaystyle{ k}\)-krytyczności. Jakoś tego nie widzę.Downonmyluck pisze:Zauważ, że każdy wierzchołek danego koloru musi być połączony z jakimkolwiek wierzchołkiem o innym kolorze. W przeciwnym razie można byłoby znaleźć lepsze kolorowanie. Tak więc tych kolorów (poza kolorem, którym pokolorwany jest rozpatrywany wierzchołek) jest \(\displaystyle{ k-1}\). Można też zrobić to nie wprost i wykorzystać k-krytyczność.
OK, przy czym zgodziłbym się raczej z Mruczkiem, że po wycięciu \(\displaystyle{ v}\) liczba chromatyczna jest równa co najwyżej \(\displaystyle{ k-1}\), a nie dokładnie \(\displaystyle{ k-1}\).Niech \(\displaystyle{ v \in V}\) będzie wierzchołkiem o najmniejszym stopniu i załóżmy, że \(\displaystyle{ \delta(G) < k-1}\).
Wtedy liczba chromatyczna \(\displaystyle{ G-v}\) wynosi \(\displaystyle{ k-1}\) i oznaczmy zbiór kolorów \(\displaystyle{ A = \left\{ 1,2,...,k-1\right\}}\). Widać, że z zasady szufladkowej istnieje taki kolor \(\displaystyle{ j \in A}\), którym nie został pokolorowany żaden z wierzchołków incydentych z \(\displaystyle{ v}\). W takim razie kolorując \(\displaystyle{ v}\) kolorem \(\displaystyle{ j}\) otrzymujemy dobre pokolorowane grafu \(\displaystyle{ G}\) na \(\displaystyle{ k-1}\) kolorów. Sprzeczność.
-
- Użytkownik
- Posty: 44
- Rejestracja: 25 kwie 2015, o 12:24
- Płeć: Mężczyzna
- Podziękował: 11 razy
- Pomógł: 3 razy
Twierdzenie o minimalnym stopniu w grafie k-krytycznym
Przepraszam, napisałem bzdurę. Miałem w głowie nierówność \(\displaystyle{ e(G) \ge {k \choose 2}}\), gdzie \(\displaystyle{ k}\) jest liczbą chromatyczną. Innymi słowy między dowolnymi zbiorami niezależnych wierzchołków (gdzie są one pokolorowane tym samym kolorem) musi istnieć co najmniej jedna krawędź, inaczej moglibyśmy zdefiniować lepsze kolorowanie.Majeskas pisze:
Nie całkiem rozumiem. Chciałeś chyba powiedzieć tyle, że przy optymalnym kolorowaniu dla każdej pary kolorów istnieje krawędź, której końce są pomalowane tymi kolorami. Ale dlaczego "tych kolorów jest \(\displaystyle{ k-1}\)"? Tzn. właściwie których? Brzmi to tak, jakbyś podał jakiś pierwszy sposób rozwiązania, nie wykorzystujący \(\displaystyle{ k}\)-krytyczności. Jakoś tego nie widzę.