Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

Z Studia Informatyczne
< Matematyka dyskretna 1
Wersja z dnia 17:35, 23 sie 2006 autorstwa Arek (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Grafy III

Ćwiczenie ex grafy Kuratowski kontr

Przedstaw graf nieplanarny, który nie jest homeomorficzny ani ściągalny do oraz . Dlaczego nie jest to kontrprzykład dla twierdzeń [th][th Kuratowski] oraz [th][th sciagalny k5k33]?

Wskazówka
Rozwiązanie

Ćwiczenie ex grafy pilka

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 ex m<=3n-6 dla plan

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

Wskazówka
Rozwiązanie

Ćwiczenie ex deg v<=5 dla plan

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 ex grafy

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 ex grafy

Nie korzystając z Twierdzenia [th][th 4barw planar] o czterech barwach pokaż, że graf planarny bez trójkątów jest czterokolorowalny.

Wskazówka
Rozwiązanie