Estructuras métricas en grafos

Resumo

La memoria Estructuras métricas en grafos se divide en cinco capítulos. En el primero se introducen las reglas para el manejo de conjuntos, listas y diccionarios en SAGE en el entorno de la Teoría Axiomática de Conjuntos, en él se establece el concepto de clausura transitiva de una relación y se programa un algoritmo para obtenerla. En el segundo capítulo se presenta los núcleos como listas de tripletas o como diccionarios de palabras de 2 letras en un alfabeto de n letras. Cada núcleo induce una aplicación lineal y a partir de ella se establece la estrecha relación entre la Teoría de Grafos y el Algebra Lineal. Se introducen los núcleos laplacianos, los grafos y los multidigrafos. En el capítulo tercero se estudian diferentes cuasimétricas asociadas a núcleos y se estudian sus intervalos de existencia y cuando los espacios métricos resultantes son embebibles en un Hilbert. Se estudian cuasimétricas y métricas en digrafos a través de la envoltura transitiva de una relación. También se estudian métricas laplacianas en digrafos comprobando que las métricas de Klein-Randic y de Chebotarev- Shamis se pueden mostrar como un caso particular de nuestra presentación. En el capítulo cuarto se aprovechan los algoritmos presentados en el trabajo Designing Hamiltonian Cycles y se comprueba su bondad por comparación con cotas inferiores de Kruskal y de Vidal. Se utilizan los resultados para establecer valoraciones del test colorimétrico de Farnsworth-Munsell que mide la capacidad de discriminación cromática y la visión defectiva del color en los seres humanos. Finaliza el capítulo con el estudio de árboles hamiltonianos mínimos y la valoración de la bondad abierta de una lista de complejos. En el capítulo quinto se estudian los árboles mínimos de Steiner aportando los algoritmos Steiner3, Steiner4 y Steiner5 que para listas L de 3, 4 o 5 complejos nos dan los puntos de Steiner de L, el dibujo del árbol mínimo de Steiner, la longitud del mismo y una comparación normalizada entre la longitud del árbol hamiltoniano mínimo y la longitud del árbol de Steiner que llamamos ganancia. Mediante la función Steiner4 se presentan modelos que pueden explicar las deformaciones de Stone-Wales y la Mitosis en membranas de grafeno. Se proponen algoritmos para hallar atajos de Steiner sobre árboles hamiltonianos óptimos y finalmente se presentan los conceptos de constantes de ganancia para tratar la conjetura de Gilbert y Pollak.