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 Baum hat 16 Knoten. Wie viele Kanten |E| hat er?

|V| = 16
|E| =
2.Leicht
ABCDEFG

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

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

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

|V| = 20|E| = 28
k =
4.Mittel
ABCDEFEuler-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| = 6|E| = 7
  1. 1Euler-Kreis
  2. 2Euler-Weg, kein Kreis
  3. 3keines von beiden
5.Schwer
69151181012320ABCDEFG

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 BC
  3. 3Kante BD
  4. 4Kante DF
  5. 5Kante EF
  6. 6Kante GB
  7. 7Kante GC
  8. 8Kante GD
  9. 9Kante GE
6.Schwer
6815134613884ABCDEFG

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| = 15
  2. 2. G
  3. 3. k = 9
  4. 4. Euler-Kreis
  5. 5. Kante AB
  6. 6. d(F) = 21

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