Direkt zum Inhalt

Aufgabe mit Lösung Ungerichteter Graph - Kantenmenge, Adjazenzmatrix etc.

Ungerichteter Graph
Level 2 (ohne höhere Mathematik)
Level 2 setzt Schulmathematik voraus. Geeignet für Schüler.

Gegeben ist ein ungerichteter Graph wie in der folgenden Illustration gezeigt:

Ungerichteter Graph
Ungerichteter Graph.
  1. Gib die Knotenmenge \(V_G\) und die Kantenmenge \(E_G\) an.

  2. Gib alle Zyklen (ink. Schlingen) an.

  3. 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)
ABCDE
A01100
B11010
C10110
D01101
E00010
Adjazenzmatrix

Physik-Formelsammlung fürs Abitur als E-Book

✅ Perfekt für die 11. bis 13. Klasse
✅ Enthält nützlichste Formeln
✅ Enthält Wertetabellen
✅ Formeln sind bunt gestaltet und visualisiert