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
AABBCCDD0111100010001000

Pokazano macierz sąsiedztwa grafu prostego nieskierowanego. Ile krawędzi |E| ma ten graf?

|E| =
2.Łatwy

Ile krawędzi |E| ma pełny graf dwudzielny K2,8?

K2,8
|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| = 9
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
4.Średni

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

|V| = 14|E| = 20
k =
5.Trudny
173108161415ABCDE

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ź BE
6.Trudny
1331962110520ABCDEF

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

start: Bk = 5
  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ź DF
  8. 8krawędź EF
  9. 9krawędź BE

Klucz odpowiedzi

  1. 1. |E| = 3
  2. 2. |E| = 16
  3. 3. ani jedno, ani drugie
  4. 4. k = 7
  5. 5. krawędź BC
  6. 6. krawędź EF

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