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
ABCDE

Dokładnie jeden wierzchołek grafu ma stopień 3. Kliknij go.

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
2.Łatwy
ABCDEF

Dokładnie jeden wierzchołek grafu ma stopień 4. Kliknij go.

deg = 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
3.Średni

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

|V| = 17|E| = 27
k =
4.Średni
ABCDEFCykl 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| = 6|E| = 7
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
5.Trudny
1161020121753ABCDEF

Algorytm Kruskala buduje minimalne drzewo rozpinające. Kliknij krawędź, którą dodaje jako krawędź numer 3; pominięte krawędzie się nie liczą.

k = 3
  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ź EF
  8. 8krawędź BE
6.Trudny
15714111366915ABCDEFG

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
  7. 7G

Klucz odpowiedzi

  1. 1. B
  2. 2. E
  3. 3. k = 11
  4. 4. Cykl Eulera
  5. 5. krawędź AC
  6. 6. G

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