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 grafu 4-regularnego: 9 (każdy wierzchołek ma stopień 4). Ile ma krawędzi |E|?

n = 9k = 4
|E| =
2.Łatwy

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

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

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

|V| = 18|E| = 20
k =
5.Trudny
71417312120ABCDE

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

start: Ak = 2
  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
7148141057151ABCDEFG

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) =

Klucz odpowiedzi

  1. 1. |E| = 18
  2. 2. |E| = 6
  3. 3. Cykl Eulera
  4. 4. k = 3
  5. 5. krawędź BD
  6. 6. d(F) = 20

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