isomorph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
[Dateianhang nicht öffentlich]
Der linke und der in der Mitte sind isomorph, es gibt eine bijektive Abbildung die Knoten des einen auf den anderen abbildet.
Der ganz rechte Graph hat auch 8 Knoten, alle Knoten sind vom Grad 3 - wie bei den beiden anderen auch.
In der Lösung steht: Enthält Kreis der Länge 5.
Finde in den beiden anderen Graphen nur Kreise der Länge 4, ist dies bereits ausreiched um zu sagen das der Graph nicht isomorph ist?
Habe keine bijektive Abbildung von diesem zu Graph 1 gefunden, aber die Abzahl Knoten/Kanten sind identisch - sollte es dann nicht so eine geben?
Frohes Fest :)
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
Hallo studentxyz!
> [Dateianhang nicht öffentlich]
>
> Der linke und der in der Mitte sind isomorph, es gibt eine
> bijektive Abbildung die Knoten des einen auf den anderen
> abbildet.
Das stimmt zwar, aber ich hoffe, dass das kein Beweis für die Isomorphie der beiden linken Graphen sein soll.
>
> Der ganz rechte Graph hat auch 8 Knoten, alle Knoten sind
> vom Grad 3 - wie bei den beiden anderen auch.
> In der Lösung steht: Enthält Kreis der Länge 5.
In der Lösung welcher Aufgabe?
>
> Finde in den beiden anderen Graphen nur Kreise der Länge
> 4,
Du kannst nicht beweisen, dass sie ausschließlich Kreise der Länge $4$ enthalten.
> ist dies bereits ausreiched um zu sagen das der Graph
> nicht isomorph ist?
Nein.
> Habe keine bijektive Abbildung von diesem zu Graph 1
> gefunden, aber die Abzahl Knoten/Kanten sind identisch -
> sollte es dann nicht so eine geben?
Nein.
>
>
> Frohes Fest :)
>
Für die beiden linken Graphen kann man einen konkreten Isomorphismus angeben.
Dass diese nicht isomorph zum rechten Graphen sind, erkennt man daran, dass sie, im Gegensatz zum rechten Graphen, keinen Kreis der Länge $5$ (Warum?) enthalten.
Warum reicht das als Beweis für die Nichtexistenz eines Isomorphismus?.
LG mathfunnel
|
|
|
| |
|
> Für die beiden linken Graphen kann man einen konkreten
> Isomorphismus angeben.
> Dass diese nicht isomorph zum rechten Graphen sind,
> erkennt man daran, dass sie, im Gegensatz zum rechten
> Graphen, keinen Kreis der Länge [mm]5[/mm] (Warum?) enthalten.
Weil es keine Kantenfolge der Länge 5 gibt die einen Kreis bilden?
> Warum reicht das als Beweis für die Nichtexistenz eines
> Isomorphismus?.
Das kann ich nicht beantworten, warum ist das so?
Freundlicher Gruß
|
|
|
| |
|
Hallo studentxyz!
>
> > Für die beiden linken Graphen kann man einen konkreten
> > Isomorphismus angeben.
> > Dass diese nicht isomorph zum rechten Graphen sind,
> > erkennt man daran, dass sie, im Gegensatz zum rechten
> > Graphen, keinen Kreis der Länge [mm]5[/mm] (Warum?) enthalten.
>
> Weil es keine Kantenfolge der Länge 5 gibt die einen Kreis
> bilden?
Reicht das als Beweis? Naja, Beweis durch 'scharfes Hinsehen' ist in diesem Fall vielleicht ausreichend. Man kann die Würfelsymmetrie ausnutzen um alle Fälle auf wenige Fälle zu reduzieren.
>
> > Warum reicht das als Beweis für die Nichtexistenz eines
> > Isomorphismus?.
>
> Das kann ich nicht beantworten, warum ist das so?
Bildet ein Isomorphismus einen Kreis der Länge $5$ auf einen Kreis der Länge $5$ ab?
>
> Freundlicher Gruß
>
>
LG mathfunnel
|
|
|
| |
|
> Hallo studentxyz!
>
> >
> > > Für die beiden linken Graphen kann man einen konkreten
> > > Isomorphismus angeben.
> > > Dass diese nicht isomorph zum rechten Graphen sind,
> > > erkennt man daran, dass sie, im Gegensatz zum rechten
> > > Graphen, keinen Kreis der Länge [mm]5[/mm] (Warum?) enthalten.
> >
> > Weil es keine Kantenfolge der Länge 5 gibt die einen Kreis
> > bilden?
>
> Reicht das als Beweis? Naja, Beweis durch 'scharfes
> Hinsehen' ist in diesem Fall vielleicht ausreichend. Man
> kann die Würfelsymmetrie ausnutzen um alle Fälle auf
> wenige Fälle zu reduzieren.
Würfelsymmetrie? Meinst du damit einen Graphen der einen Würfel darstellt?
Sehe hier keinen Würfel und es gibt sicher auch Kreise die man nicht als Würfel darstellen kann oder nicht?
>
> >
> > > Warum reicht das als Beweis für die Nichtexistenz eines
> > > Isomorphismus?.
> >
> > Das kann ich nicht beantworten, warum ist das so?
>
> Bildet ein Isomorphismus einen Kreis der Länge [mm]5[/mm] auf einen
> Kreis der Länge [mm]5[/mm] ab?
Ja, da man die grafische Darstellung anpassen kann das beide Graphen identisch sind.
Also reicht es wenn man in einem der beiden Graphen einen Kreis der Länge n findet welcher im anderen Graphen nicht vorhanden ist um isomorphie zu wiederlegen?
|
|
|
|
