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
AABBCCDDEE0100010111010010100101110

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

|E| =
2.Łatwy

Liczba krawędzi drzewa: 28. Ile wierzchołków |V| ma to drzewo?

|E| = 28
|V| =
3.Średni
ABCDEFGCykl EuleraŚcieżka Eulera, bez cykluani jedno, ani drugie

Czy graf spójny ma cykl Eulera, ścieżkę Eulera, która nie jest cyklem, czy żadne z nich? Kliknij odpowiedź.

|V| = 7|E| = 12
  1. 1Cykl Eulera
  2. 2Ścieżka Eulera, bez cyklu
  3. 3ani jedno, ani drugie
4.Średni

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

|V| = 7|E| = 12
k =
5.Trudny
2201911041816ABCDEF

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

|V| = 6|E| = 8
W =
6.Trudny
81874912ABCDE

Algorytm Kruskala buduje minimalne drzewo rozpinające. Kliknij krawędź, którą dodaje jako krawędź numer 2; pominięte krawędzie się nie liczą.

k = 2
  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. |V| = 29
  3. 3. Cykl Eulera
  4. 4. k = 6
  5. 5. W = 36
  6. 6. krawędź BE

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