Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

Z Studia Informatyczne
< Matematyka dyskretna 1
Wersja z dnia 15:04, 3 paź 2021 autorstwa Luki (dyskusja | edycje) (Zastępowanie tekstu - "<div class="thumb t(.*)"><div style="width:(.*)px;"> <flash>file=(.*)\.swf\|width=(.*)\|height=(.*)<\/flash> <div\.thumbcaption>(.*)<\/div><\/div> <\/div>" na "$4x$5px|thumb|$1|$6")
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Grafy III

Ćwiczenie 1

Przedstaw graf nieplanarny, który nie jest homeomorficzny ani ściągalny do oraz . Dlaczego nie jest to kontrprzykład dla twierdzeń 14.2 oraz 14.3?

Wskazówka
Rozwiązanie

Ćwiczenie 2

W pewnym wielościanie wszystkie ściany są pięciokątami i sześciokątami. Ile jest ścian pięciokątnych, jeżeli w każdym wierzchołku spotykają się dokładnie trzy ściany?

Wskazówka
Rozwiązanie

Ćwiczenie 3

Pokaż, że dla spójnego, prostego grafu planarnego o co najmniej trzech wierzchołkach zachodzi



Wskazówka
Rozwiązanie

Ćwiczenie 4

Pokaż, że spójny graf planarny o co najmniej jednym wierzchołku posiada wierzchołek o stopniu nie większym niż .

Wskazówka
Rozwiązanie

Ćwiczenie 5

Znajdź liczbę chromatyczną -wymiarowej kostki , czyli grafu, którego wierzchołki to ciągi , gdzie , a krawędzie łączą te ciągi, które różnią się tylko na jednej pozycji.

Wskazówka
Rozwiązanie

Ćwiczenie 6

Nie korzystając z Twierdzenia 14.13 o czterech barwach pokaż, że graf planarny bez trójkątów jest czterokolorowalny.

Wskazówka
Rozwiązanie