Registro:
| Documento: | Tesis de Grado |
| Título: | Sobre grafos perfectos y sus variantes : caracterizaciones estructurales y algoritmos de reconocimiento |
| Autor: | Busolini, Lucía |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Fecha de defensa: | 2021-07-30 |
| Fecha en portada: | 30 de julio de 2021 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias Matemáticas |
| Departamento Docente: | Departamento de Matemáticas |
| Director: | Durán, Guillermo Alfredo |
| Jurado: | Jerónimo, Gabriela Talí; Bonomo, Flavia |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nMAT001026_Busolini |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT001026_Busolini.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nMAT001026_Busolini |
| Ubicación: | Dep.MAT 001026 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Busolini, Lucía. (2021). Sobre grafos perfectos y sus variantes : caracterizaciones estructurales y algoritmos de reconocimiento. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nMAT001026_Busolini |
Resumen:
Los grafos perfectos fueron definidos por Claude Berge en 1961. Se dice que un grafo es perfecto si vale la igualdad entre el número cromático y el tamaño de la clique máxima, para todo subgrafo inducido. Recién en 2002, pudo probarse una caracterización de los grafos perfectos por subgrafos prohibidos y, en 2005, se diseñó un algoritmo polinomial para reconocer si un grafo es perfecto o no. A raíz de la definición de la clase de grafos perfectos, surgieron otras variantes de clases de grafos definidas a partir de la igualdad de ciertos parámetros, entre ellas las clases de grafos clique-perfectos, coordinados y neighborhood-perfectos. Guruswami y Pandu Rangan definieron en 2000 que un grafo es clique-perfecto si vale la igualdad entre el cardinal de un conjunto máximo de cliques independientes, donde dos cliques se dicen independientes si no tienen vértices en común, y el cardinal de un conjunto mínimo de vértices que intersecan todas las cliques, para todo subgrafo inducido. Marina Groshaus definió en 2001 que un grafo es coordinado si vale la igualdad la cantidad máxima de cliques a la que pertenece un vértice y la cantidad mínima de colores necesaria para colorear las cliques del grafo, para todo subgrafo inducido. Lehel y Tuza definieron en 1985 que un grafo es neighborhood-perfecto como aquellos para los cuales vale la igualdad entre la cantidad mínima de vecindades necesarias para cubrir todos los vértices y aristas, y el cardinal máximo de un conjunto de aristas tal que no haya dos en la misma vecindad, para todo subgrafo inducido. En este trabajo se mencionan las caracterizaciones conocidas de estas clases de grafos, algunos ejemplos y algoritmos de reconocimiento. Dado que no se conocen caracterizaciones parciales de las últimas tres clases de grafos mencionadas, estudiaremos caracterizaciones de estas clases de grafos restringidas a ciertas clases como los grafos sin triángulos, los diamond-free, entre otras. Al igual que la complejidad del problema de reconocimiento en cada caso.
Citación:
---------- APA ----------
Busolini, Lucía. (2021). Sobre grafos perfectos y sus variantes : caracterizaciones estructurales y algoritmos de reconocimiento. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT001026_Busolini
---------- CHICAGO ----------
Busolini, Lucía. "Sobre grafos perfectos y sus variantes : caracterizaciones estructurales y algoritmos de reconocimiento". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2021.https://hdl.handle.net/20.500.12110/seminario_nMAT001026_Busolini
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT001026_Busolini.pdf
Distrubución geográfica
