Aufgabe mit Lösung Ungerichteter Graph - Kantenmenge, Adjazenzmatrix etc.
Level 2 setzt Schulmathematik voraus. Geeignet für Schüler.
Gegeben ist ein ungerichteter Graph wie in der folgenden Illustration gezeigt:
Gib die Knotenmenge \(V_G\) und die Kantenmenge \(E_G\) an.
Gib alle Zyklen (ink. Schlingen) an.
Gib die Adjazenzmatrix an.
Lösungstipps
Benutze die Definition der Begriffe (siehe z.B. Wikipedia).
Lösung für (a)
Der abgebildete Graph \(G = (V_G, E_G)\) hat die folgende Knotenmenge:1\[ V_G = \{ A, B, C, D, E \} \]und die folgende Kantenmenge:2\[ E_G = \{ (A,B), (A,C), (B,A), (B,B), (B,D), (C,A), (C,C), (C,D), (E,D) \} \]
Lösung für (b)
Der Graph besitzt folgende geschlossenen Pfade (Zyklen):3\[ (A, B, D, C, A) \]4\[ (B, D, C, A, B) \]5\[ (D, C, A, B, D) \]6\[ (C, A, B, D, C) \]
Der Graph hat außerdem zwei Schlingen: \( (B,B) \) und \((C,C)\).
Lösung für (c)
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 1 | 0 | 1 | 0 |
| C | 1 | 0 | 1 | 1 | 0 | D | 0 | 1 | 1 | 0 | 1 | E | 0 | 0 | 0 | 1 | 0 |
