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, 3, 2, 1, 1. Wie viele Kanten |E| hat er?

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

Ein Baum hat 35 Knoten. Wie viele Kanten |E| hat er?

|V| = 35
|E| =
3.Mittel

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

4 × deg 33 × deg 43 × deg 52 × deg 2
L =
4.Mittel
ABCDEEuler-KreisEuler-Weg, kein Kreiskeines von beiden

Hat der zusammenhängende Graph einen Euler-Kreis, einen Euler-Weg, der kein Kreis ist, oder keines von beiden? Klicke deine Antwort an.

|V| = 5|E| = 6
  1. 1Euler-Kreis
  2. 2Euler-Weg, kein Kreis
  3. 3keines von beiden
5.Schwer
17834111215110ABCDEFG

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

k = 5
  1. 1Kante AC
  2. 2Kante BC
  3. 3Kante CE
  4. 4Kante DE
  5. 5Kante DF
  6. 6Kante EF
  7. 7Kante GB
  8. 8Kante GC
  9. 9Kante GE
6.Schwer
5131515121211113ABCDEF

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

Start: AZiel: D
d(D) =

Lösungsschlüssel

  1. 1. |E| = 7
  2. 2. |E| = 34
  3. 3. L = 21
  4. 4. keines von beiden
  5. 5. Kante DF
  6. 6. d(D) = 20

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