szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 19:35 
Użytkownik

Posty: 7
Lokalizacja: Warszawa
Witam.
Próbuję uporać się z następującym zadaniem:

Wykaż, że dla k będącego długością najdłuższej ścieżki w grafie, zachodzi: x  \le k+1, gdzie x to liczba chromatyczna grafu.

Jakieś wskazówki?
Pozdrawiam.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 19:45 
Gość Specjalny

Posty: 5756
Lokalizacja: Toruń
To nie jest prawdą. Rozważ dowolny cykl C_n, dla n \geq 4. Liczba chromatyczna x=2 lub x=3 (w zależności od n), zaś k = n.
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 19:48 
Użytkownik

Posty: 7
Lokalizacja: Warszawa
Przepraszam, odwrotnie zapisałem nierówność. Już poprawione.
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 20:20 
Gość Specjalny

Posty: 5756
Lokalizacja: Toruń
Ustalmy wierzchołek v w G. Rozważ drzewo rozpinające ten graf wygenerowane przez DFS-a o korzeniu w v. Wtedy wysokość tego drzewa to co najwyżej k. Z konstrukcji drzewa wynika, że wierzchołki na głębokości d w tym drzewie nie są połączone krawędziami. Możemy je zatem pokolorować tym samym kolorem. Zatem na głębokości 1 malujemy kolorem c_1, na głębokości 2 kolorem c_2, ...., na głębokości k kolorem c_k. Na koniec wierzchołek v malujemy kolorem c_{k+1}. Mamy zatem pokolorowanie k+1 kolorami, więc
\chi(G) \leq k+1.
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2018, o 22:03 
Użytkownik

Posty: 1083
Lokalizacja: Lublin/Warszawa
W rozw. zad. 6 stąd: http://sma.epfl.ch/~moric/gt2012/sol7.pdf jest też inne rozwiązanie.

Btw. te zadanka z kursu teorii grafów są fajne: http://sma.epfl.ch/~moric/gt2012/.

Jeszcze inaczej: indukcja w silnym sensie po długości najdłuższej ścieżki w grafie.
Pierwszy krok: długość najdłuższej ścieżki to 0. Wtedy graf to zbiór niezależny, można pokolorować go jednym kolorem.
Krok indukcyjny: Zał, że długość najdłuższej ścieżki w grafie to l. Znajdujemy w grafie maksymalny zbiór niezależny X. Kolorujemy go jednym kolorem i usuwamy go z grafu, trzeba pokazać, że pozostały graf da się pokolorować l kolorami. Pokażemy, że w pozostałym grafie długość najdłuższej ścieżki to l - 1, wtedy z założenia indukcyjnego będzie można go pokolorować l kolorami.
Przypuśćmy nie wprost, że w pozostałym grafie istnieje ścieżka długości l. Skoro w X nie było żadnego wierzchołka z tej ścieżki to znaczy, że każdy wierzchołek tej ścieżki sąsiaduje z jakimś wierzchołkiem z X, w szczególności wierzchołek na końcu tej ścieżki sąsiaduje z wierzchołkiem v \in X. Przedłużamy tą ścieżkę o wierzchołek v, dostając ścieżkę długości l + 1, ale z założenia długość najdłuższej ścieżki w tym grafie nie przekraczała l, sprzeczność.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 kocykl w grafie  matmastosowana  0
 Liczba ciągów naprzemiennych  gblablabla  0
 liczba permutacji - zadanie 7  waliant  8
 ktora liczba jest najwieksza  nice88  1
 Liczba permutacji zbioru (n-1)  jagodka13  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl