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
Student, Punkte: 2.33K