Matematyka dyskretna 1/Ćwiczenia 13: Grafy II

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Grafy II

Ćwiczenie 1

Kostka -wymiarowa jest grafem, którego wierzchołki to ciągi , gdzie , a krawędzie łączą te ciągi, które różnią się tylko na jednej pozycji. Oblicz liczbę wierzchołków, krawędzi oraz rozmiar najdłuższego cyklu.

Wskazówka
Rozwiązanie

Ćwiczenie 2

Dla jakich wartości grafy , , są eulerowskie.

Wskazówka
Rozwiązanie

Ćwiczenie 3

Przedstaw cztery pięciowierzchołkowe grafy -- kolejno graf który:

  • nie jest hamiltonowski i nie jest eulerowski
  • nie jest hamiltonowski, ale jest eulerowski
  • jest hamiltonowski i nie jest eulerowski
  • jest hamiltonowski i eulerowski.
Wskazówka
Rozwiązanie

Rozwiązanie jest przedstawione na rysunku.

Ćwiczenie 4

Dla jakich wartości grafy , , są hamiltonowskie.

Wskazówka
Rozwiązanie
Graf Petersena

Ćwiczenie 5

Czy graf Petersena (patrz rysunek) ma ścieżkę Hamiltona.

Rozwiązanie

Ćwiczenie 6

Podaj przykład grafu ilustrujący, że warunek występujący w Twierdzeniu Diraca 13.5 nie może być zastąpiony warunkiem .

Wskazówka
Rozwiązanie

Ćwiczenie 7

Wykaż, że elementowy jest hamiltonowski jeśli tylko ma przynajmniej krawędzi. Podaj przykład grafu niehamiltonowskiego z wierzchołkami i krawędziami.

Wskazówka
Rozwiązanie

Ćwiczenie 8

Wykaż, że każde drzewo jest grafem dwudzielnym. Które drzewa są pełnymi grafami dwudzielnymi?

Wskazówka
Rozwiązanie

Ćwiczenie 9

Udowodnij wierzchołkową wersję Twierdzenia Mengera.

Wskazówka
Rozwiązanie

Ćwiczenie 10

Korzystając z Twierdzenia Mengera udowodnij Twierdzenie Halla o skojarzeniach w grafach dwudzielnych.

Rozwiązanie