Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/8510
Title: | Politopo de Birkhoff acíclico |
Author: | Costa, Liliana Manuela Gaspar Cerveira da |
Advisor: | Martins, Enide Cascais Silva Andrade |
Keywords: | Matemática Algoritmos Árvores (Teoria de grafos) |
Defense Date: | 2011 |
Publisher: | Universidade de Aveiro |
Abstract: | Neste trabalho estabelece-se uma interpreta c~ao geom etrica, em termos
da teoria dos grafos, para v ertices, arestas e faces de uma qualquer
dimens~ao do politopo de Birkho ac clico, Tn =
n(T), onde T e uma
arvore com n v ertices. Generaliza-se o resultado obtido por G. Dahl,
[18], para o c alculo do di^ametro do grafo G(
t
n), onde
t
n e o politopo
das matrizes tridiagonais duplamente estoc asticas. Adicionalmente,
para q = 0; 1; 2; 3 s~ao obtidas f ormulas expl citas para a contagem do
n umero de qfaces do politopo de Birkho tridiagonal,
t
n, e e feito
o estudo da natureza geom etrica dessas mesmas faces. S~ao, tamb em,
apresentados algoritmos para efectuar contagens do n umero de faces de
dimens~ao inferior a de uma dada face do politopo de Birkho ac clico. In this work using graph theory, we give a geometrical interpretation of vertices, edges, and faces of any dimension of the acyclic Birkho polytope, Tn = n(T), were T is a tree with n vertices. We generalize a proposition from G. Dahl, [18], that allows the calculation of the diameter of the graph G( t n), where t n denotes the polytope of tridiagonal doubly stochastic matrices. Furthermore, for q = 0; 1; 2; 3 we obtain some explicit formulae for counting the number of qfaces of the tridiagonal Birkho polytope, t n, and the study of its geometrical nature is done. For a given p-face of t n we determine the number of faces of lower dimension that are contained in it and we discuss its nature. Some algorithms allowing an exhaustive account on the number of edges and faces of the acyclic Birkho polytope are presented. |
Description: | Doutoramento em Matemática |
URI: | http://hdl.handle.net/10773/8510 |
Appears in Collections: | UA - Teses de doutoramento DMat - Teses de doutoramento |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.