GEOMETRIAS FINITAS

Autor: GARCÍA VÁZQUEZ PEDRO.
Año: 2003.
Universidad: SEVILLA .
Centro de lectura: INFORMÁTICA.
Centro de realización: E.T.S. INGENIERÍA INFORMÁTICA.

Resumen: Uno de los problemas más representativos dentro de la Teoría Extremal de Grafos consiste en el estudio de los valores de la función ex(n;F), es decir, el tamaño máximo de un grafo de orden n sin contener a F como subgrafo. Es en este sentido donde podemos encuadrar los objetivos de esta tesis. Concretamente, abordaremos dos extensiones del modelo. Una de ellas consiste en el estudio de la función ex(n;TKp), que denota el número máximo de artistas de un grafo con n vértices sin contener como subgrafo una subdivisión del grafo completo de orden p. En la otra, mediante la función ex(n;Ks,t) buscaremos maximizar el tamaño de un grafo de orden n sin contener como subgrafo al grafo bipartito Ks,t. Como veremos a lo largo de este trabajo, estamos ante dos problemas extremales para los que se conocen sólo respuestas parciales y que han sido tratados principalmente desde un punto de vista asintótico, esto es, para valores suficientemente grandes de n. De hecho, los resultados han ido encaminados a la búsqueda de cotas para dichas funciones. Nuestro propósito es profundizar en la búsqueda de valores exactos para las funciones ex(n;TKp) y ex(n;Ks,t). Probaremos resultados de estructura que nos llevarán a encontrar acotaciones que conducen a tales valores exactos. Finalmente, y para los casos en que tales valores sean encontrados, caracterizaremos lo que se conoce como familia de grafos extremales y que denotaremos por EX(n;TKp) y EX(n;Ks,t) respectivamente.

Autor: MARTINEZ FERNÁNDEZ LUIS.
Año: 2001.
Universidad: PAIS VASCO.
Centro de lectura: CIENCIAS.
Centro de realización: FACULTAD DE CIENCIAS DE LA UPV-EHU.

Resumen: Se hace un compendio de las aplicaciones del algebra en teoria de diseños y matemática borrosa, así como de las aplicaciones de estas en la técnica y la ingeniería. Se hace también un estudio teórico, basado en la investigación del autor, de algunas estructuras algebráicas borrosas (grupos, anillos, ideales y módulos difusos) y de ciertas estructuras combinatorias (T-diseños, conjuntos de diferencias y sistemas de diferencias). En la primera parte se hace un estudio de los grupos, anillos, ideales y módulos difusos así como de ciertos típos de ideales difusos, los ideales difusos primos y primarios, siendo la principal novedad de este estudio la unión de las teorías ya establecidas de subanillos difusos de anillos no difusos y los ideales difusos de anillos no difusos se da una definición de las estructuras de grupo, anillo y módulo cociente difusos que generaliza las ya conocidas en la literatura, introduciendolas en un contexto más general. En la segunda parte se estudian algunas estructuras combinatorias, en relación principalmente con un método nuevo introducido, el de las asignaciones con valores en un anillo en los puntos de un T-diseño. Se generaliza un resultado de P.cameron relativo a esquemas de asociación y se estudia un nuevo tipo de diseños, los (A,T)-Diseños. También se dan algunos criterios de existencia para conjuntos de diferencias y familias de diferencias, y se construyen algunas nuevas familias infinitas de ambas. Finalmente, se mejora un algoritmo introducido por D.Ashlock para producir diseños combinatorios utilizando algoritmos genéticos, y se aplica para hallar algunas familias de diferencias con dos bloques básicos cuya existencia era hasta ahora un problema abierto.

Autor: FEDRIANI MARTEL EUGENIO MANUEL.
Año: 2000.
Universidad: SEVILLA.
Centro de lectura: MATEMATICAS .
Centro de realización: FACULTAD DE MATEMATICAS.

Resumen: La memoria se enmarca en la "Teoria de Inmersiones de Grafos en Superficies", presentando y resolviendo varios e interesantes problemas sobre dicho tema. Destacan especialmente los resultados referidos al estudio de los grafos peri S tanto en seudosuperficies para las que no se conoce su "teorema de Kuratowski", como en otras en las que se sabe que este no es finito. Se estudian las inmersiones peri sin acumulacion de vertices para el caso de grafos infinitos en superficies tubulares y se dan algoritmos para obtener tanto los menores como los menores topologicos prohibidos para la peri-representabilidad en otras seudosuperficies. Tambien se analizan los grafos no numerables que admiten inmersion en superficies con todos los vertices,en una misma cara.

Autor: CARDENAS ESCUDERO MANUEL ENRIQUE.
Año: 2000.
Universidad: SEVILLA.
Centro de lectura: MATEMATICAS .
Centro de realización: FACULTAD DE MATEMATICAS.

Resumen: En la tesis que se presenta se extienden fundamentalmente algunos resultados y metodologias de mediados de los años 80 y 90 sobre la k-categoria algebraica de categorias aditivas al estudio de la k-categoria algebraica de las categorias exactas. En el tercer capitulo se mejoran algunos resultados ya conocidos de categorias exactas, que se han indicado previamente en los dos primeros capitulos. En el ultimo capitulo se generaliza un resultado clasico de Devisage, de Quillen.

Autor: Garrido Vizuete María de los Ángeles.
Año: 1996.
Universidad: SEVILLA.
Centro de lectura: Dpto. Matemática Aplicada I.
Centro de realización: Matemática Aplicada I.

Resumen: El área de investigación sobre dibujos de grafos (graph drawing) se ha convertido en un campo extensamente estudiado, constituyendo una interesante conexión entre la computación y la teoría de grafos. Dentro de ella, la representación ortogonal de grafos ocupa un lugar importante por su aplicación al diseño de circuitos VLSI, dando lugar a diversos problemas de optimización. Esta memoria está dedicada al estudio de las inmersiones ortogonales de grafos en superficies, con el objeto de minimizar el número de codos. Motivados por el trabajo de Tamassia realizado en el plano, nos planteamos el problema de caracterizar la inmersión ortogonal cilíndrica que presenta el mínimo número de codos, entre todas las equivalentes a las de partida. Comenzamos realizando la caracterización de la asignación ortogonal óptima, concepto que recoge la información de los ángulos y codos del trazado, obteniéndola en tiempo polinomial. En el plano, los conceptos de asignación ortogonal e inmersión en la malla son equivalentes. Sin embargo, en el cilindro la situación es muy distinta, por lo que realizamos un estudio detallado de la relación entre ambas estructuras, destacando las diferencias con respecto al plano. Igualmente, diseñamos algoritmos efectivos que proporcionan inmersiones ortogonales cilíndricas, de forma que el número total de codos obtenido constituye una buena aproximación del valor óptimo, guiados por dos enfoques, uno global en el grafo y otro local en cada arista. Desde un punto de vista práctico, es necesario el estudio de inmersiones ortogonales de grafos en superficies. Este hecho nos conduce al planteamiento de dos importantes problemas en este ámbito, demostrando su naturaleza NP-completa: dada una inmersión en una superficie, decidir si admite una inmersión ortogonal sin codos esencialmente equivalente; y por otra parte, encontrar una superficie en la que un grafo dado admita una inmersión ortogonal sin codos. Dada la intratabilidad computacional de estos problemas, para obtener soluciones óptimas, presentamos algorítmos lineales de construcción de inmersiones ortogonales en superficies arbitrarias, que constituyen buenas aproximaciones a la solución óptima.

Autor: BRUNAT BLAY JOSEP M..
Año: 1994.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: INFORMATICA.
Centro de realización: DEPARTAMENTO: MATEMATICA APLICADA III PROGRAMA DE DOCTORADO: MATEMATICA APLICADA.

Resumen: EN ESTE TRABAJO SE ESTUDIAN PRINCIPALMENTE PROBLEMAS QUE TIENEN SU ORIGEN EN EL DISEÑO DE MEMORIAS DINAMICAS Y DE REDES DE INTERCONEXION SIMETRICAS. ALGUNAS DE LAS CONTRIBUCIONES SON: (I) DETERMINACION DE LOS GRUPOS CROMATICOS DE DIFERENTES DIGRAFOS ARCOLOREADOS UTILIZADOS COMO MODELOS DE MEMORIAS DINAMICAS; (II) CARACTERIZACION DE LOS DIGRAFOS LINEA QUE SON DE CAYLEY POR COLORACIONES UNIFORMEMENTE INDUCIDAS; (III) CONTRIBUCIONES AL OBJETIVO DE CARACTERIZAR LOS DIGRAFOS LINEA DE GRADO 2 QUE SON DE CAYLEY; (IV) ESTUDIO DE LOS DIGRAFOS LINEA ITERADOS DE LOS CICLOS GENERALIZADOS COMPLETOS DE CAYLEY Y RELACION CON CODIGOS CICLICOS; (V) PARA LOS DIGRAFOS PERTENECIENTES A LAS FAMILIAS SIGUIENTES SE DETERMINA EL GRUPO DE AUTOMORFISMOS, CUALES SON DE CAYLEY Y LOS LINEA ITERADOS DE CAYLEY: CICLOS GENERALIZADOS CASI COMPLETOS (EN PARTICULAR LOS DIGRAFOS DE KAUTZ), DIGRAFOS DE PERMUTACIONES Y DIGRAFOS DE FABER Y MOORE.

Autor: DIANEZ MARTINEZ ANA ROSA.
Año: 1994.
Universidad: SEVILLA .
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: MATEMATICA APLICADA I PROGRAMA DE DOCTORADO: MATEMATICA APLICADA Y TECNICAS COMPUTACIONALES.

Resumen: EL OBJETIVO DE ESTA TESIS ES EXTENDER EL CONCEPTO DE CENTRO DE UN GRAFO, DEFINIDO PARA GRAFOS FINITOS, A GRAFOS INFINITOS. EN TODO PROBLEMA DE LOCALIZACION SUBYACE UNA ESTRUCTURA DE GRAFO, DE AHI LA RELACION ENTRE LA TEORIA DE GRAFOS Y LA TEORIA DE LOCALIZACION. UNO DE LOS PROBLEMAS QUE TIENEN EN COMUN ES EL ESTUDIO DEL CENTRO. LA MAYORIA DE LOS PROBLEMAS DE LOCALIZACION SE PLANTEAN Y RESUELVEN PARA UNA ESTRUCTURA ESTATICA. PERO EN LA REALIDAD CUALQUIER SISTEMA EVOLUCIONA Y ES INTERESANTE DAR METODOS DE RESOLUCION DE PROBLEMAS QUE NOS PERMITAN ACTUALIZAR UNA SOLUCION CUANDO LOS DATOS INICIALES HAN SIDO MODIFICADOS. EN ESTE TRABAJO NOS PLANTEAMOS EL SIGUIENTE PROBLEMA DINAMICO: "?COMO HACER CRECER UN GRAFO FINITO DE FORMA QUE ALGUNOS O TODOS LOS VERTICES DEL CENTRO ESTEN EN EL CENTRO DEL NUEVO GRAFO?". DE ESTA PREGUNTA SURGE, DE FORMA NATURAL, LA FORMA DE EXTENDER EL CONCEPTO DE CENTRO A GRAFOS INFINITOS. LA EXTENSION SE REALIZA A TRAVES DE FAMILIAS CRECIENTES DE GRAFOS FINITOS QUE CONSERVAN ALGUN VERTICE DEL CENTRO Y QUE RECUBREN AL GRAFO INFINITO. A VECES, EL GRAFO ASOCIADO A UN DETERMINADO PROBLEMA DE LOCALIZACION NOS DA MENOS INFORMACION QUE EL GRAFO DE LINEA. POR ESTA RAZON, ES INTERESANTE PROFUNDIZAR EN EL ESTUDIO DEL GRAFO DE LINEA. EN ESTA MEMORIA TAMBIEN ANALIZAMOS LA RELACION QUE EXISTE ENTRE EL CENTRO DE UN GRAFO Y EL CENTRO DE SU GRAFO DE LINEA, EXTENDIENDO POSTERIORMENTE ESTA RELACION AL CASO INFINITO.

Autor: DANA JIMENEZ JUAN CARLOS.
Año: 1993.
Universidad: SEVILLA.
Centro de lectura: MATEMATICAS.
Centro de realización: DEPARTAMENTO: MATEMATICA APLICADA I PROGRAMA DE DOCTORADO: GEOMETRIA Y TOPOLOGIA (DEPARTAMENTO DE ALGEBRA, COMPUTACION, GEOMETRIA Y TOPOLOGIA)..

Resumen: 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 UNA ALGORITMICA PARA GRAFOS PERIODICOS, EN ESTE TRABAJO SE CONSTRUYEN ALGORITMOS QUE RESPONDEN SI EL GRAFO PERIODICO ES CONEXO O NO, QUE CONSTRUYEN UN ARBOL GENERADOR, Y ALGORITMOS QUE RESPONDEN AL PROBLEMA DE LA PLANARIDAD DE UN GRAFO PERIODICO Y A LA PLANARIDAD SIN ACUMULACION DE VERTICES (P-PLANARIDAD). LOS ALGORITMOS AQUI PRESENTADOS PARA GRAFOS PERIODICOS, RESUELVEN LOS PROBLEMAS ANTERIORMENTE CITADOS EN TIEMPO POLINOMIAL.