Properties of greedy trees
| dc.contributor.advisor | Wagner, Stephan | en_ZA |
| dc.contributor.author | Razanajatovo Misanantenaina, Valisoa | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Department of Mathematical Sciences. | en_ZA |
| dc.date.accessioned | 2015-01-13T11:48:19Z | |
| dc.date.available | 2015-01-13T11:48:19Z | |
| dc.date.issued | 2014-12 | en_ZA |
| dc.description | Thesis (MSc)--Stellenbosch University, 2014. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simple greedy algorithm that assigns the highest degree to the root, the second, the third, . . . , -highest degree to the root’s neighbours, etc. This particular tree is the solution to numerous extremal problems among all trees with given degree sequence. In this thesis, we collect results for some distancebased graph invariants, the number of subtrees and the spectral radius in which greedy trees play a major role. We show that greedy trees are extremal for the aforementioned graph invariants by means of two different approaches, one using level greedy trees and majorization, while the other one is somewhat more direct. Finally, we prove some new results on greedy trees for additive parameters with specific toll functions. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING: ’n Gulsige boom word vanuit ’n gegewe graadry deur middel van ’n eenvoudige gulsige algoritme gebou, wat die hoogste graad aan die wortel toewys, die tweede-, derde-, . . . , -hoogste graad aan die wortel se bure, ens. Hierdie spesifieke boom is die oplossing van ’n groot aantal ekstremale probleme onder al die bome met gegewe graadry. In hierdie tesis beskou ons ’n versameling van resultate oor afstand-gebaseerde grafiekinvariante, die aantal subbome en die spektraalstraal waarin gulsige bome ’n belangrike rol speel. Ons bewys dat gulsige bome ekstremaal vir die bogenoemde grafiekinvariante is deur van twee verskillende tegnieke gebruik te maak: een met behulp van vlak-gulsige bome en majorering, en ’n ander metode wat effens meer direk is. Laastens bewys ons sommige nuwe resultate oor gulsige bome vir additiewe parameters met spesifieke tolfunksies. | af_ZA |
| dc.identifier.uri | http://hdl.handle.net/10019.1/95909 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Algorithms | en_ZA |
| dc.subject | Greedy trees | en_ZA |
| dc.subject | Majorization (Mathematics) | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.subject | Dissertations -- Mathematics | en_ZA |
| dc.subject | Theses -- Mathematics | en_ZA |
| dc.subject | Trees (Graph theory) | en_ZA |
| dc.title | Properties of greedy trees | en_ZA |
| dc.type | Thesis | en_ZA |