Bäume... < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:38 Sa 29.04.2006 | | Autor: | Bastiane |
Hallo zusammen!
Bin ja mal gespannt, wer mir hier drauf antwortet... 
Ich formuliere die Aufgabe mal etwas einfacher, da es sonst zu kompliziert wird. ![[totlach]](/images/smileys/totlach.gif "[totlach]") Also im Prinzip habe ich einen Baum bei dem jeder Knoten maximal Grad 3 hat. Nun möchte ich zeigen, dass es immer eine Kante in diesem Baum gibt, der den Baum in zwei Teilbäume teilt (also wenn ich die Kante entfernen würde), so dass jeder Teilbaum mindestens [mm] \bruch{n}{3}-1 [/mm] (wie bekomme ich denn die obere Gaußklammer hin?) Knoten besitzt.
Wenn der Baum vollständig ist, dann ist das ja ziemlich einfach. Denn dann habe ich ja unter jedem Knoten wieder einen vollständigen Teilbaum hängen, und wenn ich eine der Kanten direkt unter der Wurzel entferne, dann habe ich ja quasi ein Drittel des Baumes abgetrennt, und die Teilbäume erfüllen genau die Bedingung.
Wenn ich nun einen entarteten Baum habe, der jeweils nur Grad 1 hat (das zählt doch dann trotzdem noch zu Grad 3, oder müsste dafür mindestens ein Knoten Grad 3 haben?), dann habe ich bei Höhe h ja genau h+1 Knoten. Da kann ich den "Baum" ja dann einfach in der Mitte oder bei einer ungeraden Anzahl kurz daneben teilen und ich habe in jedem Teilbaum ungefähr die Hälfte der Knoten stehen, also auf jeden Fall auch noch genug.
Aber wie mache ich das jetzt für allgemeine Bäume vom Grad 3? Ich finde irgendwie keine "Systematik", wie ich diese ganzen Bäume berücksichtigen kann. Ich dachte, man könnte den Baum immer direkt unter der Wurzel abtrennen, und dafür habe ich versucht, mir mal alle möglichen Bäume der Tiefe 2 aufzuzeichnen. Wenn die Wurzel nur Grad 1 oder zwei hat, klappt das noch, aber sobald die Wurzel Grad 3 hat wird das Ganze unübersichtlich und ich weiß nicht, ob ich alle Möglichkeiten abgedeckt habe.
Zudem ist mir dann noch ein Beispiel eingefallen, bei dem es nicht mehr funktioniert, wenn ich den Baum direkt unter der Wurzel teile.
Hat jemand einen Vorschlag, wie man an so etwas systematisch rangeht?
Viele Grüße und schönes Wochenende noch
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
Hallo und guten Morgen Bastiane,
sicherlich geht es in dieser Aufgabe um ungerichtete Bäume, oder ?
Du möchtest zeigen: Sei T ein solcher mit Maximalgrad [mm] \leq [/mm] 3, dann gibt es eine Zerlegung von T in zwei knotendisj. Teilbäume, so dass
(n=Knotenzahl von T) jeder von ihnen mindestens [mm] \lceil \frac{n}{3}\rceil [/mm] -1 Knoten hat, richtig ?
Für kleine n, so zB n=2 und n=3 sollte das zu Fuß gehen.
Ansonsten probieren wir doch mal:
Starten wir an einem Blatt, setzen wir T' gleich dieses Blatt.
T' ist unser aktueller Teilbaum, das Blatt ist unser aktueller Knoten v', und die Kante von dem Blatt aus (es gibt nur eine, wir nehmen hierzu n>1 an) sei unsere aktuelle
Kante e'. Falls nun e' noch nicht das gewünschte leistet, so gilt sicherlich (wir erhöhen im verfahren stets die Knotenzahl von T')
Im Verfahren soll der andere Teilbaum solange mindestens [mm] \lceil n\slash 3\rceil [/mm] -1 Knoten haben, bis wir fertig sind.
|T'| := Anz. Knoten von T' < [mm] \lceil \frac{n}{3}\rceil [/mm] -1
Dann setzen wir v' := das andere Ende von e'. Frage ist nun, wie wir e' wählen.
Im Fall, daß das neue v' Grad 2 hat, setzen wir e' gleich die andere zum neuen v' inzidente Kante, und nach Annahme und Konstruktion
[mm] |T'_{alt}|\leq \lceil \frac{n}{3}\rceil-1, [/mm] also
[mm] |T'_{neu}|\leq \lceil \frac{n}{3}\rceil
[/mm]
und somit hat der andere Teilbaum mindestens [mm] n-\lceil n\slash 3\rceil\: \geq \lceil n\slash 3\rceil [/mm] -1 Knoten (n gross genug !!!).
Der andere Fall ist der, dass der andere zu e' inzidente Knoten - also v'_{neu} - zwei weitere inzidente Kanten hat.
Seien [mm] T_1, T_2 [/mm] die beiden ''an diesen Kanten hängenden'' Teilbäume. Dann gilt
|T'_{alt}| + 1 + [mm] |T_1|+|T_2| [/mm] =n
[mm] |T'_{alt}|+1\leq \lceil n\slash 3\rceil|
[/mm]
und daraus folgern wir, dass mindestens einer der beiden Bäume [mm] T_1, T_2 [/mm] noch mindestens [mm] \lceil n\slash 3\rceil [/mm] -1 Knoten hat.
Für diesen entscheiden wir uns dann.
Klar soweit ?
Es gibt sicher für die Existenz einer solchen Kante noch elegantere Beweise - ich schau mal, ob mir noch was einfällt.
Herzlichst,
Mathias
(Und ? Löst sich bei Dir nun die Spannung ? )
> Hallo zusammen!
>
> Bin ja mal gespannt, wer mir hier drauf antwortet...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:48 Di 02.05.2006 | | Autor: | Bastiane |
Lieber Mathias!
> sicherlich geht es in dieser Aufgabe um ungerichtete Bäume,
> oder ?
Scheint so. Das heißt dann, dass die Bäume quasi gar kein "oben" und "unten" haben, ne? Und ich habe mir immer so schöne Bäume aufgemalt, wo oben die Wurzel ist und jeder Knoten maximal drei Söhne hat. Mmh - das war wohl total der falsche Ansatz. ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]") *tststs*
> Du möchtest zeigen: Sei T ein solcher mit Maximalgrad [mm]\leq[/mm]
> 3, dann gibt es eine Zerlegung von T in zwei knotendisj.
> Teilbäume, so dass
> (n=Knotenzahl von T) jeder von ihnen mindestens [mm]\lceil \frac{n}{3}\rceil[/mm]
> -1 Knoten hat, richtig ?
Also, wenn du's genau wissen möchtest, ich möchte zeigen, dass in jeder Triangulation eines einfachen Polygons mit n Ecken eine Diagonale existiert, so dass auf jeder Seite mindestens [mm] \lceil\bruch{n}{3}-1\rceil [/mm] Dreiecke liegen. Hilft dir das?
(Gilt eigentlich [mm] \lceil\bruch{n}{3}-1\rceil=\lceil \frac{n}{3}\rceil-1 [/mm] ?)
> Für kleine n, so zB n=2 und n=3 sollte das zu Fuß gehen.
Ich glaube, das ist gar nicht nötig, wenn ich mich nicht verrechnet habe, dann gilt alles, was du geschrieben hast, auch für n=2 und n=3...
> Ansonsten probieren wir doch mal:
>
> Starten wir an einem Blatt, setzen wir T' gleich dieses
> Blatt.
>
> T' ist unser aktueller Teilbaum, das Blatt ist unser
> aktueller Knoten v', und die Kante von dem Blatt aus (es
> gibt nur eine, wir nehmen hierzu n>1 an) sei unsere
> aktuelle
> Kante e'. Falls nun e' noch nicht das gewünschte leistet,
> so gilt sicherlich (wir erhöhen im verfahren stets die
> Knotenzahl von T')
>
> Im Verfahren soll der andere Teilbaum solange mindestens
> [mm]\lceil n\slash 3\rceil[/mm] -1 Knoten haben, bis wir fertig
> sind.
>
> |T'| := Anz. Knoten von T' < [mm]\lceil \frac{n}{3}\rceil[/mm] -1
>
> Dann setzen wir v' := das andere Ende von e'. Frage ist
> nun, wie wir e' wählen.
>
> Im Fall, daß das neue v' Grad 2 hat, setzen wir e' gleich
> die andere zum neuen v' inzidente Kante, und nach Annahme
> und Konstruktion
>
> [mm]|T'_{alt}|\leq \lceil \frac{n}{3}\rceil-1,[/mm] also
>
> [mm]|T'_{neu}|\leq \lceil \frac{n}{3}\rceil[/mm]
>
> und somit hat der andere Teilbaum mindestens [mm]n-\lceil n\slash 3\rceil\: \geq \lceil n\slash 3\rceil[/mm]
> -1 Knoten (n gross genug !!!).
Wie groß soll denn deiner Meinung nach n sein? Für n=1 steht doch dann da: [mm] $1-1\ge [/mm] 1-1$ und für n=2: [mm] $2-1\ge [/mm] 1-1$, und für n=3: [mm] $3-1\ge [/mm] 1-1$ - das gilt doch alles. Und für größere n gilt es doch erst recht, oder nicht?
> Der andere Fall ist der, dass der andere zu e' inzidente
> Knoten - also v'_{neu} - zwei weitere inzidente Kanten
> hat.
>
> Seien [mm]T_1, T_2[/mm] die beiden ''an diesen Kanten hängenden''
> Teilbäume. Dann gilt
>
> |T'_{alt}| + 1 + [mm]|T_1|+|T_2|[/mm] =n
>
> [mm]|T'_{alt}|+1\leq \lceil n\slash 3\rceil|[/mm]
>
> und daraus folgern wir, dass mindestens einer der beiden
> Bäume [mm]T_1, T_2[/mm] noch mindestens [mm]\lceil n\slash 3\rceil[/mm] -1
> Knoten hat.
>
> Für diesen entscheiden wir uns dann.
Müssen wir uns nicht genau für den anderen entscheiden? Denn wenn wir den größeren nehmen und ihn zu [mm] T_{alt}' [/mm] hinzufügen, so hat der Restbaum doch u. U. nicht mehr mindestens [mm] \lceil n\slash 3\rceil [/mm] -1 Knoten.
> Klar soweit ?
Ich denke schon.  Und das mache ich jetzt solange weiter, bis mein T' mindestens [mm] \lceil n\slash 3\rceil-1 [/mm] Knoten hat!? Wenn der "neue" Knoten Grad 2 hat, kann ich einfach "das andere Ende der Kante" als Knoten zu T' hinzufügen, ansonsten nehme ich den kleineren Teilbaum!? Reicht das dann, wenn ich das so schreibe oder muss ich das noch weiter ausführen? Eigentlich ist es doch dann immer nur noch das, oder? Aber wo genau ist denn gezeigt, dass nicht der "Restbaum", wenn ich einen Knoten vom Grad 3 habe und einen der beiden Teilbäume zu T' hinzufüge, auf einmal zu wenige Knoten habe? Gilt da immer das Gleiche, wie du oben für einmal diese Situation geschrieben hast? (Oje, ist doch schon zu spät, solche Sätze zu formulieren und über so etwas nachzudenken...)
> Es gibt sicher für die Existenz einer solchen Kante noch
> elegantere Beweise - ich schau mal, ob mir noch was
> einfällt.
Macht nichts - der Ansatz, dass ich vielleicht mal bei den Blättern anfange und nicht bei der (eigentlich gar nicht vorhandenen) Wurzel, hätte für's erste schon genügt. Aber falls du ein gutes Buch zur Hand hast - der Beweis müsste unter "Cutting-Theorem, Chazelle, 1982" zu finden sein.
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:13 Mi 03.05.2006 | | Autor: | mathiash |
Moin Bastiane,
den kleineren natürlich, hast ja recht !!!
Es gilt in der Tat [mm] \lceil \frac{n}{3}-1\rceil =\lceil \frac{n}{3}\rceil-1.
[/mm]
Allgemein gilt für [mm] a\in \IQ [/mm] (oder [mm] \IR) [/mm] und [mm] b\in\IZ [/mm] immer [mm] \lceil a+b\rceil =\lceil a\rceil [/mm] +b,
das gilt aber i.a. nicht mehr, falls [mm] a,b\in\IR\setminus\IZ.
[/mm]
Zu dem, was Du eigentlich zeigen möchtest:
Du kannst Doch sicher zeigen: Wenn Du eine Diagonale hast und eine Seite noch zu klein ist, dann muss es
ein Dreieck auf der anderen Seite geben, das mindestens eine Kante (also eine Dreiecksseite) auf der Diagonalen hat.
(Es können also nicht alle solchen Dreiecke nur einen Punkt mit der Diagonalen gemeinsam haben).
Ein solches Dreieck kannst Du dann auf die noch zu kleine Seite schaufeln (durch Umleiten der Diagonalen entlang der beiden anderen
Dreiecksseiten), und das sollt es doch für Dein Problem auch schon tun, gell ?
Wenn Du wach wirst, kannst Du ja mal drüber nachdenken.
Herzlichst,
Mathias
|
|
|
|
