Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Gra­phen als Ta­bel­len – Übun­gen – Lö­sung

  1. Nach­bar­schaft­s­ta­bel­len

    Abbildung 1 Lösung zur Übung Graphen als Tabellen

    Abbildung 2 Lösung zur Übung Graphen als Tabellen

    e) Die bei­den Gra­phen b) und c) be­sit­zen iden­ti­sche Nach­bar­schaft­s­ta­bel­len und sind daher iso­morph. Rechts sind Gra­phen zu sehen, die eben­falls wie b) und c) zum „Haus des Ni­ko­laus“ isom­porph sind.

  2. Graph zur Ta­bel­le

    in­di­vi­du­el­le Lö­sun­gen, zwei Bei­spie­le:

    Abbildung 3 Lösung zur Übung Graphen als Tabellen

  3. Nicht iso­mor­phe Gra­phen

    1. Beide Gra­phen ent­hal­ten zwei to­po­lo­gi­sche „Drei­ecke“ mit einer ge­mein­sa­men Kante. Die bei­den Kno­ten der Ord­nung 3 lie­gen sich ge­gen­über.

    2. Man kann z.B. die Kante zwi­schen den bei­den Kno­ten mit Ord­nung 3 als Achse be­trach­ten und einen der „Flü­gel“ um diese Achse um 180° dre­hen.

    3. Da jeder Kno­ten mit jedem an­de­ren durch genau eine Kante ver­bun­den ist, be­schrei­ben beide Gra­phen einen voll­stän­di­gen Gra­phen mit vier Kno­ten, sie sind also iso­morph.

  4. Iso­mor­phe Gra­phen er­ken­nen

    1. Der mitt­le­re Graph ist nicht zu­sam­men­hän­gend, er be­steht aus 2 Teil­gra­phen, einem Drei- und Vier­eck. Der 1. und 3. Graph sind iso­morph, sie bil­den beide einen ge­schlos­se­nen Ring.

    2. Der rech­te Graph hat 13 Kno­ten und einen Kno­ten der Ord­nung 5 (Ma­xi­mal­grad), was beide an­de­ren Gra­phen nicht auf­wei­sen. Dreht man einen der bei­den ers­ten Gra­phen um 180° um einen sei­ner Mit­tel­kno­ten, so er­kennt man die to­po­lo­gi­sche Äqui­va­lenz schnell.

  5. Iso­mor­phie be­grün­den

    Abbildung 4 Lösung zur Übung Graphen als Tabellen

    In jedem der Gra­phen gibt es zwei „Drei­ecke“, bei denen jede Ecke des einen mit genau einer Ecke des an­de­ren Drei­ecks durch eine Kante ver­bun­den ist, wie beim Pris­ma. Sie sind ha­mil­tonsch, aber nicht eu­lersch. Wegen der Iso­mor­phie ge­nügt es dabei, einen der Gra­phen zu un­ter­su­chen.

 

 

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

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

 

Wei­ter zu Logik