Properties of greedy trees
Date
2014-12
Authors
Razanajatovo Misanantenaina, Valisoa
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
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.
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.
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.
Description
Thesis (MSc)--Stellenbosch University, 2014.
Keywords
Algorithms, Greedy trees, Majorization (Mathematics), UCTD, Dissertations -- Mathematics, Theses -- Mathematics, Trees (Graph theory)