i

Repräsentation mit einer Nachbarschaftstabelle

Knoten und ihre Nachbarn

Wir betrachten weiterhin den folgenden Graphen:

Graph 1

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.

Graph 2

(c) Wie könnte man einen gewichteten Graphen mit Hilfe einer Nachbarschaftstabelle beschreiben?

Graph 2

Aufgabe 2

Wie könnte man eine Nachbarschaftstabelle (in Python) implementieren? Mache hierzu einen Vorschlag.

Suche

v
4.3.2.1.1
www.inf-schule.de/algorithmen/graphen/implementierung/station_repraesentation/nachbarschaftstabelle
www.inf-schule.de/4.3.2.1.1

Rückmeldung geben