Gra­phen als Ta­bel­len

Ein Graph lässt sich gut mit einer Ta­bel­le be­schrei­ben. Das ist zwar nicht sehr an­schau­lich, bie­tet aber eine Reihe von an­de­ren Vor­tei­len. Dabei gibt es ver­schie­de­ne Mög­lich­kei­ten, wir be­schrän­ken uns auf so­ge­nann­te Nach­bar­schaft­s­ta­bel­len (→ „Ad­ja­zenz­ma­tri­zen“).

In jede Zeile wird ein­ge­tra­gen, durch wie viele Kan­ten die Kno­ten mit­ein­an­der ver­bun­den sind. Man sieht z.B. in der letz­ten Zeile rechts, wie viele Kan­ten vom Kno­ten D aus­ge­hen. Von D zu A eine, zu B null, zu C zwei und zu D selbst eine.

Hin­weis: Eine Schlin­ge wie hier im Kno­ten D wird je nach Sicht­wei­se und An­wen­dung ein­fach oder dop­pelt ge­zählt. Es ist zwar 1 Kante, sie er­höht aber die Ord­nung (An­zahl der zu­sam­men­tref­fen­den Kan­te­nen­den) des Kno­tens um 2.

1. Füllt die Nach­bar­schaft­s­ta­bel­len zu den fol­gen­den Gra­phen aus:

   

   Ver­gleicht Ta­bel­len und Gra­phen. Fällt euch etwas auf?

2. Be­grün­det je­weils, warum die bei­den Gra­phen nicht iso­morph sind:

   

3. 

   Zeich­net zur ab­ge­bil­de­ten Nach­bar­schaft­s­ta­bel­le min­des­tens zwei Gra­phen, die un­ter­schied­lich aus­se­hen, aber iso­morph sind. Tauscht eure Hefte aus und ver­gleicht die Gra­phen.

4. Be­trach­tet rück­bli­ckend Gra­phen und Ta­bel­len auf die­sem Blatt:

   1. Woran er­kennt man in der Ta­bel­le, ob es Schlin­gen gibt?
   2. Woran sieht man, ob es ein ein­fa­cher oder ein Mul­ti­graph ist?
   3. Wie kann man die Ord­nung eines Kno­tens be­rech­nen?
   4. Woran er­kennt man, ob zwei Gra­phen iso­morph sind?

Übun­gen

Gra­phen als Ta­bel­len: Her­un­ter­la­den [odt][129 KB]

Gra­phen als Ta­bel­len: Her­un­ter­la­den [pdf][97 KB]

Wei­ter zu Übun­gen