[Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
	Mathematik-Online-Aufgabensammlung:
	Aufgabe 973: GAP - Graphen

a)

Man bestimme mit Hilfe von GAP bis auf Isomorphie alle (ungerichteten) Graphen mit 6 Knoten. Wieviele Isomorphietypen solcher Graphen gibt es ?   Die Graphen sollen hierbei als Kantenmengen dargestellt werden, wobei die Kanten durch zweielementige Mengen von Knoten repräsentiert werden sollen.

Beispiel : In dieser Darstellung sind die Graphen
[[1,2],[1,6],[2,3],[3,4],[4,5],[5,6]] und
[[1,5],[1,6],[2,4],[2,6],[3,4],[3,5]]
beide isomorph zu einem regelmäßigen Sechseck.

Tip : Man untersuche eine geeignete Gruppenoperation auf der Menge der zu betrachtenden Graphen.

b)

Man schreibe eine GAP - Funktion GraphAutomorphismGroup(Gamma,n), die zu einem gegebenen Graphen die Automorphismengruppe berechnet. Die Automorphismen eines Graphen sind genau diejenigen Permutationen der Knotenmenge, die Kanten auf Kanten abbilden. Die Graphen sollen dabei genauso dargestellt werden wie in Teil a). (Man beachte, daß die Angabe der Kardinalität der Knotenmenge als Funktionsparameter erforderlich ist, da es auch isolierte Knoten geben kann.)

c)

Man untersuche, welche der (bis auf Konjugation in ) 16 transitiven Permutationsgruppen vom Grad 6 als Automorphismengruppen der in Teil a) bestimmten Graphen mit 6 Knoten vorkommen. Wie sehen die zugehörigen Graphen aus ?

siehe auch:

• Stichwort: Gruppe