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

Ile krawędzi |E| ma graf pełny K5?

K5
|E| =
2.Łatwy
ABCDEF

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

|V| = 6
Σ deg =
3.Średni

Drzewo ma 2× wierzchołek stopnia 3, 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?

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

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

4 × deg 53 × deg 2
L =
5.Trudny
1411015611110134ABCDEFG

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

start: Akoniec: G
d(G) =
6.Trudny
31120716126ABCDE

Algorytm Prima buduje minimalne drzewo rozpinające, zaczynając od wierzchołka E. Kliknij krawędź, którą dodaje jako krawędź numer 4.

start: Ek = 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| = 10
  2. 2. Σ deg = 16
  3. 3. L = 13
  4. 4. L = 14
  5. 5. d(G) = 11
  6. 6. krawędź AC

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