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
ABCDE

Bestimme die Summe der Grade aller Knoten des gezeigten Graphen, Σ deg.

|V| = 5
Σ deg =
2.Leicht

Ein Baum hat 27 Kanten. Wie viele Knoten |V| hat er?

|E| = 27
|V| =
3.Mittel

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

|V| = 20|E| = 22
k =
4.Mittel

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

|V| = 17|E| = 26
k =
5.Schwer
13919145461810816ABCDEFG

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 CE
  5. 5Kante DE
  6. 6Kante DF
  7. 7Kante EF
  8. 8Kante GB
  9. 9Kante GC
  10. 10Kante GD
  11. 11Kante GE
6.Schwer
4761911149141ABCDEFG

Der Dijkstra-Algorithmus läuft von A aus. Klicke den Knoten an, der in Runde 6 abgeschlossen (endgültig gemacht) wird; A selbst ist Runde 1.

Start: ARunde 6
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G

Lösungsschlüssel

  1. 1. Σ deg = 10
  2. 2. |V| = 28
  3. 3. k = 3
  4. 4. k = 10
  5. 5. Kante GD
  6. 6. D

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