Graphentheorie

Neue Frage »

socio Auf diesen Beitrag antworten »
Graphentheorie
Hi alle zusammen!

Aufgabe:
Ein konvexes Polygon mit Ecken soll durch Hinzufügen überschneidungsfreier Diagonalen in Dreiecke zerlegt werden.
Zeigen Sie: Jede solche Zerlegung besteht aus Kanten.

Ansatz:
Eigentlich ist mir klar, dass dies gilt.
Ich kann ja zulässige Zerlegungen erreichen, indem ich mir eine Ecke des Polygons auswähle und mit jeder nicht benachbarten Ecke verbinde.
Da da die Kantenanzahl des Polygons gerade ist und die Anzahl der benachbarten Ecken einer Ecke gerade ist (die n Ecken minus die ausgewählte Ecke und die zwei Nachbarn dieser Ecke), beträgt die Anzahl aller Kanten der Zerlegung: .

Jetzt betrachte ich ja aber nicht alle Arten von zulässigen Zerlegungen. Bei einem Sechseck gibt es ja zB noch andere Zerlegungen.
Dass ich bei diesen einen Schnittpunkt erzeuge, wenn ich einfach mehr als Diagonalen einzeichne, ist mir zwar anschaulich klar, aber ich weiß nicht, wie ich formal korrekt beweisen kann, dass auch für diese Fälle die Anzahl der Kanten ist.

Kann mir da jemand weiterhelfen? smile
HAL 9000 Auf diesen Beitrag antworten »

Ein paar Anregungen:

1) Jede neu eingezeichnete kreuzungsfreie Diagonale erhöht die Anzahl der Polygone der Zerlegung um genau Eins.

2) Kennst du die Winkelsumme im n-Eck ? Durch das Einzeichnen der kreuzungsfreien Diagonalen ändert sich die Gesamtsumme aller Teilpolygonwinkelsummen nicht. Was bedeutet dies, wenn am Ende des Zerlegungsprozesses nur noch Dreiecke als Teilungspolygone übrig bleiben?
socio Auf diesen Beitrag antworten »

Zitat:
1) Jede neu eingezeichnete kreuzungsfreie Diagonale erhöht die Anzahl der Polygone der Zerlegung um genau Eins.


Kann ich nachvollziehen!

Zitat:
2) Kennst du die Winkelsumme im n-Eck ? Durch das Einzeichnen der kreuzungsfreien Diagonalen ändert sich die Gesamtsumme aller Teilpolygonwinkelsummen nicht. Was bedeutet dies, wenn am Ende des Zerlegungsprozesses nur noch Dreiecke als Teilungspolygone übrig bleiben?


Kenne ich leider nicht. Wir haben Winkel überhaupt nicht behandelt.
Mir ist bekannt, dass ein Dreieck eine Winkelsumme von 180° hat, da also nur noch Dreiecke als Teilungspolygone übrig bleiben, müsste die Gesamtsumme aller Teilpolygonwinkelsummen ein Vielfaches von 180° sein.

Ich muss diese Aufgabe auch nicht zwangsweise mit Graphentheorie lösen, es war nur meine erste Intuition.
HAL 9000 Auf diesen Beitrag antworten »

Naja, es muss nicht über die Innenwinkel gehen (ich dachte nur, es wäre einfacher zugänglich), es geht auch mit den Polygon-Seitenzahlen:

2) Während des ganzen Teilungsprozesses ist , wobei die Seitenzahlen der Teilpolygone sind. Man startet dabei mit und endet irgendwann mit (alles Dreiecke).
socio Auf diesen Beitrag antworten »

Okay, ich verstehe was die Formel aussagen soll.
Mir ist aber nicht klar, wie man auf kommt. Wie du schon sagst müsste die Summe am Ende des Teilungsprozess doch den Wert annehmen.

Inwiefern hilft uns die Formel?
Wir zählen ja in der Summe die eingezeichneten Diagonalen immer doppelt, weil sie immer eine Seite von zwei Teilpolygonen sind.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von socio
Mir ist aber nicht klar, wie man auf kommt.

Tja, da muss man einfach mal gründlich drüber nachdenken was bei einem einzigen Teilungsschritt mit den Seitenzahlen passiert, d.h. wenn man ein Polygon durch eine Diagonale in zwei Polynome aufspaltet.
 
 
socio Auf diesen Beitrag antworten »

Okay! Neuer Tag, neue Energie.

Also ich hab nochmal über die Formel nachgedacht und denke ich kann sie nun so erklären:

Wir führen m Teilungen unseres n-Ecks durch. Bei jeder Teilung erhöht sich die Anzahl der Teilpolygone um 1 und die Summe der Seitenanzahlen der Teilpolygone erhöht sich um 2, da die, bei der Teilung hinzugefügte, Diagonale eine Seite von zwei Polygonen ist.
zB.: Wir spalten ein Viereck in zwei Dreiecke auf. Die Diagonale die wir hierbei einzeichnen erhöht die Gesamtseitenanzahl um 2, da sie von beiden Dreiecken eine Seite ist.

Da das n-Eck n Seiten hatte und bei m Teilungen somit 2m Seiten hinzukommen, sehe ich schonmal die .

Da wir bei noch unser Ausgangspolygon (das n-Eck) haben, und noch nicht geteilt haben, müssen wir noch die zwei subtrahieren.

Soweit korrekt?

Liebe Grüße
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »