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

Graf prosty: liczba wierzchołków 7, stopnie 4, 4, 3, 3, 2, 1, 1. Ile krawędzi |E| ma ten graf?

deg: 4, 4, 3, 3, 2, 1, 1
|E| =
2.Łatwy

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

K5,8
|E| =
3.Średni

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

|V| = 14|E| = 22
k =
4.Ś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| = 12
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
5.Trudny
1719215618313ABCDEF

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

k = 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
6.Trudny
155261791611ABCDEF

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ź DE
  6. 6krawędź DF
  7. 7krawędź EF
  8. 8krawędź BE

Klucz odpowiedzi

  1. 1. |E| = 9
  2. 2. |E| = 40
  3. 3. k = 9
  4. 4. Cykl Eulera
  5. 5. krawędź AB
  6. 6. krawędź BD

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