1.Leicht
Die Adjazenzmatrix eines einfachen ungerichteten Graphen ist gezeigt. Wie viele Kanten |E| hat der Graph?
|E| =
Arbeitsblatt Graphentheorie mit Lösungen
2.Leicht
Die Adjazenzmatrix eines einfachen ungerichteten Graphen ist gezeigt. Bestimme den Grad deg(E) von Knoten E.
deg(E) =
3.Mittel
Ein Baum hat 2 Knoten vom Grad 3, 4 Knoten vom Grad 5, 2 Knoten vom Grad 2, und alle seine anderen Knoten sind Blätter (Grad 1). Wie viele Blätter L hat er?
2 × deg 34 × deg 52 × deg 2
L =
4.Mittel
Ein zusammenhängender Graph hat 7 Knoten und 16 Kanten. Wie viele Kanten k müssen entfernt werden, damit ein aufspannender Baum übrig bleibt?
|V| = 7|E| = 16
k =
5.Schwer
Der Prim-Algorithmus baut einen minimalen aufspannenden Baum auf, beginnend bei Knoten F. Klicke die Kante an, die er als Kante Nummer 4 hinzufügt.
Start: Fk = 4
- 1Kante AB
- 2Kante AC
- 3Kante BC
- 4Kante BD
- 5Kante CE
- 6Kante DE
- 7Kante DF
- 8Kante BE
6.Schwer
Wie viele geschlossene Wege der Länge 2 beginnen und enden bei E? Ein Weg darf Knoten und Kanten wiederholen. Nenne die Zahl N.
M = AdjazenzmatrixL = 2
N =
Lösungsschlüssel
- 1. |E| = 6
- 2. deg(E) = 2
- 3. L = 16
- 4. k = 10
- 5. Kante AC
- 6. N = 3
Vollständige Schritt-für-Schritt-Lösungen: Übe dieses Thema auf examproblems.com.