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: 11. Ile krawędzi |E| ma to drzewo?

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

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

|V| = 32c = 4
|E| =
3.Średni
ABCDEFGCykl EuleraŚcieżka Eulera, bez cykluani jedno, ani drugie

Czy graf spójny ma cykl Eulera, ścieżkę Eulera, która nie jest cyklem, czy żadne z nich? Kliknij odpowiedź.

|V| = 7|E| = 7
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
4.Średni

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

|V| = 15|E| = 18
k =
5.Trudny
913211131412ABCDEF

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
141061315212517ABCDEFG

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

start: Ck = 4
  1. 1krawędź AB
  2. 2krawędź AC
  3. 3krawędź BD
  4. 4krawędź CE
  5. 5krawędź DE
  6. 6krawędź DF
  7. 7krawędź GB
  8. 8krawędź GC
  9. 9krawędź GD

Klucz odpowiedzi

  1. 1. |E| = 10
  2. 2. |E| = 28
  3. 3. ani jedno, ani drugie
  4. 4. k = 4
  5. 5. d(F) = 12
  6. 6. krawędź BD

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