15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 3 - Diskrete Mathematik, Algorithmen
Donnerstag, 20. September 2001, 14.00, Hörsaal 23

 

Grenzverteilungen von Mustern in Bäumen

Thomas Klausner, TU Wien (Koautor: Michael Drmota)

 

Unter einem Muster in einem Baum $T$ verstehen wir das Auftreten eines vorgegebenen Baumes $M$ als Unterbaum von $T$ (wobei mit Ausnahme der Endknoten von $M$ die entsprechenden Knotengrade von $M$ und $T$ gleich groß sein müssen). Beispielsweise entspricht ein Knoten von $T$ vom Grad $k$ ($\ge 3$) dem Muster eines sternförmigen Baumes $M$ mit $k$ Endknoten.

Es wird gezeigt, daß die Anzahl der Muster (bei einem beliebigen, aber festen $M$) in markierten Bäumen der Größe $n$ (für $n\to\infty$) eine normalverteilte Grenzverteilung besitzt, wobei Erwartungswert und Varianz proportional zu $n$ sind.

E-Mail:

klausner@geometrie.tuwien.ac.at

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden