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
AABBCCDD0111100010011010

Die Adjazenzmatrix eines einfachen ungerichteten Graphen ist gezeigt. Bestimme den Grad deg(C) von Knoten C.

deg(C) =
2.Leicht
ABCDE

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

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

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

K8
H =
4.Mittel

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

K6
H =
5.Schwer
8135371811151620ABCDEFG

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 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
241715791ABCDE

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

|V| = 5|E| = 7
W =

Lösungsschlüssel

  1. 1. deg(C) = 2
  2. 2. B
  3. 3. H = 2520
  4. 4. H = 60
  5. 5. Kante GB
  6. 6. W = 16

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