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