Anwendungen von Gruppenwirkungen in der Kombinatorik

 

Mathematik  |  Informatik

 

Felix Qingzhou Xu, 2005 | Killwangen, AG

 

Eine Gruppenwirkung auf einer Menge ist eine Menge von Transformationen auf der Menge, die bestimmte Eigenschaften erfüllt. In dieser Arbeit werden verschiedene Anwendungsmöglichkeiten von Gruppenwirkungen in der Kombinatorik anhand von Beispielen demonstriert. Die wichtigsten Methoden sind der Abzählsatz von Frobenius und der Abzählsatz von Pólya. Diese Methoden erlauben das Zählen der Anzahl Möglichkeiten unter bestimmten Einschränkungen. Die Beispiele umfassen platonische Körper, regelmässige n-Ecke, Graphen, Isomere und weitere kombinatorische Objekte. Das Ziel dieser Arbeit war es, herauszufinden, wann der Einsatz von Gruppenwirkungen in der Kombinatorik möglich und sinnvoll ist. Das Thema wurde gewählt, weil es sowohl inhaltlich interessant als auch angemessen im Rahmen der Maturaarbeit war.

Fragestellung

Gruppenwirkungen können als Methode zur Lösung kombinatorischer Probleme verwendet werden, allerdings ist dies nicht immer möglich und auch nicht immer effizient. In dieser Arbeit sollen folgende Fragen beantwortet werden:
• Wann ist die Anwendung von Gruppenwirkungen in der Kombinatorik möglich?
• Wann ist die Anwendung von Gruppenwirkungen sinnvoll?

Methodik

In dieser Arbeit werden Grundlagen aus der Gruppentheorie eingeführt, die schliesslich zu den wichtigsten Sätzen dieser Arbeit führen. Es handelt sich dabei um den Abzählsatz von Frobenius und den Abzählsatz von Pólya. Der Abzählsatz von Frobenius liefert eine Formel für die Anzahl von Bahnen, die aus der Wirkung einer Gruppe auf eine Menge hervorgeht, und der Abzählsatz von Pólya kann als Verfeinerung des Abzählsatzes von Frobenius gesehen werden. Die Anwendungen dieser Abzählsätze in der Kombinatorik beruhen auf dem Fakt, dass die Anzahl der Bahnen oft eine kombinatorische Bedeutung hat. Die Arbeit wurde in LaTeX verfasst und zum Erstellen von Abbildungen wurden GeoGebra und TikZ verwendet.

Ergebnisse

Die Resultate dieser Arbeit sind verschiedene Anwendungsbeispiele von Gruppenwirkungen. Es wurden neun Probleme aufgelistet, die verschiedene Anwendungsmöglichkeiten veranschaulichen. Einige dieser Beispiele basieren auf geometrischen Figuren wie zum Beispiel regelmässigen n-Ecken oder platonischen Körpern, andere beinhalten Graphen, Isomere oder Objekte, bei denen mehrere Gruppen involviert sind. In den Beispielen geht es häufig um die Anzahl wesentlich unterschiedlicher Möglichkeiten, Figuren zu färben oder zu konstruieren, sowie um die Anzahl nicht-isomorpher Objekte.

Diskussion

Die Anwendung von Gruppenwirkungen ist generell möglich, wenn eine für das Problem relevante Gruppe existiert. Bei geometrischen Figuren wie den platonischen Körpern oder regelmässigen n-Ecken ist dies oft der Fall. Meistens ist jedoch nicht sofort ersichtlich, ob eine solche Gruppe existiert.
Die Methode der Gruppenwirkungen ist effizient, solange die Gruppe gut beschreibbar ist. Besonders bei Problemen mit kleinen Gruppen macht ihre Anwendung Sinn. Ist die Anzahl der Möglichkeiten sehr klein, so kann die Brute-Force-Methode effizienter sein, allerdings ist die Methode der Gruppenwirkungen verlässlicher, da sie auf einem bewiesenen Theorem basiert.

Schlussfolgerungen

Zusammenfassend lässt sich sagen, dass Gruppenwirkungen eine sehr effiziente Methode sind, sofern sie angewendet werden können. Ob diese Methode eingesetzt werden kann, hängt jedoch stark von der Existenz einer relevanten Gruppe ab, und diese Existenz ist nicht immer offensichtlich. Es ist gerade die Kunst, bei einem gegebenen kombinatorischen Problem zu erkennen, ob eine Gruppenwirkung vorliegt und wenn ja, um welche Gruppe es sich handelt.
Diese Arbeit ist in sich abgeschlossen. Mögliche Erweiterungen bestünden darin, weitere Anwendungen zu behandeln oder weitere Ergebnisse, wie das Resultat von De Brujin, zu behandeln.

 

 

Würdigung durch den Experten

Prof. Dr. Norbert Hungerbühler

Felix Xu verwendet die Abzähltheorie von Pólya, um neun kreative Varianten von kombinatorischen Problemen zu lösen: Färbeprobleme, wobei der Gruppe oder den Färbungen Nebenbedingungen auferlegt werden, Anzahlbestimmungen in Graphenklassen und Anwendungen in der Chemie beim Abzählen von Isomeren. Besonders interessant ist ein Beispiel, bei dem zwei Gruppenwirkungen gleichzeitig im Spiel sind. Die Kunst dabei besteht darin zu erkennen, ob eine Gruppenwirkung vorliegt und wenn ja, um welche Gruppe es sich handelt. Es ist zudem technisch anspruchsvoll, den jeweiligen Zyklenzeiger zu berechnen.

Prädikat:

hervorragend

Sonderpreis «Stockholm International Youth Science Seminar (SIYSS)» gestiftet von der Metrohm Stiftung

 

 

 

Kantonsschule Wettingen
Lehrer: Markus Kriener