Graphen als Tabellen
Ein Graph lässt sich gut mit einer Tabelle beschreiben. Das ist zwar nicht sehr anschaulich, bietet aber eine Reihe von anderen Vorteilen. Dabei gibt es verschiedene Möglichkeiten, wir beschränken uns auf sogenannte Nachbarschaftstabellen (→ „Adjazenzmatrizen“).
In jede Zeile wird eingetragen, durch wie viele Kanten die Knoten miteinander verbunden sind. Man sieht z.B. in der letzten Zeile rechts, wie viele Kanten vom Knoten D ausgehen. Von D zu A eine, zu B null, zu C zwei und zu D selbst eine.
Hinweis: Eine Schlinge wie hier im Knoten D wird je nach Sichtweise und Anwendung einfach oder doppelt gezählt. Es ist zwar 1 Kante, sie erhöht aber die Ordnung (Anzahl der zusammentreffenden Kantenenden) des Knotens um 2.
-
Füllt die Nachbarschaftstabellen zu den folgenden Graphen aus:
Vergleicht Tabellen und Graphen. Fällt euch etwas auf?
-
Begründet jeweils, warum die beiden Graphen nicht isomorph sind:
-
Zeichnet zur abgebildeten Nachbarschaftstabelle mindestens zwei Graphen, die unterschiedlich aussehen, aber isomorph sind. Tauscht eure Hefte aus und vergleicht die Graphen.
-
Betrachtet rückblickend Graphen und Tabellen auf diesem Blatt:
- Woran erkennt man in der Tabelle, ob es Schlingen gibt?
- Woran sieht man, ob es ein einfacher oder ein Multigraph ist?
- Wie kann man die Ordnung eines Knotens berechnen?
- Woran erkennt man, ob zwei Graphen isomorph sind?
Graphen als Tabellen: Herunterladen [odt][129 KB]
Graphen als Tabellen: Herunterladen [pdf][97 KB]
Weiter zu Übungen