Inmersiones de grafos en superficies tubulares de género finito

Abstract

El matemático alemán Euler (1707-1782) resolvió en 1736 el famoso problema de los puentes de Königsberg. Dicha ciudad estaba divida en cuatro partes, conectadas por siete puentes, al pasar por ella un río (ver Figura 1.1). El problema planteado era el siguiente: empezando a andar en un punto cualquiera de la ciudad ¿es posible volver al punto de partida habiendo cruzado los siente puentes tan solo una vez? La respuesta de Euler fue NO y basó su negativa en el siguiente razonamiento: prescindiendo de la geografía peculiar de la ciudad y su entorno, puede trazarse un esquema de la misma mediante cuatro puntos A, B, C, D (que se correspondan con cada una de las partes de la ciudad) y unir con curvas arbitrarias aquellos puntos conectados en la realidad por los puentes (ver Figura 1.2). El problema inicial es, de hecho, equivalente al problema (basado en la figura adjunta) de si partiendo de uno de los cuatro puntos puede trazarse un itinerario que englobe a todas las curvas una sola vez. Si ello fuese posible el número de líneas por cada punto debería ser par y en cambio todos los puntos tienen un número impar de líneas. Por tanto el problema no tiene solución. Los puentes de Königsberg fueron destruidos durante la segunda guerra mundial, pero la resolución del problema por parte de Euler, fue el principio de una teoría matemática de gran utilidad y brillantes: La Teoría de Grafos. Antes de llegar a la formulación precisa de dicha teoría fueron muchos los científicos que de forma totalmente independiente utilizaron conceptos que a posteriori se han visto unificados con la Teoría de Grafos. Kirchhoff en 1847, manejó esquemas sobre circuitos electrónico; Cayley en 1869 estudió la enumeración de los isómeros del compuesto orgánico CnH2n+2 usando esquemas donde cada punto estaba unido con una o cuatro líneas correspondientes a las valencias de enlace; Jordan, en 1869, estudió estructuras arborescentes de forma abstracta. En 1859, Hamilton ideó el siguiente juego: dado un dodecaedro, si en cada uno de sus 20 vértices se pone el nombre de una ciudad, ¿es posible encontrar un circuito cerrado a través de las aristas del dodecaedro que pase por cada ciudad una sola vez? Dicho juego dio lugar a la teoría de grafos hamiltonianos, de múltiples aplicaciones como para resolver problemas de circulación. En tiempo más recientes surgió el problema de colorear mapas de forma que países con frontera común tuviesen coloración diferente. Lewin introdujo en Psicología esquemas como los anteriores al representar personar por puntos y unir aquellos puntos si las personas representadas tenían relaciones personales. Whlenbeck, Lee y Young. En Física usaron esquemas con puntos y líneas al simbolizar estructuras moleculares y sus interacciones… etc. Lo común en todos los casos es el llegar a simbolizar un problema concreto mediante un esquema gráfico o grafo, formado por puntos y líneas que los unen, y estudiar entonces soluciones al problema inicial planteado mediante reflexiones sobre el esquema gráfico asociado. Como situaciones totalmente dispares pueden dar lugar a los mismos esquemas gráficos, estudiando éstos en general se obtienen soluciones a problemas múltiples. Por supuesto la elaboración de un grafo representa siempre una renuncia a muchas condiciones y características, pues el grafo como tal debe ser un esquema simple. Nótese también que el trazado de un grafo no es un problema de geometría métrica, es decir, la forma de las líneas que unen puntos es cualquiera: interesa visualizar las relaciones, las conexiones, las interacciones,… no hacer una fotografía del trazado. El estudio de este tipo de representaciones, de su existencia y de su clasificación, es lo que se conoce como Teoría de Grafos Topológicos. Este tipo de cuestiones tiene una gran aplicabilidad en campos como la Arquitectura, el diseño de redes de comunicación o el diseño de circuitos integrados, por citar algunos (ver [22] para más detalles). Voy a permitirme hacer un pequeño inciso en su aplicación a la Arquitectura, ya que una convicción personal casi me lo exige que es la siguiente: mi labor en la Universidad es Docente e Investigadora y no me gustan que vayan por separado, sobre todo en un caso como éste que tan claramente pueden ir unidos. En las diferentes etapas de concreción de un proyecto arquitectónico la Teoría de Grafos Topológicos aporta un eslabón clave. Una vez perfiladas las partes o elementos que formarán el proyecto, y antes de proceder al trazado de los primeros croquis predimensionales, es sumamente clarificador trazar el grafo de relaciones entre los elementos prefijados. Por supuesto, diferentes tipos de relaciones: acceso físico (puertas), acceso visual (ventanas, cristal,…), pared común,… etc., llevan a realizar diversos grafos sobre un mismo conjunto de elementos: tantos grafos como tipos de relaciones. Si simbolizamos por puntos los elementos y trazamos como aristas entre estos puntos segmentos que simbolicen la relación acceso a obtenemos un grafo. Si éste pone de manifiesto la existencia de un ciclo eso nos viene a decir que es posible establecer un circuito entre dos elementos cualesquiera (ver Figura 1.3). A un grafo plano de adyacencia pueden corresponder diversos croquis. A cada croquis le corresponde (salvo isomorfismo) un grafo de adyacencia. Un grafo de adyacencias no plano no puede corresponder a una distribución real en planta. Una vez realizado un grafo de adyacencias y un croquis dimensionado, a dicho croquis puede asociarse un grafo evaluado de dimensiones con el siguiente criterio. Se marcan tantos vértices como trozos de paredes horizontales haya, más dos vértices especiales (al principio y al final), escalando todos los vértices de arriba abajo: de cada vértice salen aristas (dirigidas hacia abajo) donde se coloca el dimensionado de las paredes horizontales en cada vértice se sitúa en un círculo el dimensionado vertical que queda entre la pared asociada al vértice y la siguiente por debajo. En el vértice final la dimensión vertical debe ser cero y la arista saliente debe tener la dimensión horizontal total. Nótese que el grafo no es correcto si la suma de valores salientes en cada vértice no es igual a la suma de los valores entrantes. El interés de estos grafos dimensionales es verificar si la repartición de dimensiones interiores es correcta. Otro problema abierto de Teoría de Grafos, cuya motivación ha sido arquitectónica, es el de la disección exacta de un cuadrado en subrectángulos trazando solo líneas horizontales y verticales determinando en cada caso todas las subdivisiones posibles y no isomorfas. Nótese que es problema no es el de encontrar todos los grafos finitos posibles sino aquellos que correspondan a una disección plana pausible. Por ejemplo los grafos K5 y K3,3 no se corresponden con ninguna disección de este tipo. Si n indica el número de rectángulos en que se quiere dividir el cuadrado, para n = 1, 2, 3, 4, 5 y 6 se ha calculado que existen, respectivamente, 1, 1, 2, 7, 22 y 117 formas diferentes de subdivisiones no equivalentes topológicamente. Para n ≥ 7 el problema de la descripción exhaustiva de tales subdivisiones está aún abierto. Este tipo de problemas se relaciona hoy con la creación de algoritmos capaces de resolver la cuenta de todas las posibles soluciones mediante el uso de ordenadores y plotters acoplados. A lo largo de la memoria hablaremos de Superficies Tubulares de Género Finito, con respecto a éstas me gustaría mencionar la aplicación práctica que en las nuevas tendencias en la Arquitectura tienen estas superficies utilizadas como soporte en la construcción de diferentes tipos de cúpulas. Y principalmente hablaremos de inmersiones de grafos infinitos en estas superficies. Cabe preguntarse en este punto, ¿por qué grafos infinitos? Primero porque los grafos infinitos son estructuras matemáticas y por tanto merece la pena su estudio, además existen muchas relaciones entre otras ramas de las matemáticas como Álgebra, Teoría de Grupos, Geometría, Lógica, etc. y la Teoría de Grafos y en estos campos las estructuras infinitas son muy comunes. Segundo, porque un grafo infinito puede ser considerado como un grado finito del cual no se sabe exactamente su tamaño. Por último, pero no por ello menos importante, los grafos infinitos son una sucesión creciente de grafos finitos (lo que en la literatura se conoce como Grafos Universales). Esta memoria está estructurada de la siguiente forma: Comenzamos con una breve introducción sobre la Teoría de Grafos, para seguir con un capítulo dedicado a las nociones y conceptos básicos que necesitaremos para el desarrollo y una mejor comprensión de los contenidos que a lo largo de las dos partes que forman este trabajo vamos a presentar. La primera parte estudia inmersiones de grafos infinitos, numerables y localmente finitos en superficies abiertas de género finito y está compuesta por dos capítulos (3 y 4). En el Capítulo 3 hablaremos y, desde un punto de vista teórico, caracterizaremos los grafos sin un punto de acumulación de vértices en tales superficies, encontrando una lista de subgrafos prohibidos para esta propiedad en el cilindro (problema éste propuesto por Thomassen en su visita a nuestro Departamento en 1994). En el Capítulo 4 centraremos nuestra atención en el caso de superficies abiertas planas sobre las cuales generalizaremos los resultados obtenidos por Ayala, Domínguez, Márquez y Quintero para grafos mosaicos planos, así como otros obtenidos por Thomassen en [58] sobre representaciones planas por segmentos rectilíneos a dichas superficies. En la segunda parte de la memoria, hablaremos de inmersiones de grafos infinitos, numerables, localmente finitos y dinámicos; lo que nos va a permitir no solo encontrar resultados teóricos sino también algorítmicos, debido a la estructura repetitiva que tienen estos grafos. En el Capítulo 5 estudiaremos cuando las inmersiones de estos grafos en el cilindro presentan algún tipo de acumulación de puntos, siguiendo la línea de trabajo abierta por Dana en su Tesis Doctoral. Y por último, concluimos esta parte planteándonos el estudio de ciertas propiedades métricas estrechamente relacionadas con las inmersiones de grafos por segmentos rectilíneos que presentan puntos de acumulación, abriendo una nueva línea de investigación, también propuesta por Thomassen en su visita y donde proponemos interesantes problemas abiertos. Para finalizar este trabajo de investigación, presentamos un Apéndice donde damos un procedimiento para obtener los subgrafos prohibidos que verifican cierta propiedad a partir de los menores prohibidos que verifican la misma y las referencias bibliográficas más significativas consultadas para elaborar esta memoria.