Resumen:
Los grafos perfectos fueron introducidos por Berge en los inicios de la década del ‘60 y a partir de allí fueron extensamente estudiados en la literatura. Se dice que un grafo G es perfecto cuando el número cromático es igual al tamaño del clique máximo para todo subgrafo inducido de G. En esta tesis determinamos la complejidad computacional de los problemas algorítmicos asociados a los grafos perfectos y sus variantes (grafos clique-perfectos, grafos K-perfectos, grafos coordinados) tanto en el caso general como dentro de la clase de los grafos clique-Helly hereditarios. Definimos los grafos balanceados como aquellos cuya matriz clique es balanceada. Es sabido que las matrices balanceadas son perfectas y, en consecuencia, los grafos balanceados son grafos perfectos. Mostramos que la clase de los grafos balanceados tiene reconocimiento polinomial, encontramos nuevas caracterizaciones para esta clase en términos de sus ciclos impares y de sus cliques y estudiamos algunas de sus subclases. El grafo clique de un grafo G es el grafo intersección de los subgrafos completos maximales de G. Los grafos clique han sido estudiados en el contexto de grafos de intersección y operadores en grafos. En 1971, Roberts y Spencer dieron una caracterización para la clase de grafos clique K(G). Sin embargo, ningún algoritmo eficiente ha podido ser formulado en función de esa caracterización. La caracterización de los grafos clique ha sido realizada para diversas clases de grafos, mientras que para algunas otras aún es un problema abierto. En esta tesis caracterizamos los grafos clique de varias clases de grafos, entre ellas los grafos balanceados, los totalmente unimodulares, los grafos clique-Helly y perfectos y los grafos trivialmente perfectos.
Citación:
---------- APA ----------
Bonomo, Flavia. (2002). Sobre grafos balanceados y complejidad computacional de problemas asociados a la teoría de grafos perfectos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000624_Bonomo
---------- CHICAGO ----------
Bonomo, Flavia. "Sobre grafos balanceados y complejidad computacional de problemas asociados a la teoría de grafos perfectos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2002.https://hdl.handle.net/20.500.12110/seminario_nMAT000624_Bonomo
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000624_Bonomo.pdf
Distrubución geográfica
