Politopo de Birkhoff acíclico

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.