1.Leicht
Die Adjazenzmatrix eines einfachen ungerichteten Graphen ist gezeigt. Bestimme den Grad deg(D) von Knoten D.
deg(D) =
Arbeitsblatt Graphentheorie mit Lösungen
2.Leicht
Die Adjazenzmatrix eines einfachen ungerichteten Graphen ist gezeigt. Wie viele Kanten |E| hat der Graph?
|E| =
3.Mittel
Ein zusammenhängender Graph hat 8 Knoten und 13 Kanten. Wie viele Kanten k müssen entfernt werden, damit ein aufspannender Baum übrig bleibt?
|V| = 8|E| = 13
k =
4.Mittel
Ein Baum hat 4 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?
4 × deg 44 × deg 5
L =
5.Schwer
Bestimme das Gesamtgewicht W eines minimalen aufspannenden Baums des gewichteten Graphen.
|V| = 6|E| = 8
W =
6.Schwer
Bestimme mit dem Dijkstra-Algorithmus die Länge d(F) des kürzesten Weges von A nach F im gewichteten Graphen.
Start: AZiel: F
d(F) =
Lösungsschlüssel
- 1. deg(D) = 2
- 2. |E| = 3
- 3. k = 6
- 4. L = 22
- 5. W = 48
- 6. d(F) = 12
Vollständige Schritt-für-Schritt-Lösungen: Übe dieses Thema auf examproblems.com.