Teoria grafów: karta pracy z odpowiedziami

Darmowa karta pracy do druku – Teoria grafów: 6 zadań od łatwych do poziomu egzaminu, z kluczem odpowiedzi. Wydrukuj ją lub zapisz jako PDF.

Nowa karta pracyĆwicz online z podpowiedziami

Dla nauczycieli: można bezpłatnie drukować, kopiować i używać na zajęciach. Każdy nowy arkusz ma nowe wartości i własny klucz odpowiedzi. Będziemy wdzięczni za link do ExamProblems na stronie kursu.

Imię: ____________________   Data: ____________

1.Łatwy
ABCDEFG

Znajdź sumę stopni wszystkich wierzchołków pokazanego grafu, Σ deg.

|V| = 7
Σ deg =
2.Łatwy

Ile krawędzi |E| ma pełny graf dwudzielny K4,10?

K4,10
|E| =
3.Średni
ABCDEFGCykl EuleraŚcieżka Eulera, bez cykluani jedno, ani drugie

Czy graf spójny ma cykl Eulera, ścieżkę Eulera, która nie jest cyklem, czy żadne z nich? Kliknij odpowiedź.

|V| = 7|E| = 12
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
4.Średni

Ile różnych cykli Hamiltona H ma graf pełny K8? Cykle różniące się tylko wierzchołkiem startowym lub kierunkiem liczą się jako ten sam.

K8
H =
5.Trudny
1431921291811ABCDEF

Znajdź łączną wagę W minimalnego drzewa rozpinającego grafu ważonego.

|V| = 6|E| = 8
W =
6.Trudny
121399415215108ABCDEFG

Użyj algorytmu Dijkstry, aby znaleźć długość d(F) najkrótszej ścieżki z A do F w grafie ważonym.

start: Akoniec: F
d(F) =

Klucz odpowiedzi

  1. 1. Σ deg = 14
  2. 2. |E| = 40
  3. 3. Cykl Eulera
  4. 4. H = 2520
  5. 5. W = 39
  6. 6. d(F) = 23

Pełne rozwiązania krok po kroku: ćwicz ten temat na examproblems.com.