Grafos periódicosuna 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 ALGORITMICA FINITA, AUNQUE PRACTICAMENTE TODO EL ESFUERZO A LA HORA DE DESARROLLAR UNA ALGORITMICA EN TEORIA DE GRAFOS HA SIDO DEDICADO A GRAFOS FINITOS, MERECE LA PENA ESTUDIAR LOS GRAFOS INFINITOS FUNDAMENTALMENTE POR DOS RAZONES: UNA DE ELLAS PORQUE LOS GRAFOS INFINITOS CONSTITUYEN UNA ESTRUCTURA INCLUIDA DENTRO DE LAS MATEMATICAS Y, POR TANTO, MERECE LA PENA SU ESTUDIO; LA OTRA RAZON 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. SE PARTIRA DE UN GRAFO FINITO Y, A PARTIR DE EL Y MEDIANTE REGLAS ARITMETICAS, DEFINIMOS LOS DEMAS VERTICES Y ARISTAS DEL GRAFO INFINITO. ESTA FAMILIA ESTA CONSTITUIDA POR GRAFOS QUE LLAMAREMOS GRAFOS PERIODICOS. 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 CABRIA CITAR LOS GRAFOS TRATADOS POR B. GRUNBAUM 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 TEORIA DE PROBABILIDADES; LOS DIAGRAMAS DE CAYLEY, ETC. LOS ALGORITMOS BASICOS QUE SE EMPLEAN EN LA RESOLUCION DE MULTITUD DE CUESTIONES EN GRAFOS FINITOS, SON LOS ALGORITMOS DE CONEXION, CONSTRUCCION DE UN ARBOL GENERADOR Y DE PLANARIDAD. COMO EJEMPLO DE LA CONSTRUCCION DE U