1.Uzasadnić że indeks chromatyczny 3-regularnego grafu hamiltonowskiego jest równy 3.
2.Uzasadnić że dla grafu o m krawędziach prawdziwa jest nierówność licz. chromatyczna \(\displaystyle{ \le 0.5+ \sqrt{0,25+2m}}\)
Teoria grafów-1. indeks chromatyczny, 2.liczba chromatyczna
-
silvaran
- Użytkownik
- Posty: 1300
- Rejestracja: 6 sty 2009, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Warszawa
- Podziękował: 60 razy
- Pomógł: 123 razy
Teoria grafów-1. indeks chromatyczny, 2.liczba chromatyczna
Zad 1
3 regularny -> parzysta ilość wierzchołków (łatwo dowieść)
Hamiltonowski -> można go narysować w ten sposób: cykl rozpinający + dodatkowe krawędzie wewnątrz (po jednej z każdego wierzchołka)
wystarczy teraz wykazać, że skoro jest parzysta liczba wierzchołków, to cykl Hamiltona można pokolorować na dwa kolory. A dodatkowe krawędzie wewnątrz na kolor 3, bo żadna ze środka nie sąsiaduje z inną (bo graf jest 3 regularny)
--dopisek po 14:00--
Jak ciekawostkę moge powiedzieć, że zrobiłem to zadanie dziś rano i trzy godziny później miałem takie samo zadanie na egzaminie z dyskretnej
3 regularny -> parzysta ilość wierzchołków (łatwo dowieść)
Hamiltonowski -> można go narysować w ten sposób: cykl rozpinający + dodatkowe krawędzie wewnątrz (po jednej z każdego wierzchołka)
wystarczy teraz wykazać, że skoro jest parzysta liczba wierzchołków, to cykl Hamiltona można pokolorować na dwa kolory. A dodatkowe krawędzie wewnątrz na kolor 3, bo żadna ze środka nie sąsiaduje z inną (bo graf jest 3 regularny)
--dopisek po 14:00--
Jak ciekawostkę moge powiedzieć, że zrobiłem to zadanie dziś rano i trzy godziny później miałem takie samo zadanie na egzaminie z dyskretnej