Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Enumeration of tanglegrams
Thesis (MSc)--Stellenbosch University, 2018.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2018
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613818700431360 |
|---|---|
| access_status_str | Open Access |
| author | Ravelomanana, Jean Bernoulli |
| author2 | Ralaivaosaona, Dimbinaina |
| author_browse | Ralaivaosaona, Dimbinaina Ravelomanana, Jean Bernoulli |
| author_facet | Ralaivaosaona, Dimbinaina Ravelomanana, Jean Bernoulli |
| author_sort | Ravelomanana, Jean Bernoulli |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2018. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/103653 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:42:11.774Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2018 |
| publishDateRange | 2018 |
| publishDateSort | 2018 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/103653 Enumeration of tanglegrams Ravelomanana, Jean Bernoulli Ralaivaosaona, Dimbinaina Wagner, Stephan Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Generating function UCTD Tanglegrams (Mathematics) Triangulation (Mathematics) Binary trees Matching leaves (Mathematics) Tangled chain (Mathematics) Thesis (MSc)--Stellenbosch University, 2018. 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. 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. 2018-02-22T16:50:12Z 2018-04-09T07:05:04Z 2018-02-22T16:50:12Z 2018-04-09T07:05:04Z 2018-03 Thesis http://hdl.handle.net/10019.1/103653 en_ZA Stellenbosch University ix, 72 pages : illustrations (some colour) application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Generating function UCTD Tanglegrams (Mathematics) Triangulation (Mathematics) Binary trees Matching leaves (Mathematics) Tangled chain (Mathematics) Ravelomanana, Jean Bernoulli Enumeration of tanglegrams |
| title | Enumeration of tanglegrams |
| title_full | Enumeration of tanglegrams |
| title_fullStr | Enumeration of tanglegrams |
| title_full_unstemmed | Enumeration of tanglegrams |
| title_short | Enumeration of tanglegrams |
| title_sort | enumeration of tanglegrams |
| topic | Generating function UCTD Tanglegrams (Mathematics) Triangulation (Mathematics) Binary trees Matching leaves (Mathematics) Tangled chain (Mathematics) |
| url | http://hdl.handle.net/10019.1/103653 |
| work_keys_str_mv | AT ravelomananajeanbernoulli enumerationoftanglegrams |