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
AABBCCDDEE0110010011100010100001100

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

|E| =
2.Łatwy

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

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

Drzewo ma 3× wierzchołek stopnia 5, 3× wierzchołek stopnia 2, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?

3 × deg 53 × deg 2
L =
4.Średni

Drzewo ma 3× wierzchołek stopnia 3, 2× wierzchołek stopnia 4, 4× wierzchołek stopnia 5, 4× wierzchołek stopnia 2, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?

3 × deg 32 × deg 44 × deg 54 × deg 2
L =
5.Trudny
51931113151442ABCDEFG

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ź GB
  9. 9krawędź GC
6.Trudny
35145718104ABCDEF

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| = 5
  2. 2. |E| = 6
  3. 3. L = 11
  4. 4. L = 21
  5. 5. krawędź AB
  6. 6. d(F) = 16

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