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 einfacher Graph hat 6 Knoten mit den Graden 4, 3, 2, 2, 2, 1. Wie viele Kanten |E| hat er?

deg: 4, 3, 2, 2, 2, 1
|E| =
2.Leicht
ABCDEF

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

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

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

4 × deg 32 × deg 43 × deg 53 × deg 2
L =
4.Mittel

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

2 × deg 4
L =
5.Schwer
121817133261019ABCDEF

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

Start: Dk = 4
  1. 1Kante AB
  2. 2Kante AC
  3. 3Kante BC
  4. 4Kante BD
  5. 5Kante CE
  6. 6Kante DE
  7. 7Kante DF
  8. 8Kante EF
  9. 9Kante BE
6.Schwer
861215126131167ABCDEFG

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. |E| = 7
  2. 2. E
  3. 3. L = 19
  4. 4. L = 6
  5. 5. Kante BD
  6. 6. d(F) = 25

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