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
AABBCCDD0101100000011010

Pokazano macierz sąsiedztwa grafu prostego nieskierowanego. Znajdź stopień deg(C) wierzchołka C.

deg(C) =
2.Łatwy
AABBCCDDEEFF011000101110110010010011011101000110

Pokazano macierz sąsiedztwa grafu prostego nieskierowanego. Ile krawędzi |E| ma ten graf?

|E| =
3.Średni

Drzewo ma 3× wierzchołek stopnia 3, 3× wierzchołek stopnia 4, 3× wierzchołek stopnia 5, 2× wierzchołek stopnia 2, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?

3 × deg 33 × deg 43 × deg 52 × deg 2
L =
4.Średni

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

K5
H =
5.Trudny
25389571ABCDEF

Algorytm Dijkstry rusza z A. Kliknij wierzchołek zatwierdzony (uczyniony stałym) w rundzie 4; sam A to runda 1.

start: Arunda 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
6.Trudny
33515131213ABCDEFG

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(C) = 1
  2. 2. |E| = 9
  3. 3. L = 20
  4. 4. H = 12
  5. 5. C
  6. 6. d(F) = 9

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