Matroids Matheplanet Forum Index
Forumbereich moderiert von: matroid
Mathematik » Kombinatorik & Graphentheorie » Triangulation. Anzahl notwendiger Diagonalen.
Druckversion
Druckversion
Seite 1   [1 2]   2 Seiten
Kein bestimmter Bereich J Triangulation. Anzahl notwendiger Diagonalen.
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-09-29

In einem konvexen n-Eck bildet jede Ecke, außer mit sich selbst und außer mit ihren beiden Nachbarecken, mit den anderen Ecken Diagonalen (nichtüberschneidende Geraden); das sind also n-3 Diagonalen.

Die n-3 Diagonalen zu einer Startecke bilden eine Triangulation (vollständige Zerlegung in nichtüberschneidene Dreiecke).

Aber:
Wie kann ich zeigen, dass jede Triangulation genau n-3 Diagonalen beinhalten muss, die nicht notwendigerweise von der selben Startecke ausgehen.


Intuitiv ist es klar, aber muss man ja trotzdem irgendwie begründen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.04.2016, Mitteilungen: 4989, aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-09-29

Induktion ist eine Möglichkeit. Der Induktionsanfang ist n = 3. Im Induktionsschritt verwende irgendeine Diagonale der Triangulierung und wende die Induktionsvoraussetzung auf die beiden "Hälften" an.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, eingetragen 2020-09-29
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Hallo,

jede Diagonale teilt ein konvexes Polygon in zwei konvexe Polygone. Die Anzahl $D$ der Dreiecke in einer Triangulation ist also um eins größer als die Anzahl $d$ der benötigten Diagonalen.

Versuche jetzt noch eine zweite Gleichung (in der $D,d$ und $n$ vorkommen) herzuleiten, indem du auf zwei verschiedene Arten ausdrückst, wie viele Kanten die Dreiecke einer Triangulierung insgesamt haben (beachte, dass sowohl Diagonale als auch Kanten des $n$-Ecks Kanten eines Triangulierungsdreiecks sein können).

[Die Antwort wurde vor Beitrag No.1 begonnen.]
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, vom Themenstarter, eingetragen 2020-09-30
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Induktion hatte ich schon gedacht; meistens ist es eleganter, wenn es anders geht. Daher würde ich eher den anderen Weg verfolgen.

2020-09-29 22:56 - Nuramon in Beitrag No. 2 schreibt:
jede Diagonale teilt ein konvexes Polygon in zwei konvexe Polygone. Die Anzahl $D$ der Dreiecke in einer Triangulation ist also um eins größer als die Anzahl $d$ der benötigten Diagonalen.

Versuche jetzt noch eine zweite Gleichung (in der $D,d$ und $n$ vorkommen) herzuleiten, indem du auf zwei verschiedene Arten ausdrückst, wie viele Kanten die Dreiecke einer Triangulierung insgesamt haben (beachte, dass sowohl Diagonale als auch Kanten des $n$-Ecks Kanten eines Triangulierungsdreiecks sein können).

Ich habe versucht das aufzustellen.

1) Vom n-Eck kann man mit einer Anzahl 1,2,...,d Diagonalen Dreiecke Abschneiden, bis n-d=3 wird.

2) Dann hat man d Dreiecke gebildet sowie das eine verbliebene Dreieck. Damit ist die Anzahl D der Dreiecke insgesamt D = d+1



Aber irgendwie folgt bereits aus 1) direkt das Gesuchte: d = n-3


Sollte doch reichen (?).

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, eingetragen 2020-09-30
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Hallo,

ja, dein Ansatz sollte auch klappen. Deine Argumentation benutzt, dass es in jeder Triangulierung eines $n$-Ecks immer ein Dreieck gibt, bei dem zwei Seiten gleichzeitig Kanten des $n$-Ecks sind. Das müsstest du also noch begründen.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 25.10.2012, Mitteilungen: 2586
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, eingetragen 2020-09-30

2020-09-29 22:10 - Wario im Themenstart schreibt:

Aber:
Wie kann ich zeigen, dass jede Triangulation genau n-3 Diagonalen beinhalten muss, die nicht notwendigerweise von der selben Startecke ausgehen.


ich würde sagen, anstelle "genau" müsste "mindestens" stehen

du könntest zu einem beliebigen, neuen, innenligenden punkt von jeder ecke eine linie ziehen, also n linien, und hättest auch eine vollständige triangulation

haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, vom Themenstarter, eingetragen 2020-09-30
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-09-30 19:41 - Nuramon in Beitrag No. 4 schreibt:
ja, dein Ansatz sollte auch klappen. Deine Argumentation benutzt, dass es in jeder Triangulierung eines $n$-Ecks immer ein Dreieck gibt, bei dem zwei Seiten gleichzeitig Kanten des $n$-Ecks sind. Das müsstest du also noch begründen.

Das leuchtet irgendwie ein. Da das das 'verbliebene Dreieck' betrifft, würde ich es so formulieren.  
_________________
1) Von einem konvexen n-Eck kann man mit einer Anzahl von 1,2,...,d Diagonalen Dreiecke Abschneiden, bis n-d=3 wird.

2) Dann hat man d Dreiecke gebildet sowie das eine verbliebene Dreieck, dessen Kanten sich aus einer Diagonalen und zwei n-Eckskanten zusammensetzen. Damit ist die Anzahl D der Dreiecke insgesamt D = d+1.
_________________

Aber ob das so begründet ist?
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.7, vom Themenstarter, eingetragen 2020-09-30

2020-09-30 19:53 - haribo in Beitrag No. 5 schreibt:
2020-09-29 22:10 - Wario im Themenstart schreibt:
Aber:
Wie kann ich zeigen, dass jede Triangulation genau n-3 Diagonalen beinhalten muss, die nicht notwendigerweise von der selben Startecke ausgehen.

ich würde sagen, anstelle "genau" müsste "mindestens" stehen

du könntest zu einem beliebigen, neuen, innenligenden punkt von jeder ecke eine linie ziehen, also n linien, und hättest auch eine vollständige triangulation

Das ist kein schlechter Einwand, das ist aber m.E. eher ein Problem der Definition der Triangulation.
Um das Problem zu vermeiden würde ich diese so formulieren:
Definition: Unter der Triangulation eines Vielecks versteht man dessen vollständige Zerlegung durch nichtüberschneidende Dreiecke, deren Eckpunkte Ecken des Vielecks sind.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.8, eingetragen 2020-09-30
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Das trifft jetzt nicht ganz das, was ich in No. 4 meinte.

Du sagst, dass

1) Von einem konvexen n-Eck kann man mit einer Anzahl von 1,2,...,d Diagonalen Dreiecke Abschneiden, bis n-d=3 wird.
Aber es schneidet halt nunmal nicht jede Diagonale ein Dreieck ab.
Allgemein teilt eine Diagonale das $n$-Eck nur in zwei konvexe Vielecke. Wenn du in jedem Schritt nur eine beliebige Diagonale betrachtest, dann läuft das ganze auf Triceratops Induktionsargument hinaus.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.9, vom Themenstarter, eingetragen 2020-09-30
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-09-30 20:28 - Nuramon in Beitrag No. 8 schreibt:
Das trifft jetzt nicht ganz das, was ich in No. 4 meinte.

Du sagst, dass

1) Von einem konvexen n-Eck kann man mit einer Anzahl von 1,2,...,d Diagonalen Dreiecke Abschneiden, bis n-d=3 wird.
Aber es schneidet halt nunmal nicht jede Diagonale ein Dreieck ab.
Allgemein teilt eine Diagonale das $n$-Eck nur in zwei konvexe Vielecke. Wenn du in jedem Schritt nur eine beliebige Diagonale betrachtest, dann läuft das ganze auf Triceratops Induktionsargument hinaus.

Oje, stimmt. Ich ging davon aus, dass man die Diagonalen immer so wählen kann (nicht muss, aber eben kann), das ein Dreieck abgeschnitten wird.

Also wenn es so nicht geht, muss ich es mir ggf. komplett neu überlegen.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.10, eingetragen 2020-09-30

Es geht schon. Ich wollte nur darauf hinweisen, dass du es auch begründen musst.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.11, vom Themenstarter, eingetragen 2020-09-30

2020-09-30 20:33 - Nuramon in Beitrag No. 10 schreibt:
Es geht schon. Ich wollte nur darauf hinweisen, dass du es auch begründen musst.

Ok, wie wäre es hiermit?

___________________
1)Von einem konvexen n-Eck kann man mit einer Anzahl von 1,2,...,d Diagonalen Vielecke geringerer Eckenzahl abschneiden, bis n-d=3 wird.

2) Dann hat man d Dreiecke gebildet (da sonst, also bei Teilvielecken mit größerer Eckenzahl, weitere Abschneidungen möglich wären) sowie das eine verbleibende Dreieck, dessen Kanten sich aus einer Diagonalen und zwei n-Eckskanten zusammensetzen.
Damit ist die Anzahl D der Zerlegungsdreiecke insgesamt D = d+1.
___________________



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.12, eingetragen 2020-09-30
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Ich bin mir nicht sicher, ob ich überhaupt richtig verstehe, was du tun willst.

Wozu brauchst du dein 2) eigentlich? Die Gleichung $D=d+1$ war doch nur für meinen Ansatz aus No.2 wichtig.

Kannst du genauer formulieren, was du mit 1) überhaupt meinst?
Ich hatte dich ursprünglich so verstanden, dass du mit einer beliebigen Triangulierung eines konvexen $n$-Ecks startest und behauptest, dass es in dieser immer ein Teildreieck ABC gibt, so dass $A$ und $C$ im $n$-Eck die Nachbarecken von $B$ sind (diesen Teil müsste man noch beweisen!). Die Diagonale $AC$ zerlegt dann die betrachtete Triangulierung des $n$-Ecks in das Dreieck ABC und eine Triangulierung eines $n-1$-Ecks. Diese kleinere Triangulierung hat genau eine Diagonale weniger als die ursprüngliche. Iterativ macht man das jetzt mit der neuen Triangulierung des $n-1$-Ecks so lange weiter, bis am Ende nur noch eine Triangulierung eines Dreiecks übrig bleibt, die natürlich 0 Diagonalen enthält. Das passiert nach $n-3$ Iterationen. Also war die Anzahl der Diagonalen in der Ausgangstriangulierung gleich $n-3$.

Mit deiner neuen Formulierung sehe ich nicht, inwiefern sich dein Ansatz noch von der von Triceratops vorgeschlagenen Induktion unterscheidet. Diese erscheint mir im übrigen einfacher als das iterierte Dreiecke abschneiden.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.13, vom Themenstarter, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Ich möchte einen kurzen Aufsatz zum Thema schreiben, der seinen Schwerpukt nochmal woanders hat. Aber da muss man ja die Grundlagen etwas klären; also im Grunde den

Satz: Bei einer Triangulation eines $n$-Eck ist
· die Anzahl der Diagonalen $n-3=:d$
· die Anzahl der Dreiecke $n-2=d+1=:D$

Wenn dafür
das
1)Von einem konvexen n-Eck kann man mit einer Anzahl von 1,2,...,d Diagonalen Vielecke geringerer Eckenzahl abschneiden, bis n-d=3 wird.

2) Dann hat man d Dreiecke gebildet (da sonst, also bei Teilvielecken mit größerer Eckenzahl, weitere Abschneidungen möglich wären) sowie das eine verbleibende Dreieck, dessen Kanten sich aus einer Diagonalen und zwei n-Eckskanten zusammensetzen.
Damit ist die Anzahl D der Zerlegungsdreiecke insgesamt D = d+1.


ausreicht, wäre mir das recht. Wenn das jetzt eine Art Induktion war, wäre es auch nicht so schlimm.





\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.14, eingetragen 2020-10-01

Also 1) ist einfach kein Beweis, sondern nur eine Umformulierung der zu beweisenden Aussage.

Du kannst es aber zu einem Beweis machen, indem du das Induktionsargument von Triceratops ausführst.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.15, vom Themenstarter, eingetragen 2020-10-01

2020-10-01 01:04 - Nuramon in Beitrag No. 14 schreibt:
Also 1) ist einfach kein Beweis, sondern nur eine Umformulierung der zu beweisenden Aussage.

Du kannst es aber zu einem Beweis machen, indem du das Induktionsargument von Triceratops ausführst.

OK, mein Problem ist gerade, dass ich mir uneins bin, wie ich das am besten elegant aufschreibe / formuliere. Ich würde diesen Vorkapitelsatz gerne möglichst kurz halten.
Für Ideen wäre ich offen.






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 25.10.2012, Mitteilungen: 2586
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.16, eingetragen 2020-10-01

Wie ist die Definition der Innenwinkel eines konvexen n-Ecks ? Muss er < 180 grad betragen oder darf er nur nicht >180 grad sein, also ist 180 grad zulässig oder nicht?

Ich fand diese Definition: Verbindung aller n Punkte müssen komplett innerhalb der Polygonfläche oder auf ihrem Rand liegen.... das würde 180 grad ermöglichen




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.17, eingetragen 2020-10-01

2020-10-01 03:40 - Wario in Beitrag No. 15 schreibt:
OK, mein Problem ist gerade, dass ich mir uneins bin, wie ich das am besten elegant aufschreibe / formuliere. Ich würde diesen Vorkapitelsatz gerne möglichst kurz halten.
Für Ideen wäre ich offen.
Schreib doch erstmal überhaupt einen Beweis auf. Kürzen kannst du ihn später dann immer noch.
Recht viel länger als drei bis fünf Zeilen dürfte der Induktionsbeweis eigentlich eh nicht sein.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.18, vom Themenstarter, eingetragen 2020-10-01

Also ein Iduktionsbeweise sähe für mich so aus:

Bei einer Triangulation eines n-Eck ist die Anzahl der Diagonalen n−3.

I.A.:
3-Eck: 0 Diagonalen, 3-3=0
4-Eck: 1 Diagonale, 4-3=1

I.B.:
n-Eck: n-3 Diagonalen

I.S.:
(n+1)-Eck: Ein (n+1)-Eck entsteht, wenn man eine n-Eck-Kante zu einem Dreieck auftrennt; diese Kante braucht man nun als 1 weitere Diagonale zur Triangulation.
=> (n-3)+1 = (n+1)-3.

Mag so stimmen, aber gefällt mir so inhaltlich irgendwie nicht.





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.19, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Dein Beweis hat immer noch das gleiche Problem: Du musst mit einer beliebigen Triangulierung anfangen und es ist nicht offensichtlich, dass es in dieser immer eine Diagonale gibt, die nur eine einzige Ecke abtrennt.

Betrachte im Induktionsschluss stattdessen eine beliebige Diagonale der Triangulierung. Diese teilt das $n$-Eck in ein $m_1$-Eck und ein $m_2$-Eck, auf die du die Induktionsvoraussetzung anwenden kannst (Stichwort: starke Induktion).
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.20, vom Themenstarter, eingetragen 2020-10-01

2020-10-01 13:59 - Nuramon in Beitrag No. 19 schreibt:
Stichwort: starke Induktion

Ja, das hat man mal dem Namen nach gehört. Induktion ist sicher alles eine korrekte Sache, aber gefällt aus Eleganzgründen eh nicht. Möchte lieber eine andere Beweisart ausarbeiten, insb. wenn das solche Zustände annimmt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.21, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Entschuldige die direkte Formulierung, aber: Woher willst du denn wissen, ob starke Induktion zu einem eleganten Beweis führt, wenn dir nicht klar ist, wie man diese auf dein Problem anwenden kann?

Ich gebe dir als Starthilfe mal die Induktionsannahme:
Für jedes $m<n$ gelte, dass eine beliebige Triangulierung eines konvexen $m$-Ecks genau $m-3$ Diagonalen enthält.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.22, vom Themenstarter, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-10-01 14:37 - Nuramon in Beitrag No. 21 schreibt:
Entschuldige die direkte Formulierung, aber: Woher willst du denn wissen, ob starke Induktion zu einem eleganten Beweis führt, wenn dir nicht klar ist, wie man diese auf dein Problem anwenden kann?

Ich gebe dir als Starthilfe mal die Induktionsannahme:
Für jedes $m<n$ gelte, dass eine beliebige Triangulierung eines konvexen $m$-Ecks genau $m-3$ Diagonalen enthält.

Kann ich nicht wissen, ich bezog das mehr darauf, dass mir dieses Geschreibse "I.A.:... I.B.:... I.S.:..." nicht gefällt bzw. ich das nicht elegant finde. Ein rein subjektiver Eindruck; wie gesagt kein Urteil über die Korrektheit des Verfahrens.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.23, eingetragen 2020-10-01

Ich gebe dir Recht, dass "direkte" (im Sinne von "ohne Induktion") Beweise meistens schöner sind als Induktionsbeweise. Wenn es dir aber wichtiger ist einen "eleganten" Beweis (das ist sowieso subjektiv) als überhaupt einen Beweis zu haben, dann solltest du deine Prioritäten dringend noch einmal überdenken. Insbesondere da dir Induktionsbeweise anscheinend Probleme bereiten, wirst du nicht darum herum kommen diese noch weiter zu üben.

Übrigens habe ich bereits in No.2 skizziert, wie man die Aussage ohne Induktion beweisen kann.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kezer Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 04.10.2013, Mitteilungen: 1040
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.24, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-10-01 14:48 - Wario in Beitrag No. 22 schreibt:
Kann ich nicht wissen, ich bezog das mehr darauf, dass mir dieses Geschreibse "I.A.:... I.B.:... I.S.:..." nicht gefällt bzw. ich das nicht elegant finde.

Wenn man fortgeschrittener ist, schreibt man oft bloß nur z.B. "Für $n = 1$ gilt die Aussage. Nun zu $n > 1$." Für den Leser ist es meistens klar, dass Induktion gemeint ist.

Einführungsaufgaben zur Induktion in der Uni machen oft den Eindruck als ob Induktionsbeweise langweilig und monoton wären, das ist aber im Allgemeinen ganz und gar nicht so.


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.25, vom Themenstarter, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-10-01 14:57 - Nuramon in Beitrag No. 23 schreibt:
Ich gebe dir Recht, dass "direkte" (im Sinne von "ohne Induktion") Beweise meistens schöner sind als Induktionsbeweise. Wenn es dir aber wichtiger ist einen "eleganten" Beweis (das ist sowieso subjektiv) als überhaupt einen Beweis zu haben, dann solltest du deine Prioritäten dringend noch einmal überdenken. Insbesondere da dir Induktionsbeweise anscheinend Probleme bereiten, wirst du nicht darum herum kommen diese noch weiter zu üben.

Übrigens habe ich bereits in No.2 skizziert, wie man die Aussage ohne Induktion beweisen kann.

Schlecht wäre es nicht, aber da ich das mehr aus Spaß an der Sache mache, weniger aus dringender Veranlassung, sehe jetzt keinen wichtigen Grund, mich vertiefend in das Induktionsthema einzuarbeiten, solange ich das vermeiden kann.



Aber ich habe eine weitere Idee, die sehr gut wäre, weil sie direkt einen weiteren interessanten Aspekt beleuchtet:

_____________
Zwichen den Ecken eines konvexen Vielecks gibt insgesamt $
(n-1)+(n-2)+(n-3)+\dots+3+2+1 = \dfrac{n(n-1)}{2}
$ Verbindungsstrecken. Zieht man davon die $n$ Strecken zwischen den benachbarten Eckpunkten (Kanten) ab, führt dies auf eine Gesamtzahl von $
\dfrac{n(n-1)}{2}-n=\dfrac{n(n-3)}{2}
$ aller möglichen Diagonalen.

_____________

Da steckt die Anzahl $n-3$ der für eine Triangulation benötigten Diagonalen drin.
Kann ich kombinatorisch begründen, dass ich $\dfrac{n(n-3)}{2}$ durch $\dfrac{n}{2}$ teilen muss, um eine mögliche Triangulation zu erhalten?


\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.26, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Da $\frac n2$ noch nicht mal zwingend eine ganze Zahl sein muss, kann ich mir nicht wirklich vorstellen, wie das gehen soll.

Hast du eigentlich noch einmal über No.2 nachgedacht?
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.27, vom Themenstarter, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-10-01 23:25 - Nuramon in Beitrag No. 26 schreibt:
1) Da $\frac n2$ noch nicht mal zwingend eine ganze Zahl sein muss, kann ich mir nicht wirklich vorstellen, wie das gehen soll.

2) Hast du eigentlich noch einmal über No.2 nachgedacht?

1) Stimmt. Aber das wäre wirklich elegant, wenn man das aus dieser Betrachtung rausholen könnte; vll. mit einer Fallunterschiedung für gerade / ungerade Eckenzahl. Ich weiß es nicht.

2) Darauf werde ich mich dann wohl jetzt fokussieren müssen.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 15.10.2014, Mitteilungen: 1884
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.28, eingetragen 2020-10-01
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
Insbesondere bei Verwendung starker Induktion kann man die Zeremonie wirklich ziemlich in Grenzen halten. Um $\forall n.\ P(n)$ zu zeigen, sagt man z.B. einfach:
Sei $n$ beliebig. Wir verwenden starke Induktion und haben deswegen außerdem: $\forall m < n.\ P(m)$. [Und jetzt irgendwie $P(n)$ beweisen].

Man kann es also fast so sehen, als würde einfach eine zusätzliche Voraussetzung erscheinen, von der man Gebrauch machen kann, und sonst alles gleich bleiben.

Tatsächlich geht man natürlich vom Ziel $\forall n.\ P(n)$ zum Ziel $\forall n.\ (\forall m < n.\ P(m)) \to P(n)$ über. Letzteres ist aber per starker Induktion hinreichend für ersteres.


(Ein ähnliches Phänomen tritt auf, wenn man klassische Logik verwendet: Wenn man zum Ziel hat, eine Aussage A zu beweisen, kann man jederzeit die Annahme $\lnot A$ hinzunehmen. Dies liegt daran, dass $(\lnot A \to A) \to A$ gilt. Da das vielleicht etwas verwunderlich ist, heißt das Ding auch "Consequentia mirabilis" 😁 )

[Die Antwort wurde nach Beitrag No.25 begonnen.]
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 25.10.2012, Mitteilungen: 2586
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.29, eingetragen 2020-10-02

eigentlich war dein start in #1 gar nicht schlecht, da er immerhin eine geschickte auswahl von zu schneidenden diagonalen aufzeigt welche ohne überschneidungen zu einer vollständige zerlegung in dreiecke, also triangulation mit n-3 schnitten führt

ich würde danach die verallgemeinerung in drei schritten aufzeigen

1.)
-nochmal definieren in welcher reihenfolge man diese triangulation durch schnitte durchführen könnte/müsste dass jeweils immer ein dreieck abgeschnitten/hergestellt wird

2.)
- zeigen dass die reihenfolge der durchführung dieser schnitt für das ergebnis "vollständige triangulation in n-3 schnitten" egel ist, also auch ein schnitt entlang einer beliebigen inneren diagonalen aus dem set der in #1 gewählten diagonalen, der als zwischenschritt zwei konvexe polygone herstellt, kann mit der gleichen gesamtzahl von schnitten, zum gleichen ergebnis führen: vollständige triangulation in n-3 schnitten

3.)
- zeigen das dieser mittlere schnitt nicht nur einer aus der schar der diagonalen, welche du in #1 ausgewählt hast, genommen werden muss sondern jede beliebige(bzw viele) andere diagonale zu zwei neuen, den beiden in schritt 2 aber völlig gleichwertigen, konvexe polygone führt

ergebniss: es ist für die (mindestanzahl an schnitten n-3) völlig egal welche der diagonalen als schnitt aus dem set der möglichkeiten innerhalb der inzwischen zerlegten konvexen polygonen als nächstes gewählt wird

q.e.d.?
haribo

p.s. deiner neudefinition von "triangulation" in #7 möchte ich nicht zustimmen, das ist mir zu beliebig hingebogen, drum bleibe ich bei: n-3 ist die MINDESTanzahl von schnitten



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.30, vom Themenstarter, eingetragen 2020-10-02
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-09-29 22:56 - Nuramon in Beitrag No. 2 schreibt:
jede Diagonale teilt ein konvexes Polygon in zwei konvexe Polygone. Die Anzahl $D$ der Dreiecke in einer Triangulation ist also um eins größer als die Anzahl $d$ der benötigten Diagonalen.

Versuche jetzt noch eine zweite Gleichung (in der $D,d$ und $n$ vorkommen) herzuleiten, indem du auf zwei verschiedene Arten ausdrückst, wie viele Kanten die Dreiecke einer Triangulierung insgesamt haben (beachte, dass sowohl Diagonale als auch Kanten des $n$-Ecks Kanten eines Triangulierungsdreiecks sein können).

Ich vermute, es muss irgendwie so laufen:

Sei d(n) die Anzahl für eine Triangulation benötigter Diagonalen in einem n-Eck.
Wird durch eine Diagonale ein k-Eck abgeschnitten, so verbleibt ein (n-k+2)-Eck.
Damit hat man die Beziehung:  d(n) = d(k) + d(n-k+2) + 1,
wobei der Summand 1 die trennende Diagonale brücksichtigt.

Andererseits weiß man d(3)=0 (oder auch d(4)=1).

________
Und wie löst man das jetzt?
Ansonsten ist es wahrscheinlich doch nicht das Gewünschte, wei die Anzahl D(n) von Dreiecken nicht vorkommt.





\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.31, eingetragen 2020-10-02

Das ist zwar nicht das, was ich vorgeschlagen hatte. Aber trotzdem gut, dass du es so machen willst, denn das ist jetzt fast schon alles, was du für den Beweis mit starker Induktion benötigst.

Du musst noch berücksichtigen, dass du die trennende Diagonale auch mitzählen musst. Dann kannst du die Induktionsannahme einsetzen und bist fertig.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 15.10.2014, Mitteilungen: 1884
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.32, eingetragen 2020-10-02

2020-10-02 21:05 - Wario in Beitrag No. 30 schreibt:
Sei d(n) die Anzahl für eine Triangulation benötigter Diagonalen in einem n-Eck.
Wird durch eine Diagonale ein k-Eck abgeschnitten, so verbleibt ein (n-k+2)-Eck.
Damit hat man die Beziehung:  d(n) = d(k) + d(n-k+2).
Das ist falsch.

Andererseits weiß man d(3)=0 (oder auch d(4)=1).
________
Und wie löst man das jetzt?
Ansonsten ist es wahrscheinlich doch nicht das Gewünschte, wei die Anzahl D(n) von Dreiecken nicht vorkommt.
Setze k=3, dann hast du mit deinen Gleichungen eine durch primitive Rekursion definierte Funktion, der man eine Definition in geschlossener Form ansieht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.33, vom Themenstarter, eingetragen 2020-10-02

2020-10-02 21:29 - Nuramon in Beitrag No. 31 schreibt:
Das ist zwar nicht das, was ich vorgeschlagen hatte. Aber trotzdem gut, dass du es so machen willst, denn das ist jetzt fast schon alles, was du für den Beweis mit starker Induktion benötigst.

Du musst noch berücksichtigen, dass du die trennende Diagonale auch mitzählen musst. Dann kannst du die Induktionsannahme einsetzen und bist fertig.

Achso, dann muss es wohl so lauten:

2020-10-02 21:05 - Wario in Beitrag No. 30 schreibt:
Sei d(n) die Anzahl für eine Triangulation benötigter Diagonalen in einem n-Eck.
Wird durch eine Diagonale ein k-Eck abgeschnitten, so verbleibt ein (n-k+2)-Eck.
Damit hat man die Beziehung:  d(n) = d(k) + d(n-k+2) + 1,
wobei der Summand 1 die trennende Diagonale brücksichtigt.

Andererseits weiß man d(3)=0 (oder auch d(4)=1).


Aber, wie schon wieder das? Ich dachte das ist jetzt eine Rekursion.  Und die muss wiederum durch starke Induktion bewiesen werden? Geht das nicht anders?

[Die Antwort wurde nach Beitrag No.31 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.34, eingetragen 2020-10-02

Kannst du es durch starke Induktion zeigen? Das ist jetzt wirklich nur noch eine einzige Zeile Rechnung. Du musst nur noch die Induktionsvoraussetzung einsetzen.

Über einen Beweis ohne Induktion können wir danach noch reden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.35, vom Themenstarter, eingetragen 2020-10-02

2020-10-02 23:36 - Nuramon in Beitrag No. 34 schreibt:
a) Kannst du es durch starke Induktion zeigen?
b) Das ist jetzt wirklich nur noch eine einzige Zeile Rechnung. Du musst nur noch die Induktionsvoraussetzung einsetzen.

b) Glaube ich sofort, aber

a) nein, momentan nicht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.36, eingetragen 2020-10-02
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Wende die
2020-10-01 14:37 - Nuramon in Beitrag No. 21 schreibt:
Induktionsannahme:
Für jedes $m<n$ gelte, dass eine beliebige Triangulierung eines konvexen $m$-Ecks genau $m-3$ Diagonalen enthält.
auf die Gleichung

d(n) = d(k) + d(n-k+2) + 1
an.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.37, vom Themenstarter, eingetragen 2020-10-03
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-10-02 23:56 - Nuramon in Beitrag No. 36 schreibt:
Wende die
2020-10-01 14:37 - Nuramon in Beitrag No. 21 schreibt:
Induktionsannahme:
Für jedes $m<n$ gelte, dass eine beliebige Triangulierung eines konvexen $m$-Ecks genau $m-3$ Diagonalen enthält.
auf die Gleichung

d(n) = d(k) + d(n-k+2) + 1
an.


n-3 = d(k) + d(n-k+2) + 1;  mit k=3, d.h. d(k)=d(3)=0 wird
n-3 = d(n-1) + 1.  Mit dem Schritt von n auf n+1 wird
n+1-3 = d(n) +1 also d(n) = n-3.


PS: Indukton ist deshalb nicht schön, weil das Ergebnis wissen muss und dann beweist. Es ist immer schöner, wenn man das Ergebnis rausbekommt.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2415
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.38, eingetragen 2020-10-03
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Warum setzt du $k=3$? Das ist die gleiche unbegründete Annahme, die ich jetzt schon mehrfach bemängelt habe.

Die Induktionsannahme kannst du nicht nur auf $n-1$ anwenden, sondern auf jedes $m<n$.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 189
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.39, vom Themenstarter, eingetragen 2020-10-03
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-10-03 12:50 - Nuramon in Beitrag No. 38 schreibt:
Warum setzt du $k=3$? Das ist die gleiche unbegründete Annahme, die ich jetzt schon mehrfach bemängelt habe.

Die Induktionsannahme kannst du nicht nur auf $n-1$ anwenden, sondern auf jedes $m<n$.

Ja was weiß ich. Dann soll ich wahrscheinlich das machen:

d(n) = d(k) + d(n-k+2) + 1

n-3 = k-3 + n-k+2-3+1 = n-3 (wahre Aussage).
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 1Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]