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 6, stopnie 3, 3, 2, 2, 1, 1. Ile krawędzi |E| ma ten graf?

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

Pokazano macierz sąsiedztwa grafu prostego nieskierowanego. Znajdź stopień deg(D) wierzchołka D.

deg(D) =
3.Średni

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

|V| = 13|E| = 20
k =
4.Średni

Drzewo ma 3× wierzchołek stopnia 3, 2× 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 2
L =
5.Trudny
51113512122ABCDEF

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

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

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

start: Bk = 4
  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

Klucz odpowiedzi

  1. 1. |E| = 6
  2. 2. deg(D) = 3
  3. 3. k = 8
  4. 4. L = 5
  5. 5. F
  6. 6. krawędź AC

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