Isomorphe Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:41 Mi 27.01.2010 | | Autor: | extasic |
| Aufgabe | a)
Zeigen Sie: Isomorphe Graphen haben die gleiche Anzahl von Knoten und Kanten
b)
Zeichnen Sie alle paarweise nicht-isomorphen Graphen mit 4 Knoten
c)
Zeigen Sie (durch Markieren der Knoten), dass die folgenden Graphen isomorph sind
[Externes Bild http://img189.imageshack.us/img189/1724/out2f.png] |
Hallo!
Mit dieser Aufgabe quäle ich mich nun schon eine ganze Weile herum, leider komme ich einfach nicht weiter bzw. weiß nicht, ob mein Ansatz richtig ist.
Hier meine Ansätze:
a)
Dies ergibt sich meines Erachtens schon aus der Definition. Da isomorphe Graphen über eine Bijektion definiert werden, die alle Elemente in Ziel- und Quellmenge erfasst und jedes Element in der Quellmenge auf genau ein Element abbildet, muss die Anzahl der Knoten und Kanten gleich sein.
Richtig?
b)
Hier habe ich mir einen Ansatz wie bei a) erwähnt überlegt, und alle 4-knotigen Graphen mit unterschiedlicher Kantenzahl gezeichnet. Stimmt das? Habe ich alle erwischt?
[Externes Bild http://img12.imageshack.us/img12/8867/outu.png]
c)
Bei dieser Aufgabe habe ich - nach durchnummerierung aller Knoten - tabellarisch erfasst, welche Knoten mit wie Vielen verbunden sind. Dann habe ich versucht das ganze zu verbinden, allerdings gab es immer Ungereimtheiten. Auch ein kurzfristig gestricktes Prolog-Programm konnte nicht helfen - möglicherweise auf Grund meiner unzureichenden Kenntnisse.
Wie fange ich hier an? Habt ihr einen Tipp?
Vielen Dank im Voraus!!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:51 Do 28.01.2010 | | Autor: | SEcki |
> a)
>
> Dies ergibt sich meines Erachtens schon aus der Definition.
> Da isomorphe Graphen über eine Bijektion definiert werden,
> die alle Elemente in Ziel- und Quellmenge erfasst und jedes
> Element in der Quellmenge auf genau ein Element abbildet,
> muss die Anzahl der Knoten und Kanten gleich sein.
>
> Richtig?
Kommt imemr auf eure Definition an - aber imo goldrichtig. :)
> b)
>
> Hier habe ich mir einen Ansatz wie bei a) erwähnt
> überlegt, und alle 4-knotigen Graphen mit
> unterschiedlicher Kantenzahl gezeichnet. Stimmt das? Habe
> ich alle erwischt?
Ich glaube, dass du alle erwischt hast. Aber wo ist dein Beweis, das dies alle sind? Ich würde nur bis zu 3 Kanten beweisen, und die andere Kantenzahl über Dualisieren lösen (wo vorher Kanten waren, fallen die raus, wo keine waren, kommen welche rein). Bei den Kanten - ich würde da mit der Inzidenzzahl der Knoten arbeiten, also wieviele Kanten an einen Knoten stossen und damit einen Iso konstruieren.
> c)
>
> Bei dieser Aufgabe habe ich - nach durchnummerierung aller
> Knoten - tabellarisch erfasst, welche Knoten mit wie Vielen
> verbunden sind. Dann habe ich versucht das ganze zu
> verbinden, allerdings gab es immer Ungereimtheiten.
Schwer sich das anzuschauen, aber imo sind die isomorph. Aber man kann nicht beliebig die Ecken mit der gleichen Anzahl der Kanten tauschen - nimm pro Ecke zusätzlich eine Liste der NAchbarecken mit der Kantenzhal - du wirst feststellen, die unterscheidet sich bei denen mit 4 Kanten untereinander.
> Auch
> ein kurzfristig gestricktes Prolog-Programm konnte nicht
> helfen - möglicherweise auf Grund meiner unzureichenden
> Kenntnisse.
In Prolog? Das würde mich interessieren, trotzdem.
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:14 Do 28.01.2010 | | Autor: | extasic |
Vielen Dank, das hat mir sehr weitergeholfen!
|
|
|
|
