Grafos periódicos: Una familia de grafos infinitos que admiten una algorítmica constructiva

Abstract

El objetivo de esta Tesis es definir una familia de grafos infinitos en la cual es posible construir una algorítmica finita. Se estudiará los grafos infinitos fundamentalmente por dos razones: una de ellas porque los grafos infinitos constituyen una estructura incluida dentro de las matemáticas y, por tanto, merece la pena su estudio; la otra razón es que, en realidad, conociendo soluciones de problemas que se plantean en grafos finitos, podemos trasladarlos para familias crecientes de grafos finitos (lo que en la literatura se conoce como Grafos Universales). En grafos infinitos, uno de los principales problemas que surgen es la forma de poder definirlos de manera que puedan ser tratados en el ordenador. En esta memoria, este problema es solventado definiendo los grafos de manera recurrente, es decir, definimos un grafo finito y, a partir de él y mediante reglas aritméticas, definimos los demás vértices y aristas del grafo infinito. Esta familia está constituida por grafo que llamaremos grafos periódicos. A pesar de lo restringida que pueda parecer esta familia de grafos, muchos ejemplos de grafos infinitos que surgen en la literatura se pueden incluir dentro de este contexto, como por ejemplo cabe citar los grafos tratados por B. Grünbaum y G.C. Shephard En “Tilings and Patterns”, Freeman, New York. Año 1987, los que surgen al resolver sistemas de ecuaciones en grafos (estudio que se recoge en M. Bauderon, “On System of Equations Defining Infinite Graphs”. C.N.R.S. prc. Mathematiques et Informatique); en teoría de probabilidades; los Diagramas de Cayley son ejemplos de grafos infinitos contenidos en esta familia, etc. Los algoritmos básicos que se emplean en la resolución de multitud de cuestiones en grafos finitos, son los algoritmos de conexión, construcción de un árbol generador y de planaridad. Como ejemplo de la construcción de una algorítmica para grafos periódicos, en este trabajo se construye un algoritmo que responde si el grafo periódico es conexo o no, un algoritmo que construye un árbol generador, y algoritmos que responden al problema de la planaridad de un grafo periódico y a la planaridad sin acumulación de vértices (p-planaridad). Los algoritmos aquí presentados para grafos periódicos, resuelven los problemas en tiempo polinomial. Pocos campos dentro de las matemáticas aparecen tan relacionados como pueden ser la Teoría de Grafos y la Algorítmica. Efectivamente, una parte importante de la Teoría de Grafos requiere o trata de la resolución algorítmica de los problemas que se plantean y, por otra parte, no existe otra vía más natural para introducirse en la algorítmica que la Teoría de Grafos, ya que las estructuras que se presentan en algorítmica permiten, de forma muy sencilla, introducirse en dicha disciplina. Por razones obvias, prácticamente la totalidad del esfuerzo desarrollado por la algorítmica en teoría de grafos queda limitado para el caso en que los grafos son finitos. Sin embargo, los grafos infinitos constituyen una estructura a la que se le ha dedicado relativamente poco estudio y esfuerzo, aunque tal vez merezca la pena dedicarle una mayor atención Fundamentalmente por dos razones: - La primera porque los grafos infinitos constituyen una estructura incluida dentro de las matemáticas y, por tanto, merece la pena su estudio. - Una segunda razón es que, en realidad, conociendo soluciones de problemas que se plantan en grafos finitos, podemos trasladarlos para familias crecientes de grafos finitos (lo que en la literatura se conoce como Grafos Universales). Por otra parte, y posiblemente sorprendente para muchos, últimamente se han desarrollado muchos métodos que permiten trabajar algorítmicamente en estructuras infinitas e incluso, dentro de la teoría de grafos, existen algunos esfuerzos por resolver problemas en grafos infinitos, tanto los que vienen definidos de una forma recursiva o bien generados por grafos finitos. Sin embargo, hay que decir que estos métodos señalados anteriormente es fácil comprobar que es imposible desarrollar una algorítmica similar a las clásicas existentes para grafos finitos (algorítmica que resuelve problemas como conexión de un grafo, planaridad, etc.) si los grafos están definidos de esa forma. Así por ejemplo, si un grafo viene definido de forma recursiva ni tan siquiera es posible desarrollar un algoritmo que responda si una arista dada es arista del grafo. Otra cuestión sería definir el grafo de forma recursivamente enumerable. En este caso es posible conocer, sin más que ir generando una lista, que evidentemente sería parcial, las aristas del grafo. Pero aún en este caso sería imposible desarrollar una algorítmica que, en tiempo finito, responda si el grafo es conexo o no (problema que es fundamental tenerlo resuelto, desde un punto de vista algorítmico en teoría de grafos). Para solventar estos problemas definiremos una familia de grafos infinitos como serán los grafos periódicos. Básicamente, un grafo periódico será la unión de todas las traslaciones, según vectores de Z2, de cierto grafo finito dado. A pesar de lo restringida que pueda parecer esta definición, muchos ejemplos de grafos infinitos que surgen en la literatura se pueden incluir dentro de este contexto, como por ejemplo cabe citar los grafos tratados por B. Grünbaum en “Tilings and Patterns”, los que surgen al resolver sistemas de ecuaciones en grafos, los diagramas de Cayley, etc. Cabe decir que, a lo largo de esta memoria trataremos de desarrollar una algorítmica sobre lo grafos infinitos anteriormente definidos. Para ello, lo que se hará será tratar tres problemas clásicos en la Teoría de Grafos finitos y la Algorítmica como son la conexión, existencia y construcción de un árbol generador, y el problema de la planaridad. Veremos que es posible desarrollar algoritmos que resuelvan, incluso en tiempo polinomial, dichos problemas. La memoria está organizada de la siguiente forma: Un primer capítulo de preliminares que recoge de una forma general las definiciones básicas de Teoría de Grafos y Algorítmica, así como algunos resultados que se utilizarán posteriormente. Anteriormente se ha definido la familia de grafos periódicos generados por un grafo finito como los trasladados en todo el plano de dicho generador. En el siguiente capítulo de este trabajo se resuelve el problema de la conexión para esta familia de grafos. A diferencia del caso finito, que para estudiar la conexión se parte de un vértice y se construye un árbol generador, para el caso de un grafo periódico se comprueba si este pertenece a una serie de ciertas familias definidas previamente, las cuales se intersectan en una subfamilia que definen a los grafos infinitos conexos. Una vez que se ha estudiado y resuelto el problema de la conexión para grafos periódicos, se presenta en este capítulo un algoritmo que, en tiempo O(n9), responde si dicho grafo es conexo o no, siendo n el número de componentes conexas que tiene el grafo finito que genera al periódico. En el caso en que el grafo periódico no es conexo, tenemos suficiente información sobre la cantidad y la forma que tienen sus componentes conexas. Así, dependiendo de las familias a las que pertenece el grafo periódico, éste podrá tener un número infinito de componentes finitas, un número finito de componentes infinitas, un número infinito de ellas, etc. Además, si el grafo finito que genera al periódico tiene n componentes conexas se tiene que, a lo más, existen n componentes en el grafo periódico que, mediante traslaciones de éstas, se obtienen todas las demás. Posteriormente, en el siguiente capítulo, se resuelve el problema de la construcción de un árbol generador (en la literatura spanning tree) para grafos periódicos conexos. Un primer resultado que se tiene es que un grafo periódico conexo siempre contiene ciclos, por lo que la estructura de árbol infinito no podemos definirla como grafo periódico. Por lo tanto, se amplía la definición de la familia de los grafos periódicos a otra familia, formada por lo que se llamarán grafos periódicos generalizados, de forma que un grafo periódico generalizado no será más que una unión finita de grafos periódicos. Se verá que dentro de esta familia podemos encontrar grafos infinitos sin siclos y se demostrará que todo grafo periódico conexo contiene, en la familia ampliada, un subgrafo suyo que es árbol generador. Después de las bases teóricas que demuestran que siempre existe un árbol generador de un grafo periódico conexo, se presenta un algoritmo que, en tiempo O(n4), construye dicho árbol, definiéndolo como un grafo periódico generalizado. En el caso en que el grafo periódico no sea conexo, se tiene que existe un subgrafo de él que contiene generadores de todas las componentes conexas del periódico. Bastará con aplicar dicho algoritmo a cada componente conexa. Por último se estudia el problema de la planaridad y la planaridad sin acumulación de vértices (en la literatua p-planaridad) para grafos periódicos, haciendo distinción en toda la casuística posible según como puedan ser las componentes conexas de dicho grafo periódico. Al igual que en los otros capítulos, se presenta un algoritmo que, en el peor de los casos en tiempo O(m2), con m el número de vértices del grafo finito que genera al periódico, resuelve el problema de la planaridad y el de la planaridad sin acumulación de vértices. Al final de cada capítulo hemos preferido presentar conclusiones y problemas abiertos, pues se ha creído que podría contribuir a fijar el alcance y una posible prolongación de los temas estudiados y de otros temas mencionados. Por último se da una sección dedica a la bibliografía empleada, así como las referencias básicas que se han utilizado para el desarrollo de este trabajo.