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
ABCDEFG

Znajdź sumę stopni wszystkich wierzchołków pokazanego grafu, Σ deg.

|V| = 7
Σ deg =
2.Łatwy
AABBCCDDEEFF001000001110110010010001011001000110

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

|E| =
3.Średni

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

|V| = 8|E| = 8
k =
4.Średni

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

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

start: Ck = 5
  1. 1krawędź AB
  2. 2krawędź AC
  3. 3krawędź BC
  4. 4krawędź CE
  5. 5krawędź DE
  6. 6krawędź DF
  7. 7krawędź EF
  8. 8krawędź BE
6.Trudny
19714898389ABCDEFG

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. Σ deg = 18
  2. 2. |E| = 7
  3. 3. k = 1
  4. 4. L = 5
  5. 5. krawędź AB
  6. 6. d(F) = 24

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