Automorhismen, Kreise |
05.02.2005, 12:09 | ich weiß nicht weiter | Auf diesen Beitrag antworten » |
Automorhismen, Kreise Aufgabe 1) Wieviele Kreise der Länge r enthält der vollständige Graph K_n? Aufgabe 2) Bestimmen Sie die Automorphismengruppen des folgenden Graphen: Dargestellt ist ein C_5 Graph (= Ein Graph mit 5 Kanten und Knoten und keinen Überschneidungen). Falls ihr so einen Graphen nicht kennt, kann ich gerne nochmal ein Bild malen oder sowas. Kann mir da vielleich tjemand helfen? |
||
06.02.2005, 16:30 | quarague | Auf diesen Beitrag antworten » |
1) vollständig heisst, das jeder Knoten mit jedem anderen verbunden ist? dann geht das ungefähr so: für einen Kreis der Länge 3 wähle ich 3 beliebige verschiedene Knoten aus, wobie die Reihenfolge egal ist. also n(n-1)(n-2)/6 Möglichkeiten für Länge größer 3 so ähnlich aber man muss noch überlegen, ob ersten ein Knoten mehrmals besucht werden darf (def Kreis ?) und zweitens wie viele Möglichkeiten für verschiedene Kreise es in einem Graphen mit genau r Knoten gibt. Das ist wieder sowas kombinatorisches 2) wenn dein Graph einfach ein Fünfeck ist, müsste Z/5Z + Z/2Z herauskommen. Man benennt die Knoten von 1 bis 5, dann müssen benachbarte Knoten wieder auf benachbarte abgebildet werden, dabei kann man entweder die Orientierung beibehalten oder nicht, und es gibt 5 Möglichkeiten wohin die 1 abgebildet wird. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |