DSpace
 
  Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Teses de doutoramento >
 Politopo de Birkhoff acíclico
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/8510

title: Politopo de Birkhoff acíclico
authors: Costa, Liliana Manuela Gaspar Cerveira da
advisors: Martins, Enide Cascais Silva Andrade
keywords: Matemática
Algoritmos
Árvores (Teoria de grafos)
issue 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 q􀀀faces 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 q􀀀faces 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 collectionsUA - Teses de doutoramento
MAT - Teses de doutoramento

files in this item

file description sizeformat
5932.pdf674.2 kBAdobe PDFview/open
statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2