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

Graf prosty: liczba wierzchołków 7, stopnie 4, 3, 2, 2, 2, 2, 1. Ile krawędzi |E| ma ten graf?

deg: 4, 3, 2, 2, 2, 2, 1
|E| =
2.Łatwy

Graf prosty: liczba wierzchołków 5, stopnie 3, 3, 2, 2, 2. Ile krawędzi |E| ma ten graf?

deg: 3, 3, 2, 2, 2
|E| =
3.Ś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 =
4.Średni

Graf spójny: liczba wierzchołków 20, liczba krawędzi 25. Ile krawędzi k trzeba usunąć, aby zostało drzewo rozpinające?

|V| = 20|E| = 25
k =
5.Trudny
4579110291513ABCDEFG

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) =
6.Trudny
91981811207ABCDE

Algorytm Kruskala buduje minimalne drzewo rozpinające. Kliknij krawędź, którą dodaje jako krawędź numer 4; pominięte krawędzie się nie liczą.

k = 4
  1. 1krawędź AB
  2. 2krawędź AC
  3. 3krawędź BC
  4. 4krawędź BD
  5. 5krawędź CE
  6. 6krawędź DE
  7. 7krawędź BE

Klucz odpowiedzi

  1. 1. |E| = 8
  2. 2. |E| = 6
  3. 3. H = 2520
  4. 4. k = 6
  5. 5. d(F) = 15
  6. 6. krawędź BD

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