Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Triangulation. Anzahl notwendiger Diagonalen.
Thema eröffnet 2020-09-29 22:10 von Wario
Druckversion
Druckversion
Seite 2   [1 2]   2 Seiten
Autor
Kein bestimmter Bereich J Triangulation. Anzahl notwendiger Diagonalen.
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, eingetragen 2020-10-03 21:32

\(\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}}\)
Na ja, fast. Für $d(n)$ darfst du natürlich noch nicht $n-3$ einsetzen.
Also so:
$$ d(n) = d(k) + d(n-k+2) + 1 = k-3 + n-k+2-3+1 = n-3,$$ womit der Induktionsschluss erledigt ist.


Jetzt zu einem Beweis ohne Induktion:
Betrachte eine beliebige Triangulierung eines konvexen $n$-Ecks. Diese bestehe aus $D$ Dreiecken und $d$ Diagonalen.
Da jede Diagonale ein weiteres Stück abtrennt, gilt $D=d+1$.

Wir leiten jetzt noch eine weitere Gleichung her, indem wir auf zwei verschiedene Weisen zählen, wie viele verschiedene Dreiecksseiten in der Triangulierung vorkommen:
- Einerseits ist jede Dreiecksseite entweder eine der $n$ Seiten des $n$-Ecks oder eine der Diagonalen der Triangulierung. Daher gibt es insgesamt $n+d$ Dreiecksseiten.
- Fällt dir noch eine zweite Methode ein, die Dreieckseiten zu zählen? Tipp: Jedes Dreieck hat drei Seiten, aber manche Dreiecke teilen sich eine Seite.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2020
Mitteilungen: 123
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, vom Themenstarter, eingetragen 2020-10-03 23:42

\(\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 21:32 - Nuramon in Beitrag No. 40 schreibt:
Jetzt zu einem Beweis ohne Induktion:
Betrachte eine beliebige Triangulierung eines konvexen $n$-Ecks. Diese bestehe aus $D$ Dreiecken und $d$ Diagonalen.
Da jede Diagonale ein weiteres Stück abtrennt, gilt $D=d+1$.

Wir leiten jetzt noch eine weitere Gleichung her, indem wir auf zwei verschiedene Weisen zählen, wie viele verschiedene Dreiecksseiten in der Triangulierung vorkommen:
- Einerseits ist jede Dreiecksseite entweder eine der $n$ Seiten des $n$-Ecks oder eine der Diagonalen der Triangulierung. Daher gibt es insgesamt $n+d$ Dreiecksseiten.
- Fällt dir noch eine zweite Methode ein, die Dreieckseiten zu zählen? Tipp: Jedes Dreieck hat drei Seiten, aber manche Dreiecke teilen sich eine Seite.

Also ich habe rausgefunden, dass 2D+1=n+d gilt (mit D=d+1 folgt das Gesuchte), kann es aber gerade noch nicht gut begründen.


\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, eingetragen 2020-10-03 23:52

\(\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}}\)
Eine Erklärung für den $2D+1$ Term habe ich nicht (kann aber durchaus sein, dass es eine gibt), ist aber auch nicht der Term, auf den ich hinauswollte.

Ganz naiv könnte man ja erstmal sagen, dass jedes Dreieck $3$ Seiten hat, es also $3D$ Dreiecksseiten gibt. Dabei hat man aber manche Seiten mehrfach gezählt, die man folglich wieder abziehen muss. Welche Dreiecksseiten werden mehrfach gezählt?
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2020
Mitteilungen: 123
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, vom Themenstarter, eingetragen 2020-10-05 23:16

\(\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 23:52 - Nuramon in Beitrag No. 42 schreibt:
Eine Erklärung für den $2D+1$ Term habe ich nicht (kann aber durchaus sein, dass es eine gibt), ist aber auch nicht der Term, auf den ich hinauswollte.

Ganz naiv könnte man ja erstmal sagen, dass jedes Dreieck $3$ Seiten hat, es also $3D$ Dreiecksseiten gibt. Dabei hat man aber manche Seiten mehrfach gezählt, die man folglich wieder abziehen muss. Welche Dreiecksseiten werden mehrfach gezählt?

Ich weiß nicht, wie man das gut begründen kann: man müsste von 3D Dreiecksseiten D-1 Seiten abziehen, um auf 3D-(D-1) = 2D+1 = n+d zu kommen.

Welche andere Gleichung meintest Du?
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, eingetragen 2020-10-05 23:52


Dein Versuch Gleichungen zu erraten passt irgendwie nicht zu deinem Anliegen einen Beweis zu finden, für den man nicht von vorn herein wissen muss, welche Formel am Ende rauskommt.

Mach dir mal eine Skizze mit einer Triangulierung. Dann markiere darin alle Dreiecksseiten, die zu mehr als einem Dreieck gehören.



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


2020-10-05 23:52 - Nuramon in Beitrag No. 44 schreibt:
Mach dir mal eine Skizze mit einer Triangulierung. Dann markiere darin alle Dreiecksseiten, die zu mehr als einem Dreieck gehören.

Das sind d Dreiecksseiten, die Anzahl der Diagonalen. Und das sagt mir jetzt was?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, eingetragen 2020-10-08 21: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}}\)
Fassen wir mal zusammen:
- Es gibt $D$ Dreiecke.
- Jedes Dreieck hat drei Seiten.
- Jede Dreiecksseite ist Seite von genau einem oder genau zwei Dreiecken.
- Die Dreieckseiten, die zu zwei Dreiecken gehören, sind genau die Diagonalen der Triangulierung. Davon gibt es genau $d$ Stück.

Ausgehend von diesen Fakten, wie viele Dreiecksseiten gibt es insgesamt?
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2020
Mitteilungen: 123
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.47, vom Themenstarter, eingetragen 2020-10-08 21:40


· Die Gesamtzahl aller Seiten ist n+d
· D Dreiecke bilden 3D Seiten. Davon gehören d Seiten zu zwei Dreiecken.

Also ist 3D - d = n+d  und da D=d+1 wird
3d + 3 - d = n + d bzw. d = n-3.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.48, eingetragen 2020-10-08 22:01


👍



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

\(\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-08 22:01 - Nuramon in Beitrag No. 48 schreibt:
👍

Wunderbar, dann würde ich es zusammenfassend so formulieren:


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

Beweis:
Jede Diagonale gehört zu zwei Dreiecken. Eine Diagonale teilt ein konvexes Vieleck in zwei konvexe Vielecke, die eine Diagonale gemein haben. Die Anzahl $D$ der Dreiecke in einer Triangulation ist entsprechend um eins größer als die Anzahl $d$ der benötigten Diagonalen, d.h. $D=d+1$.

Die Gesamtzahl aller auftrenden Seiten ist $n+d$.
$D$ Dreiecke bilden $3D$ Seiten; davon gehören $d$ Seiten zu zwei Dreiecken.

Also ist $3D - d = n+d$  und da $D=d+1$ wird
$3d + 3 - d = n + d$ bzw. $d = n-3$.
Entsprechend wird $D=d+1=n-2$.
________________________


Dann verweise ich noch auf das Thema LinkTriangulation. Aufstellen aller möglichen Punktefolgen
Dort hätte ich einen Ansatz, aber weitere Ideen sind ja immer gut.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario hat die Antworten auf ihre/seine Frage gesehen.
Wario hat selbst das Ok-Häkchen gesetzt.
Seite 2Gehe 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]