Complejidad de estructuras geométricas y combinatorias

Author

Hernando Martín, M. Carmen

Director

Hurtado, Ferran

Codirector

Noy, Marc

Date of defense

1999-04-30

ISBN

9788469136171

Legal Deposit

B.31911-2008



Department/Institute

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III

Abstract

En la presente memoria, se abordan cuatro problemas, existiendo en todos ellos una gran interacción entre la combinatoria y la geometría. El primer problema que se estudia es la introducción de varias extensiones del concepto de tipo de orden para nubes de puntos. Concretamente, se introducen los tipos de orden circulares y triángulares, en las versiones orientada y no orientada. Se han demostrado resultados combinatorios análogos a resultados bien conocidos sobre tipos de orden ordinarios, introducidos por Goodman y Pollack como es el llamado Teorema de ordenación geométrica. Se ha estudiado también la información geométrica que proporciona cada uno de estos conceptos. El segundo problema estudia el empaquetamiento plano de grafos; esto es, el trazado de grafos, disjuntos en aristas, en el plano. Hemos obtenido varios resultados sobre el empaquetamiento plano de árboles y ciclos. Concretamente, para árboles que no sean estrellas, se ha demostrado que siempre admiten empaquetamiento plano: dos copias de un árbol cualquiera, un árbol cualquiera y un camino, un árbol cualquiera y un ciclo. También se han obtenido resultados sobre empaquetamiento plano de dos o tres ciclos. La principal herramienta que se ha utilizado es la representación de un árbol en un polígono convexo con propiedades muy concretas. En tercer lugar se estudia el grafo T (P) de árboles geométricos de una nube de puntos P, siendo este grafo el que tiene por vértices los árboles generadores sin cortes de P y dos de tales árboles T1, T2 son aduacentes si y sólo s, T2C=t1e+f para ciertas aristas e y f. Se han obtenido propiedades combinatorias de estos grafos, especialmente en el caso particular en que el conjunto de puntos esta en posición convexa. En este caso se ha determinado el centro, radio y grupo de automofismos de estos grafos, y demostrado que son hamiltonianos y de conectividad máxima. Finalmente, también se ha estudiado el grafo Mm de los emparejamientos perfectos sin cortes de una nube de 2m puntos en posición convexa. Entre los resultados obtenidos cabe destacar que se ha demostrado que Mm es bipartito, hamiltoniano sólo si m es par y que el diámetro de Mm es igual a m-1, siendo todos los emparejamientos de excentricidad máxima.

Keywords

árboles goemétricos; flips; grafos geométricos; grafos planos; empaquetamiento de árboes; tipos de órdenes circulares y triángulares; estructuras gemotétricas y combinatorias; emparejamientos perfectos; teoría de grafos; grafos hamiltonianos

Subjects

51 - Mathematics

Documents

01_hernandoMartin_portadaSumari.pdf

242.9Kb

02_hernandoMartin_capitol_1.pdf

918.8Kb

03_hernandoMartin_capitol_2.pdf

1.401Mb

04_hernandoMartin_capitol_3.pdf

1.018Mb

05_hernandoMartin_capitol_4.pdf

3.010Mb

06_hernandoMartin_capitol_5.pdf

1.754Mb

07_hernandoMartin_bibliografia.pdf

386.6Kb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)