Enumeration of tanglegrams
| dc.contributor.advisor | Ralaivaosaona, Dimbinaina | en_ZA |
| dc.contributor.advisor | Wagner, Stephan | en_ZA |
| dc.contributor.author | Ravelomanana, Jean Bernoulli | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. | en_ZA |
| dc.date.accessioned | 2018-02-22T16:50:12Z | |
| dc.date.accessioned | 2018-04-09T07:05:04Z | |
| dc.date.available | 2018-02-22T16:50:12Z | |
| dc.date.available | 2018-04-09T07:05:04Z | |
| dc.date.issued | 2018-03 | |
| dc.description | Thesis (MSc)--Stellenbosch University, 2018. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT : Tanglegrams are graphs obtained by taking two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the two trees. Tanglegrams appear in biology in the study of cospeciation or coevolution, and in computer science in the study of software projects and clustering problems. This thesis is concerned with the enumeration of tanglegrams: we first prove an exact formula for the number of non-isomorphic tanglegrams on n leaves and an asymptotic formula for the same quantity as n tends to infinity. Next, we study several parameters of random tanglegrams such as the number of occurrences of subtrees or the distribution of root branches. Finally, our main contribution in this thesis is on the enumeration of planar tanglegrams on n leaves, where a planar tanglegram is a tanglegram that can be drawn in the plane without crossings. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING : Tanglegramme is grafieke wat uit twee binêre wortelbome met dieselfde aantal blare en ’n perfekte matching tussen die blare van die twee bome bestaan. Tanglegramme verskyn in biologie in die studie van kospesiasie en koëvolusie, en in rekenaarwetenskap in die ondersoek van sagtewareprojekte en groeperingsprobleme. Hierdie proefskrif behandel die aftelling van tanglegramme: ons bewys eers ’n formule vir die aantal van nie-isomorfe tanglegramme met n blare en ’n asimptotiese formule vir hierdie aantal as n na oneindig strewe. Verder bestudeer on ’n verskeidenheid van parameters van lukrake tanglegramme soos die aantal voorkoms van deelbome of die verdeling van worteltakke. Laastens is ons hoofbydrag in hierdie proefskrif die aftelling van planêre tanglegramme met n blare, waar ’n planêre tanglegram ’n tanglegram is wat in die vlak sonder kruisings geteken kan word. | af_ZA |
| dc.format.extent | ix, 72 pages : illustrations (some colour) | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/10019.1/103653 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Generating function | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.subject | Tanglegrams (Mathematics) | en_ZA |
| dc.subject | Triangulation (Mathematics) | en_ZA |
| dc.subject | Binary trees | en_ZA |
| dc.subject | Matching leaves (Mathematics) | en_ZA |
| dc.subject | Tangled chain (Mathematics) | en_ZA |
| dc.title | Enumeration of tanglegrams | en_ZA |
| dc.type | Thesis | en_ZA |