Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

Z Studia Informatyczne
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