Resumen:
Los grafos circulares son los grafos intersección de cuerdas dentro de un cÍrculo. Los grafos sin diamantes son los grafos que no tienen un diamante como subgrafo inducido. Estas dos clases de grafos han sido muy estudiadas a partir de la década del '70 y tienen diversas aplicaciones. Además, varios problemas NP-completos tienen solución eficiente en grafos pertenecientes a algunas de sus subclases. Recientemente, fue planteada una conjetura que caracteriza a la clase de los grafos circulares Helly como aquellos que son circulares y sin diamantes. Trabajaremos en esta tesis en el estudio de algunas propiedades que pueden ayudar en la demostración de esta conjetura. Particularmente, estudiamos un método para conseguir representaciones de grafos Helly circulares en porciones arbitrariamente pequeñas del círculo. Implementamos un algoritmo polinomial de reconocimiento de grafos circulares, con el objetivo de poder desarrollar una herramienta que permita visualizar las representaciones en modelos de cuerdas de estos grafos. Hasta nuestro conocimiento existen varios artículos de reconocimiento polinomial de grafos circulares pero ninguno de ellos ha sido implementado. Estos desarrollos son hechos en el lenguaje de programación Java, y tienen como objetivo continuar con la construcción de un paquete de algoritmos para acelerar las investigaciones en estas clases de grafos. Además, estudiamos una extensión del operador clique de un grafo que nos permite obtener más información sobre el grafo original una vez aplicada esta operación. En particular, estudiamos propiedades de este operador sobre los grafos sin diamantes. Como último punto, sacamos conclusiones sobre la tesis y la carrera completa y proponemos futuros trabajos extendiendo lo aquí desarrollado.
Citación:
---------- APA ----------
Barrionuevo, Juan Manuel; Calvo, Aureliano. (2004). Sobre grafos circulares y sin diamantes. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000781_BarrionuevoCalvo
---------- CHICAGO ----------
Barrionuevo, Juan Manuel; Calvo, Aureliano. "Sobre grafos circulares y sin diamantes". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2004.https://hdl.handle.net/20.500.12110/seminario_nCOM000781_BarrionuevoCalvo
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000781_BarrionuevoCalvo.pdf
Distrubución geográfica
