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

Ein 3-regulärer Graph hat 4 Knoten (jeder Knoten hat den Grad 3). Wie viele Kanten |E| hat er?

n = 4k = 3
|E| =
2.Leicht

Ein einfacher Graph hat 5 Knoten mit den Graden 3, 2, 2, 2, 1. Wie viele Kanten |E| hat er?

deg: 3, 2, 2, 2, 1
|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 zusammenhängender Graph hat 9 Knoten und 14 Kanten. Wie viele Kanten k müssen entfernt werden, damit ein aufspannender Baum übrig bleibt?

|V| = 9|E| = 14
k =
5.Schwer
15974814101820ABCDEFG

Der Kruskal-Algorithmus baut einen minimalen aufspannenden Baum auf. Klicke die Kante an, die er als Kante Nummer 3 hinzufügt; übersprungene Kanten zählen nicht.

k = 3
  1. 1Kante AB
  2. 2Kante AC
  3. 3Kante CE
  4. 4Kante DE
  5. 5Kante DF
  6. 6Kante GB
  7. 7Kante GC
  8. 8Kante GD
  9. 9Kante GE
6.Schwer
1146146610415ABCDEFG

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

Start: AZiel: C
d(C) =

Lösungsschlüssel

  1. 1. |E| = 6
  2. 2. |E| = 5
  3. 3. H = 60
  4. 4. k = 6
  5. 5. Kante DF
  6. 6. d(C) = 7

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