Arbeitsblatt Graphentheorie mit Lösungen

Kostenloses Arbeitsblatt Graphentheorie zum Ausdrucken: 6 Aufgaben von leicht bis Prüfungsniveau, mit Lösungsschlüssel. Drucke es aus oder speichere es als PDF.

Neues ArbeitsblattOnline mit Tipps üben

Für Lehrkräfte: kostenlos ausdrucken, kopieren und im Unterricht verwenden. Jedes neue Arbeitsblatt hat neue Werte und einen eigenen Lösungsschlüssel. Über einen Link zu ExamProblems auf Ihrer Kursseite freuen wir uns.

Name: ____________________   Datum: ____________

1.Leicht
ABCDE

Genau ein Knoten des Graphen hat den Grad 1. Klicke ihn an.

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
2.Leicht
ABCDE

Genau ein Knoten des Graphen hat den Grad 2. Klicke ihn an.

deg = 2
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
3.Mittel

Ein zusammenhängender Graph hat 8 Knoten und 13 Kanten. Wie viele Kanten k müssen entfernt werden, damit ein aufspannender Baum übrig bleibt?

|V| = 8|E| = 13
k =
4.Mittel

Ein zusammenhängender Graph hat 10 Knoten und 21 Kanten. Wie viele Kanten k müssen entfernt werden, damit ein aufspannender Baum übrig bleibt?

|V| = 10|E| = 21
k =
5.Schwer
201419731111012ABCDEFG

Der Prim-Algorithmus baut einen minimalen aufspannenden Baum auf, beginnend bei Knoten D. Klicke die Kante an, die er als Kante Nummer 3 hinzufügt.

Start: Dk = 3
  1. 1Kante AB
  2. 2Kante BD
  3. 3Kante CE
  4. 4Kante DE
  5. 5Kante DF
  6. 6Kante GB
  7. 7Kante GC
  8. 8Kante GD
  9. 9Kante GE
6.Schwer
61483871514ABCDEF

Bestimme mit dem Dijkstra-Algorithmus die Länge d(F) des kürzesten Weges von A nach F im gewichteten Graphen.

Start: AZiel: F
d(F) =

Lösungsschlüssel

  1. 1. D
  2. 2. C
  3. 3. k = 6
  4. 4. k = 12
  5. 5. Kante GD
  6. 6. d(F) = 24

Vollständige Schritt-für-Schritt-Lösungen: Übe dieses Thema auf examproblems.com.