Lösung von Aufgabe 3
Ein Graph ist durch die folgende Adjazenzmatrix gegebenen:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 1 | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 0 | 0 | 0 |
| C | 1 | 0 | 1 | 0 | 0 |
| D | 0 | 0 | 0 | 0 | 1 |
| E | 0 | 0 | 1 | 0 | 0 |
Bewerten Sie die Aussagen:
- a) Der Graph ist gewichtet.
- b) Der Graph ist gerichtet.
- c) Es gibt einen Pfad von D nach A.
- d) Der Graph ist zyklisch.
- e) Es gibt mindestens einen Knoten, der eine Kante auf sich selbst hat (d.h. eine Kante, die von diesem Knoten ausgeht und auf diesen Knoten zeigt).
- f) Es gibt einen isolierten Knoten.
Zur Lösung der Aufgabe bietet es sich an, den Graphen zu zeichnen:
Zu den Aussagen:
- a) Nein, es gibt keine Kantengewichte. Die Einsen bezeichnen nur, ob jeweils eine Kante vorhanden ist.
- b) Ja, da es z.B. eine Kante von A nach D gibt, aber keine von D nach A.
- c) Diese Aussage ist falsch.
- d) Der Pfad von A zu sich selbst ist ein geschlossener Pfad, der keine Kante zweimal enthält. Der Graph ist daher zyklisch.
Es gibt aber auch einen nichttrivialen Zyklus: A → D → E → C → A. - e) Das ist richtig: Die Knoten A und C haben jeweils eine Kante auf sich selbst.
- f) Das ist richtig: Der Knote B ist isoliert.