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 5, stopnie 4, 3, 2, 2, 1. Ile krawędzi |E| ma ten graf?

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

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

K4,10
|E| =
3.Średni

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

3 × deg 5
L =
4.Średni

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

K6
H =
5.Trudny
15319164691112ABCDEF

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

|V| = 6|E| = 9
W =
6.Trudny
5133411121414ABCDEFG

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

start: Arunda 6
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G

Klucz odpowiedzi

  1. 1. |E| = 6
  2. 2. |E| = 40
  3. 3. L = 11
  4. 4. H = 60
  5. 5. W = 34
  6. 6. C

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