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

Liczba wierzchołków drzewa: 25. Ile krawędzi |E| ma to drzewo?

|V| = 25
|E| =
2.Łatwy

Las (graf bez cykli): liczba wierzchołków 13, liczba składowych spójności 5. Ile krawędzi |E| ma ten las?

|V| = 13c = 5
|E| =
3.Średni

Drzewo ma 4× wierzchołek stopnia 4, 3× 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 43 × deg 53 × deg 2
L =
4.Średni

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

|V| = 19|E| = 22
k =
5.Trudny
318141112101525ABCDEFG

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

start: Gk = 2
  1. 1krawędź AC
  2. 2krawędź BC
  3. 3krawędź BD
  4. 4krawędź CE
  5. 5krawędź EF
  6. 6krawędź GB
  7. 7krawędź GC
  8. 8krawędź GD
  9. 9krawędź GE
6.Trudny
21529121359ABCDEF

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

start: Akoniec: E
d(E) =

Klucz odpowiedzi

  1. 1. |E| = 24
  2. 2. |E| = 8
  3. 3. L = 19
  4. 4. k = 4
  5. 5. krawędź GE
  6. 6. d(E) = 11

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