Repräsentation mit einer Nachbarschaftstabelle
Knoten und ihre Nachbarn
Wir betrachten weiterhin den folgenden Graphen:
Sämtliche Informationen dieses Graphen lassen sich z.B. so in einer Nachbarschaftstabelle darstellen:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 0 |
| B | 0 | 1 | 1 | 1 |
| C | 1 | 1 | 0 | 0 |
| D | 0 | 0 | 0 | 0 |
Lässt man in dieser Tabelle die Knotenbezeichner weg (man geht dann von einer bekannten Durchnummerierung der Knoten aus), so spricht man auch von einer Adjazenzmatrix.
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 |
Aufgabe 1
(a) Wie liest man die Nachbarschaftstabelle?
(b) Ergänze die Nachbarschaftstabelle so, dass sie den folgenden erweiterten Graphen beschreibt.
(c) Wie könnte man einen gewichteten Graphen mit Hilfe einer Nachbarschaftstabelle beschreiben?
Aufgabe 2
Wie könnte man eine Nachbarschaftstabelle (in Python) implementieren? Mache hierzu einen Vorschlag.