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
AABBCCDDEEFF011000101000110010000011001101000110

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

deg(A) =
2.Łatwy

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

|V| = 16
|E| =
3.Średni
ABCDECykl 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| = 5|E| = 5
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
4.Średni

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

|V| = 12|E| = 17
k =
5.Trudny
5151212106710ABCDEF

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
1145815527ABCDEF

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

Klucz odpowiedzi

  1. 1. deg(A) = 2
  2. 2. |E| = 15
  3. 3. Ścieżka Eulera, bez cyklu
  4. 4. k = 6
  5. 5. d(F) = 22
  6. 6. E

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