Nachbarschaftsmatrix und Nachbarschaftsliste
Graphen ohne Bild darstellen
Ein Computer kann mit einer Zeichnung wenig anfangen. Er braucht eine Darstellung durch Wörter über dem binären Alphabet {0, 1}. Das gelingt mit einer Nachbarschaftsmatrix oder einer Nachbarschaftsliste.
Merke: Nachbarschaftsmatrix
Eine Tabelle mit binären Einträgen nennt man Nachbarschaftsmatrix (Adjazenzmatrix) eines Graphen. Zwei Knoten heißen Nachbarn, wenn sie direkt durch eine Kante verbunden sind. Eine 1 bedeutet: Die Knoten sind Nachbarn, eine 0: Sie sind es nicht.
Zeige auf eine 1 in der Matrix, auf eine Kante oder einen Knoten.
G = (V, E)
V = {B, A, C, E, D}
E = {{A,B}, {B,C}, {A,C}, {A,D}, {A,E}, {E,D}, {C,D}}
| B | A | C | E | D | |
|---|---|---|---|---|---|
| B | 0 | 1 | 1 | 0 | 0 |
| A | 1 | 0 | 1 | 1 | 1 |
| C | 1 | 1 | 0 | 0 | 1 |
| E | 0 | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 1 | 0 |
Aufgabe 4: Vom Wort zum Graphen
Gegeben ist das Binärwort einer Nachbarschaftsmatrix:
010000001000000010010000000101000000
Aufgabe 4.2: Handelt es sich um einen ungerichteten oder einen gerichteten Graphen?
Aufgabe 4.3: Zeichne den zugehörigen Graphen. Die Knoten sind schon gesetzt.
Aufgabe 4.3: Zeichne den zugehörigen Graphen. Die Knoten sind schon gesetzt.
Nachbarschaftsliste
Merke: Nachbarschaftsliste
Bei der Nachbarschaftsliste (Adjazenzliste) wird für jeden Knoten eine Liste aller seiner Nachbarn (ungerichteter Graph) bzw. Nachfolger (gerichteter Graph) angegeben. Zeige auf eine Zeile:
a: b, d, d, e
b: a, c
c: b, d
d: a, a, c
e: a
Zwischen a und d gibt es zwei Kanten – darum steht d zweimal bei a und a zweimal bei d.
G = (V, E)
V = {b, c, a, e, d}
E = {{a,b}, {b,c}, {c,d}, {a,d}, {a,d}, {a,e}}