Zur Hauptnavigation springen [Alt]+[0] Zum Seiteninhalt springen [Alt]+[1]

Graphen als Tabellen – Lösung

  1. Nachbarschaftstabellen und isomorphe Graphen

    Abbildung 1 Lösung zu Graphen als Tabellen

    Die Tabellen von a) und b) sind identisch. Die beiden Graphen sind isomorph. Gleiches gilt für c) und d). Wenn Graphen identische Nachbarschaftstabellen besitzen, so sind sie isomorph. Dazu müssen die Knoten gleich benannt sein wie bei a) und b) bzw. c) und d). Achtung, die Umkehrung gilt nicht! Wenn zwei Graphen isomorph sind, müssen sie nicht identische Nachbarschaftstabellen besitzen, wie man bei d) und e) sieht. Es kommt auf die Bezeichnungen1 der Knoten an. Bei e) erhält man durch „Umnummerierung“ der Knoten (Vertauschung der Namen von A und D) die gleiche Tabelle wie bei c) oder d).

  2. Nicht isomorphe Graphen

    1. Anzahl der Knoten stimmt nicht überein.

    2. Anzahl der Kanten stimmt nicht überein.

    3. Knoten und Kantenanzahl stimmt überein, aber die Ordnungen der Knoten nicht.

    4. Knoten- und Kantenanzahl und Ordnungen stimmen zwar überein, das Nachbarschaftsgefüge stimmt aber nicht. Es gibt vielfältige Begründungen:

      Man erkennt dies z.B. daran, dass die beiden Knoten mit Ordnung 3 links direkt verbunden sind, rechts aber nicht. Oder man betrachtet das Gefüge der Knoten mit Ordnung 2. Links sind zwei Knoten der Ordnung 2 Nachbarn (direkt durch eine Kante verbunden), rechts nicht. Oder man erkennt, dass links ein Hamiltonkreis existiert, rechts aber nicht.

  3. Graphen zu Tabelle zeichnen

    Abbildung 2 Lösung zu Graphen als Tabellen

    Rechts sind 4 mögliche isomorphe Graphen zu sehen, sicher sehen eure aber ganz anders aus, oder?

  4. Reflexion

    1. Eine Schlinge erkennt man an einer 1 in der Diagonalen von links oben nach rechts unten.

    2. Wenn ein Eintrag größer als 1 ist, so sind die beiden beteiligten Knoten durch mehr als eine Kante verbunden, also liegt eine Mehrfachkante und damit ein Multigraph vor.

    3. Man summiert die Einträge in der entsprechenden Zeile oder Spalte. „Schlingeneinträge“ in der Diagonalen werden dabei doppelt gezählt , weil sie die Ordnung um 2 erhöhen.

    4. siehe Nr. 2, die Nachbarschaftsstruktur muss gleich sein, die äußere Form nicht.

1 Statt „Bezeichnung“ verwendet man den englischen Begriff „label“. Bei einem gelabelten Graph kommt es auf die Bezeichnungsreihenfolge der Knoten an. Graphen sind meist ungelabelt, wenn nur die Struktur interessiert.

 

Übungen

 

Graphen als Tabellen – Lösung: Herunterladen [odt][154 KB]

Graphen als Tabellen – Lösung: Herunterladen [pdf][143 KB]

 

Weiter zu Übungen