$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

We wtorek, 22 lutego 2005 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Mariusz WOŹNIAK

(Instytut Matematyczny PAN oraz WMS)

wygłosi referat pod tytułem:

O cięciu drzew na żywo

Problem dowolnego podziału drzew można przedstawić następująco (por. referat MW z 28 XI 2003):

Przypuśćmy, że mamy drzewo $T$ rzędu $n$. Usuwając z niego $p-1$ krawędzi otrzymamy $p$ drzew. Pytanie: czy mając $p$ liczb $n_1$, $n_2$ ,..., $n_p$, takich, że ich suma wynosi $n$, możemy tak usunąć krawędzie w $T$ aby dostać $p$ drzew mających odpowiednio $n_1$, $n_2$ etc. wierzchołków?

Jeśli jest to możliwe dla dowolnego ciągu liczb naturalnych, których suma wynosi $n$, to drzewo $T$ nazywamy dowolnie podzielnym (DP).

Referat poświęcony jest wersji na żywo (,on-line") powyższego problemu:

Ciąg $n_i$ poznajemy wyraz po wyrazie, a drzewo mające oodpowiednią liczbę wierzchołków musimy określić od razu, bez możliwości pó14niejszej korekty.

Okazuje się, że (w odróżnieniu od przypadku ogólnego) można w pełni scharakteryzować rodzinę drzew DP na żywo.

Serdecznie zapraszamy wszystkich chętnych!