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

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

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

deg: 3, 2, 2, 2, 1
|E| =
3.Średni

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

|V| = 13|E| = 14
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| = 10
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
5.Trudny
81326147142ABCDEFG

Algorytm Dijkstry rusza z A. Kliknij wierzchołek zatwierdzony (uczyniony stałym) w rundzie 6; sam A to runda 1.

start: Arunda 6
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
6.Trudny
ABCDE

Ile jest marszów zamkniętych o długości 3, które zaczynają się i kończą w D? Marsz może powtarzać wierzchołki i krawędzie. Nazwij tę liczbę N.

M = macierz sąsiedztwaL = 3
N =

Klucz odpowiedzi

  1. 1. |E| = 4
  2. 2. |E| = 5
  3. 3. k = 2
  4. 4. ani jedno, ani drugie
  5. 5. F
  6. 6. N = 2

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