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 5-regulärer Graph hat 6 Knoten (jeder Knoten hat den Grad 5). Wie viele Kanten |E| hat er?

n = 6k = 5
|E| =
2.Leicht
AABBCCDDEEFF011000101110110000010010010101000010

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

deg(B) =
3.Mittel
ABCDEFGEuler-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| = 7|E| = 7
  1. 1Euler-Kreis
  2. 2Euler-Weg, kein Kreis
  3. 3keines von beiden
4.Mittel

Ein Baum hat 2 Knoten vom Grad 5, und alle seine anderen Knoten sind Blätter (Grad 1). Wie viele Blätter L hat er?

2 × deg 5
L =
5.Schwer
73141345862012ABCDEFG

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

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

Wie viele Wege der Länge 3 führen von F nach A? Ein Weg darf Knoten und Kanten wiederholen. Nenne die Zahl N.

M = AdjazenzmatrixL = 3
N =

Lösungsschlüssel

  1. 1. |E| = 15
  2. 2. deg(B) = 4
  3. 3. keines von beiden
  4. 4. L = 8
  5. 5. Kante EF
  6. 6. N = 2

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