Cortes en grafos utilizando resultados de teoría espectral

"Dentro de la gran variedad de problemas que se encuentran en el ámbito de teoría de grafos, hay muchos para los cuales encontrar una solución exacta es muy difícil o imposible. Uno de estos problemas es el de partición de un grafo no dirigido en n vértices, dadas unas restricciones en el volumen de las particiones. En este, se desea separar el conjunto de vértices en dos grupos con los requerimientos de minimizar el tamaño del corte, en otras palabras, el número de arcos entre los grupos, y maximizar el volumen de los conjuntos. Pero, las soluciones algorítmicas para el problema de encontrar el corte óptimo, son muy costosas. Usando teoría espectral buscaremos un método que nos permita encontrar una solución aproximada a este problema. Con este fin se encontrará una relajación del problema de hallar el mejor corte en términos del cociente de Raleigh de la matriz Laplaciana. Luego se demostrará la desigualdad de Cheeger para grafos regulares, la cual nos da una relación no trivial entre el mejor corte y el segundo valor propio. En la siguiente parte del capítulo se adapta el resultado a grafos irregulares. Con esto se construirá un algoritmo que, dado un vector propio asociado al segundo valor propio más pequeño, tiene como salida un corte que cumple la desigualdad de Cheeger."--Tomado del Formato de Documento de Grado.

• Autores: Perdomo Villegas, Santiago
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2018
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: spa
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/39221
• Acceso en línea: http://hdl.handle.net/1992/39221
• Palabra clave: Teoría de grafos; Teoría espectral (Matemáticas); Matrices (Matemáticas); Grafos bipartitos; Matrices laplacianas; Matemáticas
• Rights: openAccess
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/