szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 15 maja 2014, o 18:58 
Użytkownik

Posty: 1920
Lokalizacja: Warszawa
Witam,

n to dodatnia liczba naturalna.
Pokazać, że (x-n) jest czynnikiem wielomianu P_G(x) wtw gdy n < K(G)
Za K uważam liczbę chromatyczną. Zaś za literę P wielomian chromatyczny.

Chciałbym prosić o wsparcie przy tym dowodzie.

Spróbuję najpierw powiedzieć co w ogóle rozumiem z tego twierdzenia.

Najpierw z lewa na prawą.

Wiadomo więc, że (x-n) jest czynnikiem wielomianu chromatycznego. Oznacza to, że co najmniej jeden z wierzchołków ma stopień choćby n. Dlatego, że decydując się malować jeden z węzłów mamy do wyboru x-n kolorów, a więc któryś z węzłów ma taki stopień (co najmniej taki). No nie wiem czy to dobre rozumowanie...
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2014, o 06:56 
Gość Specjalny

Posty: 5960
Lokalizacja: Toruń
Jak (x-n) jest składnikiem tego wielomianu to znaczy, że nie istnieje kolorowanie przy użyciu n kolorów i de facto to tyle.
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2014, o 19:33 
Użytkownik

Posty: 1920
Lokalizacja: Warszawa
Tak, to jest prawda. Okazuje się, że za pomocą n kolorów można pomalować na 0 sposobów.

Ale dlaczego od razu to oznacza, że liczba chromatyczna musi być większa ?
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2014, o 21:14 
Użytkownik

Posty: 5101
Lokalizacja: 52°16'37''N 20°52'45''E
Bo jak nie możesz pokolorować n kolorami, to tym bardziej nie pokolorujesz k kolorami dla k<n. Każde k-kolorowanie jest też n-kolorowaniem.
Góra
Mężczyzna Offline
PostNapisane: 17 maja 2014, o 12:49 
Użytkownik

Posty: 1920
Lokalizacja: Warszawa
Tak, to jest prawda rzeczywiście. Więc ja sformalizuję:

z lewej na prawą:

Załóżmy, że (x-n) jest czynnikiem. Wówczas dla tej liczby kolorów (n) mamy zero sposobów kolorowania grafu. A więc jasne jest, że żadna liczba mniejsza też nie starczy, stąd liczba chromatyczna musi być większa

W drugą stronę równie łatwo.

Załóżmy, że liczba chromatyczna jest większa. A więc nie można pokolorować na mniejszą ilość kolorów, tzn że jest zero sposobów, a więc wielomian chromatyczny musi się zerować dla tej wartości. Tak więc ten czynnik na prawdę istnieje.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile różnych dzielników ma liczba  Anonymous  8
 Drzewo a graf dwudzielny?  Anonymous  1
 Graf Samodopełniający  Anonymous  1
 Ilu jest uczniów w klasie jesli wiadomo że liczba utworzo  Acura_100  5
 wykazać że istnieje liczba całkowita podzielna przez 17..  noob  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl