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
ABCDE

Dokładnie jeden wierzchołek grafu ma stopień 1. Kliknij go.

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
2.Łatwy
AABBCCDDEEFF011000101100110010010011001101000110

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

|E| =
3.Średni

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

|V| = 19|E| = 23
k =
4.Średni

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

4 × deg 33 × deg 44 × deg 5
L =
5.Trudny
514118103111ABCDEF

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

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

Znajdź łączną wagę W minimalnego drzewa rozpinającego grafu ważonego.

|V| = 7|E| = 9
W =

Klucz odpowiedzi

  1. 1. A
  2. 2. |E| = 8
  3. 3. k = 5
  4. 4. L = 24
  5. 5. E
  6. 6. W = 49

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