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
AABBCCDD0001001001011010

Die Adjazenzmatrix eines einfachen ungerichteten Graphen ist gezeigt. Bestimme den Grad deg(A) von Knoten A.

deg(A) =
2.Leicht

Wie viele Kanten |E| hat der vollständige Graph K5?

K5
|E| =
3.Mittel

Wie viele verschiedene Hamilton-Kreise H hat der vollständige Graph K6? Kreise, die sich nur im Startknoten oder in der Richtung unterscheiden, zählen als gleich.

K6
H =
4.Mittel

Ein Baum hat 2 Knoten vom Grad 3, 2 Knoten vom Grad 4, 3 Knoten vom Grad 5, und alle seine anderen Knoten sind Blätter (Grad 1). Wie viele Blätter L hat er?

2 × deg 32 × deg 43 × deg 5
L =
5.Schwer
1620971718361915ABCDEFG

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

Start: Fk = 3
  1. 1Kante AC
  2. 2Kante BC
  3. 3Kante BD
  4. 4Kante DE
  5. 5Kante DF
  6. 6Kante EF
  7. 7Kante GB
  8. 8Kante GC
  9. 9Kante GD
  10. 10Kante GE
6.Schwer
181744624ABCDEFG

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. deg(A) = 1
  2. 2. |E| = 10
  3. 3. H = 60
  4. 4. L = 17
  5. 5. Kante BD
  6. 6. d(F) = 13

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