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

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

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

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

Ein Baum hat 4 Knoten vom Grad 4, 4 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 44 × deg 53 × deg 2
L =
4.Mittel

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

|V| = 20|E| = 24
k =
5.Schwer
1413196241811ABCDEFG

Bestimme das Gesamtgewicht W eines minimalen aufspannenden Baums des gewichteten Graphen.

|V| = 7|E| = 9
W =
6.Schwer
24115131710181911ABCDEFG

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

k = 6
  1. 1Kante AB
  2. 2Kante BC
  3. 3Kante BD
  4. 4Kante CE
  5. 5Kante DE
  6. 6Kante DF
  7. 7Kante GB
  8. 8Kante GC
  9. 9Kante GD
  10. 10Kante GE

Lösungsschlüssel

  1. 1. |E| = 5
  2. 2. B
  3. 3. L = 22
  4. 4. k = 5
  5. 5. W = 34
  6. 6. Kante DF

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