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 Wald (ein Graph ohne Kreise) hat 27 Knoten und 5 Zusammenhangskomponenten. Wie viele Kanten |E| hat er?

|V| = 27c = 5
|E| =
2.Leicht
ABCDEFG

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

|V| = 7
Σ deg =
3.Mittel

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

|V| = 10|E| = 18
k =
4.Mittel

Wie viele verschiedene Hamilton-Kreise H hat der vollständige Graph K4? Kreise, die sich nur im Startknoten oder in der Richtung unterscheiden, zählen als gleich.

K4
H =
5.Schwer
8313215124181619ABCDEFG

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

Start: Ak = 3
  1. 1Kante AB
  2. 2Kante AC
  3. 3Kante BC
  4. 4Kante BD
  5. 5Kante CE
  6. 6Kante DE
  7. 7Kante EF
  8. 8Kante GB
  9. 9Kante GC
  10. 10Kante GE
6.Schwer
ABCDE

Wie viele geschlossene Wege der Länge 2 beginnen und enden bei C? Ein Weg darf Knoten und Kanten wiederholen. Nenne die Zahl N.

M = AdjazenzmatrixL = 2
N =

Lösungsschlüssel

  1. 1. |E| = 22
  2. 2. Σ deg = 18
  3. 3. k = 9
  4. 4. H = 3
  5. 5. Kante BD
  6. 6. N = 3

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