isomorphie zweier graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Entscheiden Sie jeweils, ob die Graphen isomorph sind.
Sind sie isomorph, geben Sie bitte einen Isomorphismus an. Falls nicht, begründen Sie, warum die Graphen nicht isomorph sind. |
ich habe im ersten schritt erstmal die bedingungen (nicht hinreichend) für isomorphie geprüft, d.h die anzahl der knoten und kanten gezählt, sowie eine adjazenzmatrix aufgetsellt um die knotengrade/valenzen zu prüfen und mir eine gute übersicht zu verschaffen bzw sofort auf den ersten oder zweiten blick eine mögliche isomorphie zu erspähen.
leider ohne erfolg...
alle graphenpaare besitzen eine identische gradfolge.
soweit ich weiß, wurde noch kein effektiver algorithmus um
isomorphie festzustellen gefunden.
nun bleibt mir doch nur noch die möglichkeit, sämtliche permutationen auszuprobieren oder?
hier mal ein bild der angesprochenen graphen (hoffe dies ist hier zulässig):
http://s14.directupload.net/file/d/3132/y7464lwm_png.htm
schon einmal vielen dank im voraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
thread kann bitte geschlossen werden.
habe es selbst rausbekommen.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:45 So 13.01.2013 | | Autor: | Teufel |
Hi!
Einen guten Algorithmus gibt es dafür auch nicht. Aber alle Permutationen musst du in der Regel nicht durchprobieren! Das erste Paar ist ja relativ einfach.
Beim zweiten gibt es nur einen Knoten vom Grad 4 in beiden Graphen. Also muss f(e)=6 sein z.B. wenn f der Insomorphismus werden soll. Links hängen an e noch a und b dran, daher muss dann f(a)=1 und f(b)=3 (oder umgekehrt) gelten, weil rechts 1 und 3 an der 6 hängen. Und so kannst du dich da durchhangeln.
|
|
|
| |
|
hallo teufel, vielen dank für deinen beitrag.
genau auf die von dir genannte art und weise, habe ich versucht, die nicht-isomorphie zu beweisen.
|
|
|
|
