Begriff von isomorph bei Graphen, Suche nach klaren Beispiel und Begriffsdefinition

Aufrufe: 38     Aktiv: vor 1 Woche, 1 Tag

0

In einer Lehrbuch wird es wie folgt erklaert :"Ein Isomorphismus gepflanzter Bäume ist ein Isomorphismus
der Wurzelbäume, bei dem zusätzlich die Reihenfolge der direkten Nachfahren berücksichtigt wird.
"
Wie kann man Isomorphie in einem Graphen prüfen? Mir ist klar , dass dafür keine Regeln gibt, aber was gilt allgemein zu betrachten ? Biejektive Abbildung muss vorhanden sien um ein Isomorphismus bei den Grafen zu behaupten, aber dabei mir fällt nichts ein.

 

gefragt vor 1 Woche, 5 Tage
s
studenlang1142,
Student, Punkte: 10
 
Kommentar schreiben Diese Frage melden
1 Antwort
0

allgemein sind graphen genau dann isomorph wenn man sie genau gleich "aufmalen" kann, mit eventueller umbenennung der elemente

trotzdem kann es natürlich oft ziemlich schwer sein, isomorphie zu zeigen - vorallem wenn man keinen vorschlag für einen konkreten isomorphismus hat

wenn ich zwei graphen hätte und auf isomorphie überprüfen sollte, würde ich damit anfangen zu schauen, ob ich ganz offensichtlich beide gleich aufmalen kann oder ob das ganz offensichtlich nicht gehen kann. dann würde ich schauen ob beide graphen die gleiche gradfolge haben, dann ob beide die gleiche färbungszahl haben (kann man ja oft schon anhand K_n's als untergraphen erkennen) und wenn das beides passt, erst dann würde ich versuchen einen isomorphismus zu finden.

klar bei bäumen ist die färbungszahl natürlich immer gleich - dabei würde ich im dritten schritt stattdessen auf ähnlichkeiten beim prüfer code achten falls dir das was sagt

hoffe ich hab die frage richtig verstanden

geantwortet vor 1 Woche, 5 Tage
a
aufjedebewertungeinschnaps
Student, Punkte: 1.07K
 

Ja an meiner Uni sagen die Betreuer auch, man muss schon mehrere Dinge probieren , bevor man einen oder keinen Isomorphismus findet.   -   studenlang1142, vor 1 Woche, 1 Tag
Kommentar schreiben Diese Antwort melden