Contribución al coloreado de grafos y las redes pequeño-mundo.

Abstract

En la presente tesis se analiza el problema del coloreado de grafos tanto desde el punto de vista teórico como en relación a la resolución del problema mediante técnicas algorítmicas, algunas de las cuales se describen por vez primera. Se estudian asimismo distintas variaciones del problema simple del coloreado incluyendo el coloreado de vértices etiquetados, en que se asigna un número variable de colores a cada vértice, y el coloreado con aristas etiquetadas, en el que los colores asignados a vértices adyacentes deben guardar una distancia mayor o igual a la etiqueta de la arista que los une, así como combinaciones de ambos.<br/><br/>Las técnicas descritas para el coloreado de grafos han sido posteriormente adaptadas a un problema de asignación de frecuencias en telefonía móvil habiéndose aplicado los algoritmos sobre distintos tipos de redes celulares. Las distintas redes analizadas pueden incorporar o no conmutación en frecuencia, variando la naturaleza del problema en cada caso. Para el caso de coloreado múltiple asociado al problema de asignación de frecuencias se ha descrito un conjunto de matrices asociadas a un grafo G(V,E) y un coloreado simple C que permiten reasignar colores a distintos vértices de G(V,E) aprovechando colores de C. Este reciclaje, en combinación con las métodos algorítmicos aplicados en coloreados simples, ha permitido resolver con eficiencia el problema del multicoloreado de grafos y en consecuencia el problema de asignación de frecuencias en redes celulares.<br/><br/>En la segunda parte de la tesis se estudian las redes pequeño-mundo y se describen pautas deterministas para su obtención. De este modo se describe en primer lugar el modelo probabilista definido por Watts y Strogatz y se analiza la aparición de autoorganización crítica en las redes pequeño-mundo (caracterizadas por un apiñamiento elevado y un diámetro o distancia máxima entre vértices reducido) para a continuación ampliar el concepto sobre modelos deterministas. Se ha demostrado de este modo la posibilidad de obtener redes pequeño-mundo sobre grafos circulantes, mallas toroidales e hipercubos.<br/><br/>Finalmente se ha probado la universalidad del efecto pequeño-mundo, es decir, la posibilidad de recortar arbitrariamente el diámetro de un grafo genérico G(V,E) sin que se produzcan variaciones significativas en su topología local (medida a partir del factor de clustering o apiñamiento del grafo), explicando así la ubicuidad de las redes pequeño-mundo y su descripción en entornos de todo tipo: social, biológico, industrial, matemático, etcétera.