Resumen de Estudio y construcción de estructuras topológicas idóneas para la modelización de redes de interconexión
Eduardo Alberto Canale Betancourt
En esta tesis se estudia el problema grado-diámetro, o problema (Delta-De), surgido del intento diseñar topologáis eficientes para redes de interconexión en circuitos de integración a muy grande escala. El mismo consiste en hallar el máximo número de vértices que puede tener un grafo con grado máximo Delta y diámetro De fijos. Hemos organizado la tesis en nueve capítulos más uno con conclusiones.
Los primeros dos capítulos son una introducción y un repaso de los dos conceptos y resultados básicos de la teoría de grafos. El resto de los capítulos está dividido en dos partes una para digrafos y otra para grafos.
La primera consta de cuatro capítulos (números, 3,4,5 y 6). Los primeros tres tratan del problema en el contexto de los digrafos unilateralmente conexo, esto es, aquellos para los cuales entre dos vértices existe un camino dirigido que los une sin importar el vértice origen y el final.
El último capítulo trata el problema para digrafos cuando se considera como grado la suma de los grados de salida y de entrada. En el Capítulo 3 se establece cotas superiores al estilo de Moore, tanto para el caso general como para el caso bipartido y para p--ciclos generalizados. Mejoramos dichas cotas para digrafos con grado de entrada y salida 2 y diámetro unilateral 2 y para p--ciclos generalizados con diámetro unilateral p impar. Encontramos diagrafos de Moore para el caso de digrafos bipartidos con diámetros unilaterales 2 y 3.
En el Capítulo 4 establecemos cotas inferiores a digrafos con grado y diámetro unilateral fijos y pequeños, usando diferentes técnicas como la de digrafos de voltaje, diagrafos producto, unión de ciclos y duplicación de vértices.
En el Capítulo 5 damos cotas inferiores que son asintóticamente mejores que las conocidas hasta ahora, cuando el grado tiende a infinito y el diámetro unilaterial permanece fijo. También estudiamos el comportamiento del operador línea en el contexto un
