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.