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 krawędzi drzewa: 39. Ile wierzchołków |V| ma to drzewo?

|E| = 39
|V| =
2.Łatwy
AABBCCDDEE0010000110110000100100010

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

deg(A) =
3.Średni

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

2 × deg 33 × deg 43 × deg 52 × deg 2
L =
4.Średni

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

|V| = 18|E| = 21
k =
5.Trudny
41384139382ABCDEF

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) =
6.Trudny
ABCDEF

Ile jest marszów o długości 3 z B do C? Marsz może powtarzać wierzchołki i krawędzie. Nazwij tę liczbę N.

M = macierz sąsiedztwaL = 3
N =

Klucz odpowiedzi

  1. 1. |V| = 40
  2. 2. deg(A) = 1
  3. 3. L = 19
  4. 4. k = 4
  5. 5. d(F) = 11
  6. 6. N = 4

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