Gra­phen als Ta­bel­len – Lö­sung

1. Nach­bar­schaft­s­ta­bel­len und iso­mor­phe Gra­phen

   

   Die Ta­bel­len von a) und b) sind iden­tisch. Die bei­den Gra­phen sind iso­morph. Glei­ches gilt für c) und d). Wenn Gra­phen iden­ti­sche Nach­bar­schaft­s­ta­bel­len be­sit­zen, so sind sie iso­morph. Dazu müs­sen die Kno­ten gleich be­nannt sein wie bei a) und b) bzw. c) und d). Ach­tung, die Um­keh­rung gilt nicht! Wenn zwei Gra­phen iso­morph sind, müs­sen sie nicht iden­ti­sche Nach­bar­schaft­s­ta­bel­len be­sit­zen, wie man bei d) und e) sieht. Es kommt auf die Be­zeich­nun­gen¹ der Kno­ten an. Bei e) er­hält man durch „Um­num­me­rie­rung“ der Kno­ten (Ver­tau­schung der Namen von A und D) die glei­che Ta­bel­le wie bei c) oder d).

2. Nicht iso­mor­phe Gra­phen

   1. An­zahl der Kno­ten stimmt nicht über­ein.

   2. An­zahl der Kan­ten stimmt nicht über­ein.

   3. Kno­ten und Kan­ten­an­zahl stimmt über­ein, aber die Ord­nun­gen der Kno­ten nicht.

   4. Kno­ten- und Kan­ten­an­zahl und Ord­nun­gen stim­men zwar über­ein, das Nach­bar­schafts­ge­fü­ge stimmt aber nicht. Es gibt viel­fäl­ti­ge Be­grün­dun­gen:

      Man er­kennt dies z.B. daran, dass die bei­den Kno­ten mit Ord­nung 3 links di­rekt ver­bun­den sind, rechts aber nicht. Oder man be­trach­tet das Ge­fü­ge der Kno­ten mit Ord­nung 2. Links sind zwei Kno­ten der Ord­nung 2 Nach­barn (di­rekt durch eine Kante ver­bun­den), rechts nicht. Oder man er­kennt, dass links ein Ha­mil­ton­kreis exis­tiert, rechts aber nicht.

3. Gra­phen zu Ta­bel­le zeich­nen

   

   Rechts sind 4 mög­li­che iso­mor­phe Gra­phen zu sehen, si­cher sehen eure aber ganz an­ders aus, oder?

4. Re­fle­xi­on

5. 1. Eine Schlin­ge er­kennt man an einer 1 in der Dia­go­na­len von links oben nach rechts unten.

   2. Wenn ein Ein­trag grö­ßer als 1 ist, so sind die bei­den be­tei­lig­ten Kno­ten durch mehr als eine Kante ver­bun­den, also liegt eine Mehr­fach­kan­te und damit ein Mul­ti­graph vor.

   3. Man sum­miert die Ein­trä­ge in der ent­spre­chen­den Zeile oder Spal­te. „Schlin­gen­ein­trä­ge“ in der Dia­go­na­len wer­den dabei dop­pelt ge­zählt , weil sie die Ord­nung um 2 er­hö­hen.

   4. siehe Nr. 2, die Nach­bar­schafts­struk­tur muss gleich sein, die äu­ße­re Form nicht.

¹ Statt „Be­zeich­nung“ ver­wen­det man den eng­li­schen Be­griff „label“. Bei einem ge­la­bel­ten Graph kommt es auf die Be­zeich­nungs­rei­hen­fol­ge der Kno­ten an. Gra­phen sind meist un­ge­la­belt, wenn nur die Struk­tur in­ter­es­siert.

Übun­gen

Gra­phen als Ta­bel­len – Lö­sung: Her­un­ter­la­den [odt][154 KB]

Gra­phen als Ta­bel­len – Lö­sung: Her­un­ter­la­den [pdf][143 KB]

Wei­ter zu Übun­gen