szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 wrz 2016, o 20:22 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Znalazłem to zadanie między innymi pod taką nazwą jak w temacie. Należy pokazać, że każdy wierzchołek w grafie k-krytycznym (tzn. takim, że \chi(G)=k i usunięcie jakiegokolwiek wierzchołka zmniejsza liczbę chromatyczną) ma stopień równy co najmniej k-1.
Góra
Mężczyzna Offline
PostNapisane: 2 wrz 2016, o 20:33 
Użytkownik

Posty: 45
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 k-1. Można też zrobić to nie wprost i wykorzystać k-krytyczność.

Niech v \in V będzie wierzchołkiem o najmniejszym stopniu i załóżmy, że \delta(G)  < k-1.
Wtedy liczba chromatyczna G-v wynosi k-1 i oznaczmy zbiór kolorów A = \left\{ 1,2,...,k-1\right\}. Widać, że z zasady szufladkowej istnieje taki kolor j  \in A, którym nie został pokolorowany żaden z wierzchołków incydentych z v. W takim razie kolorując v kolorem j otrzymujemy dobre pokolorowane grafu G na k-1 kolorów. Sprzeczność.
Góra
Mężczyzna Offline
PostNapisane: 2 wrz 2016, o 20:41 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Dowód nie wprost. Załóżmy, że w tym grafie istnieje wierzchołek stopnia mniejszego niż 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ż k - 1. Jest on połączony z co najwyżej k - 2 innymi wierzchołkami, więc można go pokolorować pozostałym k - 1-szym kolorem, więc cały graf ma liczbę chromatyczną nie większą niż k - 1, sprzeczność.
Góra
Mężczyzna Offline
PostNapisane: 2 wrz 2016, o 23:08 
Użytkownik

Posty: 1439
Lokalizacja: Warszawa
Dziękuję za odpowiedzi, i to tak szybkie. Właściwie nie było to trudne. Za szybko się zniechęciłem.

Downonmyluck napisał(a):
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 k-1. Można też zrobić to nie wprost i wykorzystać k-krytyczność.


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 k-1"? Tzn. właściwie których? Brzmi to tak, jakbyś podał jakiś pierwszy sposób rozwiązania, nie wykorzystujący k-krytyczności. Jakoś tego nie widzę.

Cytuj:
Niech v \in V będzie wierzchołkiem o najmniejszym stopniu i załóżmy, że \delta(G)  < k-1.
Wtedy liczba chromatyczna G-v wynosi k-1 i oznaczmy zbiór kolorów A = \left\{ 1,2,...,k-1\right\}. Widać, że z zasady szufladkowej istnieje taki kolor j  \in A, którym nie został pokolorowany żaden z wierzchołków incydentych z v. W takim razie kolorując v kolorem j otrzymujemy dobre pokolorowane grafu G na k-1 kolorów. Sprzeczność.


OK, przy czym zgodziłbym się raczej z Mruczkiem, że po wycięciu v liczba chromatyczna jest równa co najwyżej k-1, a nie dokładnie k-1.
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2016, o 00:30 
Użytkownik

Posty: 45
Majeskas napisał(a):

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 k-1"? Tzn. właściwie których? Brzmi to tak, jakbyś podał jakiś pierwszy sposób rozwiązania, nie wykorzystujący k-krytyczności. Jakoś tego nie widzę.


Przepraszam, napisałem bzdurę. Miałem w głowie nierówność e(G)  \ge  {k \choose 2}, gdzie 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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba chromatyczna a antyklika w grafie  MateuszGRT  2
 Wspólne krawędzie cyklu i rozcięcia w grafie  TrzyRazyCztery  0
 cykle w grafie 2-spójnym  forever17  0
 Ilość drzew o maksymalnym stopniu wierzchołka  Fray  0
 Ścieżka w grafie  bartek1801  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl