Bachelorarbeit, 2016
30 Seiten, Note: 1.3
1 Einleitung
1.1 Wichtige Begriffe für das Verständnis des Lemmas
1.1.1 Grundbegriffe aus der Graphentheorie
2 Lemma von Sperner für
2.1 Beweis des Lemmas für
3 Lemma von Sperner für höhere Dimensionen
3.1 Konvexe Menge und konvexe Hülle
3.2 Simplex
3.3 Lemma von Sperner
3.4. Beweis des Lemmas
4 Der Brouwersche Fixpunktsatz
4.1 Beweis des Fixpunktsatzes von Brouwer
5 Das Kuchenproblem
5.1 Grundlegende Definitionen
5.2 Neidfrei-gerecht vs. Proportional-gerecht
5.3 Das Moving Knife – Verfahren
5.4 Neidfrei-gerechte Verteilung mithilfe des Lemmas von Sperner
5.4.1 Beispiel für
5.4.2 Aufteilung auf – Spieler
6 Resümee und Ausblick
Literaturverzeichnis
Im Rahmen des Seminars „Differentialtopologie“ bei Prof. Dr. Abbondandolo habe ich mich entschlossen eine Bachelorarbeit in diesem Themenfeld zu schreiben. Diese Arbeit basiert auf den Hilfssatz von Sperner, der sich als ein fundamentales Hilfsmittel erwiesen hat. Viele mathematische Lehrsätze wurden durch dieses Lemma kombinatorisch elegant bewiesen, wie zum Beispiel der Brouwersche Fixpunktsatz, der in dieser Arbeit auch vorgeführt wird.
Den Kern dieser Arbeit bilden zwei verschiedene Beweise, die mit Hilfe des Lemmas von Sperner erfolgreich bewiesen worden sind. Zum einen den Brouwerschen Fixpunktsatz und zum anderen ein alltägliches Problem.
Letzteres handelt von einem „Kuchenproblem“ (cake division problem), welches in Kapitel 6 genauer erläutert und mit Hilfe des Lemmas gelöst werden kann.
Im folgenden Kapitel befassen wir uns zunächst mit Sperners Lemma für , da für diese Dimension der Hilfssatz bildlich sehr gut darzustellen ist. Wenn wir das Prinzip des Lemmas verstanden haben, ist es relativ einfach, dieses Lemma auf höhere Dimension zusammenzufassen und dann auch zu beweisen. Bevor wir es für Dimension zwei formulieren können, benötigen wir einige mathematische Begriffe aus der Graphentheorie, die in diesem Kapitel kurz und knapp verfasst werden (Siehe auch [1, Kapitel 2.1]).
Definition 1.1. Ein Graph ist ein Tupel , wobei eine (endliche) nichtleere Menge von Knoten ist. Die Menge E ist eine Teilmenge der zweielementigen Teilmengen von , also
Abbildung in dieser Leseprobe nicht enthalten
Die Elemente der Menge bezeichnet man als Kanten.
Definition 1.2. Der Grad (engl. degree) von bezeichnet die Anzahl der Knoten von .
Somit gilt auch folgendes Lemma:
Lemma 1.3. Für jeden Graph gilt
Abbildung in dieser Leseprobe nicht enthalten
Beweis. Wir verwenden die Regel des doppelten Abzählens. Auf der linken Seite wird jede Kante genau zweimal gezählt. Einmal, wenn betrachtet wird und zum zweiten Mal, wenn wir bei angekommen sind. Auf der rechten Seite wird jede Kante ebenfalls zweimal gezählt.
Das folgende Lemma aus der Graphentheorie wird für das Lemma von Sperner ebenso hilfreich sein:
Lemma 1.4. Für jeden Graph gilt: Die Anzahl der Knoten mit ungeraden Grad ist gerade.
Beweis. Aus Lemma 1.3 folgt, dass die Summe der Grade aller Knoten eine gerade Zahl ist. Da aber die Summe der geraden Graden gerade sein muss, lässt sich nun folgern, dass auch die Summe der ungeraden Grade gerade ist. Die Summe von ungeraden Zahlen ist genau dann gerade, wenn ihre Anzahl gerade ist. Somit muss die Anzahl von Knoten ungeraden Grades gerade sein.
Definition 1.5. Ein Pfad entsteht aus Knoten und Kanten, die aufeinander folgende Knoten miteinander verbinden.
Definition 1.6. (Triangulierung). Gegeben sei ein Dreieck . Eine Triangulierung von ist eine Unterteilung auf kleinere Dreiecke, sodass keine Ecke eines Dreiecks auf einer eines anderen Dreiecks liegt (siehe Abb. 1).
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Triangulierung eines Dreiecks
Eine Triangulierung ist also ein Dreieck, das noch einmal in mehreren Dreiecken unterteilt wird.
Lemma 2.1 (Lemma von Sperner für ) . Gegeben sei ein Dreieck und eine Triangulierung von . Außerdem sei jede Ecke der Triangulierung mit einer „Farbe“ aus der Menge markiert, sodass jeweils die Farbe erhält und für die Ecken entlang der Kante von nach nur die Farben oder benutzt werden dürfen, wobei wir im Inneren keine Einschränkungen machen, was wiederum bedeutet: Die Inneren Ecken können beliebig mit oder gefärbt werden.
Dann gilt:
Es gibt ein Dreieck der Triangulierung von , dessen Ecken alle drei Markierungen besitzen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2: Bildliche Darstellung des Lemmas für
In Abbildung 2 enthalten die grau markierten Dreiecke die drei verschiedenen Farben. , und entsprechen hier 1,2 und 3 (siehe auch [2]).
Wir beweisen außerdem eine stärkere Aussage, die besagt, dass die Anzahl der Dreiecke mit den drei unterschiedlich gefärbten Kanten nicht nur ungleich Null ist, sondern immer ungerade ist.
Für den folgenden Beweis orientieren wir uns an [2].
Beweis. Sei
Abbildung in dieser Leseprobe nicht enthalten
Zwei Dreiecke sind durch eine Kante verbunden, falls sie eine gemeinsame Seite besitzen, deren Ecken die Farben 1 und 2 haben. K ist durch eine Kante mit allen Dreiecken verbunden, die eine Seite auf dem Rand von T haben, deren Ecken die Farben 1 und 2 haben (diese Seiten liegen auf der Seite zwischen ). Wir erhalten dann einen Graph, der Grad 1 hat in allen Dreiecken, die 3 verschiedene Farben enthalten, Grad 2 in den Dreiecken, die die Farben 1 und 2 enthalten und Grad 0, wenn das Dreieck nicht beide Farben 1 und 2 besitzt. Daraus kann man schließen, dass nur in den Dreiecken, die die drei verschiedenen Farben enthalten, der Grad ungerade ist (Grad 1).
Nun schauen wir uns die Seiten von T mit den Ecken an (siehe Abb. 3). Entlang dieser Seite existiert eine ungerade Zahl von Wechseln zwischen den beiden Farben 1 und 2. Dies bedeutet wiederum, dass der Grad von K ungerade ist. Da die Anzahl der Knoten mit ungeradem Grad gerade ist (siehe Lemma 1.4 auf S.3) und der Grad von K ungerade ist, haben ungerade viele Dreiecke der Triangulierung einen ungeraden Grad. Wie schon bemerkt sind diese Dreiecke genau die, deren Ecken verschiedene Farben besitzen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 3: bildliche Darstellung des Beweis
In der Abbildung 3 bilden die gestrichelten Linien den definierten Graph.
Bevor wir nun das Lemma von Sperner für höhere Dimensionen aufstellen können, brauchen wir wieder einige Definitionen aus der Geometrie. Das Kapitel ist angelehnt an [3].
Definition 3.1. (konvexe Menge). Eine Teilmenge heißt konvexe Menge, wenn zwei beliebige Punkte eine Verbindungsstrecke bilden, die in dieser Menge liegt (siehe Abb. 4).
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4: Bildliche Darstellung einer konvexen und nicht konvexen Menge
Bemerkung 3.2. Die konvexe Menge enthält somit keine Einbuchtungen.
Definition 3.3. Sei eine Teilmenge eines Vektorraumes V über . Die konvexe Hülle ist gegeben durch die Menge
Abbildung in dieser Leseprobe nicht enthalten
Die konvexe Hülle ist die kleinste konvexe Menge die enthält.
Definition 3.4 ( – Simplex ). Sei und 𝑉 ein Vektorraum über . Es seien gegeben, sodass die Menge linear unabhängig ist. Dann heißt die Menge
Abbildung in dieser Leseprobe nicht enthalten
– Simplex oder Simplex und heißen Ecken .
Bemerkung 3.5. Jedes – Simplex besitzt Ecken.
Satz 3.6. Ein ist konvex, abgeschlossen und beschränkt.
Beweis. Die Konvexität und Beschränktheit folgt unmittelbar aus der Definition des Simplexes. Wir zeigen also nun kurz und knapp die Abgeschlossenheit, indem wir eine Folge benutzen. Dann ist
Abbildung in dieser Leseprobe nicht enthalten
wobei hier das k als ein weiteres Index zu verstehen ist. Des Weiteren ist
Abbildung in dieser Leseprobe nicht enthalten
Da S beschränkt ist, existiert eine konvergente Teilfolge nach dem Satz von Bolzano-Weierstraß , so dass
Abbildung in dieser Leseprobe nicht enthalten
Also gilt
Abbildung in dieser Leseprobe nicht enthalten
Mit
Abbildung in dieser Leseprobe nicht enthalten
S ist somit abgeschlossen.
Wenn wir die ersten drei Simplexe betrachten, erhalten wir folgende geometrische Darstellungen: Ein – Simplex stellt einen Punkt dar (dieser Simplex enthält nur eine Ecke, die dem Punkt in der geometrischen Darstellung entspricht). Ein – Simplex entspricht einer Strecke, die insgesamt zwei Ecken besitzt. Ein Dreieck bildet das – Simplex und ein – Simplex bildet ein Tetraeder. Wenn wir die Simplexe allgemein betrachten wollen, können wir das – Simplex als ein – dimensionales „Tetraeder“ bezeichnen, wobei es sich hier um die konvexe Hülle aus endlich vielen affin unabhängigen Punkten im handelt, die den Ecken des Simplex‘ entsprechen.
Bemerkung 3.7. Eine – Seite (auch 𝑘 – Facette genannt) eines – Simplex ist das – Simplex, welches durch die konvexe Hülle irgendeiner Teilmenge der Ecken gebildet wird. Die nulldimensionalen Seiten entsprechen den Eckpunkten, die – Seiten sind die Kanten und die – Seiten bezeichnet man als Seitenflächen.
Definition 3.8 . Eine endliche Folge
Abbildung in dieser Leseprobe nicht enthalten
von Simplexen heißt Triangulierung von S , falls
Abbildung in dieser Leseprobe nicht enthalten
und falls der Durchschnitt für , entweder leer ist oder eine gemeinsame – Seite mit Dimension bildet.
Nun sei eine Triangulation von gegeben. Im Folgenden werden die Ecken von mit den Labels beschriftet. Hierbei beachten wir folgende Regeln:
1) Die Ecken von S werden paarweise verschieden beschriftet
2) Die Ecken an den Seiten von S erhalten nur die Labels ihrer Ecken,
3) Die inneren Ecken können beliebig nach den Labels der Seiten beschriftet werden.
Somit können wir eine weitere Definition aufstellen:
Definition 3.9. Eine Beschriftung der Triangulierung eines Simplex‘ heißt dann Sperner-Beschriftung, falls die oben benannten Regeln eingehalten werden.
Diese Definition der Sperner – Beschriftung ist eine Generalisierung der aus
Kapitel 2 behandelten Definition für .
In den folgenden Abbildungen betrachten wir zwei Beispiele der 1- Sperner – Beschriftung und der 3 – Sperner –Beschriftung.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5: Triangulierte Linie, die eine 1 – Sperner – Beschriftung darstellt
Abbildung in dieser Leseprobe nicht enthalten
Nicht abgebildet: Seiten mit der Nummer 3 sind im unteren Bereich, Seiten mit der Nummer 2 sind im hinteren Bereich
Abbildung 6: Trianguliertes Tetraeder, das eine 3 – Sperner – Beschriftung darstellt.
Definition 3.10. Ein elementares Simplex als Triangulierung bezeichnet man als voll beschrieben, wenn alle Ecken verschieden gefärbt oder nummeriert sind.
Nun ist es möglich Sperners Lemma für höhere Dimensionen aufzustellen:
Lemma 3.11 (Lemma von Sperner). Jede Triangulierung eines – Simplex‘ mit einer Sperner - Beschriftung besitzt eine ungerade Zahl an voll beschriebenen elementaren – Simplexe. Insbesondere existiert immer mindestens eins solcher Simplexe.
Es existieren viele Wege dieses Lemma zu beweisen. Im Folgenden werden wir eine Induktion über durchführen.
Beweis. Man wähle eine Induktion über .
Induktionsanfang : Für handelt es sich um eine triangulierte Linie, die eine darstellt (wie in Abbildung 5 auf S.10 zu sehen). Die Anzahl der voll beschriebenen Simplexe ist ungerade.
Induktionsannahme: Die Anzahl der voll beschriebenen elementaren Simplexe sind immer ungerade.
[...]
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Kommentare