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
AABBCCDDEE0110010110110000100100010

Die Adjazenzmatrix eines einfachen ungerichteten Graphen ist gezeigt. Wie viele Kanten |E| hat der Graph?

|E| =
2.Leicht

Wie viele Kanten |E| hat der vollständige bipartite Graph K5,6?

K5,6
|E| =
3.Mittel
ABCDEEuler-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| = 5|E| = 6
  1. 1Euler-Kreis
  2. 2Euler-Weg, kein Kreis
  3. 3keines von beiden
4.Mittel

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

3 × deg 33 × deg 44 × deg 5
L =
5.Schwer
21262016491311ABCDEFG

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

Start: Gk = 4
  1. 1Kante AB
  2. 2Kante AC
  3. 3Kante BC
  4. 4Kante CE
  5. 5Kante DE
  6. 6Kante DF
  7. 7Kante EF
  8. 8Kante GC
  9. 9Kante GD
6.Schwer
11191389720ABCDEF

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

|V| = 6|E| = 8
W =

Lösungsschlüssel

  1. 1. |E| = 5
  2. 2. |E| = 30
  3. 3. keines von beiden
  4. 4. L = 23
  5. 5. Kante GC
  6. 6. W = 30

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