Resumen:
Este trabajo consiste de seis capítulos. En el primero se introduce la notación necesaria y algunas nociones sobre grafos perfectos. En el segundo capítulo abordamos el teorema débil de grafos perfectos, en la primer sección mostramos como Lovász demuestra este teorema utilizando teoría de grafos, mientras que en la segunda sección damos una breve introducción sobre teoría poliedral, la relación que existe entre poliedros y grafos perfectos y como se utiliza para demostrar el teorema débil; esta demostración alternativa mantiene los rasgos generales de la demostración de Fulkerson. El tercer capítulo contiene una aplicación del famoso algoritmo del elipsoide, algoritmo de suma importancia teórica, que fue aprovechada por Grötschel, Lovász y Schrijver para demostrar que el problema de coloreo se puede resolver en tiempo polinomial, para los grafos perfectos. En el cuarto capítulo veremos los pasos que se siguieron para demostrar la conjetura fuerte sobre grafos perfectos y cuales fueron las ideas utilizadas, sin ahondar en los detalles técnicos de la demostración. En el quinto capítulo estudiaremos el algoritmo de reconocimiento de grafos perfectos, si bien la demostración de la conjetura fuerte fue un resultado de gran importancia, este algoritmo polinomial no utiliza de manera directa el teorema fuerte en su implementación. Finalmente en el sexto capítulo, veremos dos variantes importantes de los grafos perfectos: los grafos clique perfectos, K-perfectos y una serie de resultados relevantes obtenidos en estos últimos años.
Citación:
---------- APA ----------
Grippo, Luciano Norberto. (2006). Grafos perfectos : una reseña sobre los principales resultados conocidos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000876_Grippo
---------- CHICAGO ----------
Grippo, Luciano Norberto. "Grafos perfectos : una reseña sobre los principales resultados conocidos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2006.https://hdl.handle.net/20.500.12110/seminario_nMAT000876_Grippo
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000876_Grippo.pdf
Distrubución geográfica
