Matjaž Konvalinka: Število prepletogramov

Datum objave: 31. 5. 2015
Seminar za diskretno matematiko
Torek, 2. 6. 2015, od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek. Prepletogram (angl. tanglegram) je struktura, ki jo dobimo, če izberemo popolno prirejanje listov dveh binarnih dreves s korenom, in se naravno pojavlja v biologiji in računalništvu. Prepletograma sta različna, če ne obstajata simetriji dreves, ki bi en prepletogram preslikali v drugega. Pokazal bom formulo za izračun števila prepletogramov na n listih in njegovo asimptotiko ter algoritem, ki generira naključni prepletogram.