Grafos de Bouchet : una generalización de los grafos circulares

Mostrar todas las versiones(3)

Un grafo circular es el grafo intersección de cuerdas en un círculo. Estos han sido introducidos por Even e Itai en los '70 y muy estudiados en la literatura. Existen diferentes caracterizaciones para esta clase de grafos. Una de ellas utiliza el concepto de complementaciones locales, y fue apo...

Descripción completa

Detalles Bibliográficos
Autor principal: Czemerinski, Hernán
Formato: Tesis de Grado
Lenguaje:Español
Publicado: 2001
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000172_Czemerinski
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:seminario_nCOM000172_Czemerinski
record_format dspace
spelling todo:seminario_nCOM000172_Czemerinski2023-10-03T16:48:09Z Grafos de Bouchet : una generalización de los grafos circulares Czemerinski, Hernán Un grafo circular es el grafo intersección de cuerdas en un círculo. Estos han sido introducidos por Even e Itai en los '70 y muy estudiados en la literatura. Existen diferentes caracterizaciones para esta clase de grafos. Una de ellas utiliza el concepto de complementaciones locales, y fue aportada por André Bouchet en 1994. En el presente trabajo, utilizamos la idea de esta caracterización para definir una nueva clase, que generalizan a los circulares, y a los cuales llamamos Grafos de Bouchet. Probamos que estos grafos también generalizan a los grafos de intervalos, con lo que son una generalización de la unión de ambas clases; encontramos, por medio del uso de la computadora, una caracterización por 33 subgrafos prohibidos de la nueva clase; y vemos que como consecuencia de esta caracterización se obtiene un reconocimiento polinomial. Por último, mostramos que existen 396 formulaciones diferentes para el teorema de caracterización de Bouchet para grafos circulares. Fil: Czemerinski, Hernán. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2001 Tesis de Grado PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/seminario_nCOM000172_Czemerinski
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv Español
description Un grafo circular es el grafo intersección de cuerdas en un círculo. Estos han sido introducidos por Even e Itai en los '70 y muy estudiados en la literatura. Existen diferentes caracterizaciones para esta clase de grafos. Una de ellas utiliza el concepto de complementaciones locales, y fue aportada por André Bouchet en 1994. En el presente trabajo, utilizamos la idea de esta caracterización para definir una nueva clase, que generalizan a los circulares, y a los cuales llamamos Grafos de Bouchet. Probamos que estos grafos también generalizan a los grafos de intervalos, con lo que son una generalización de la unión de ambas clases; encontramos, por medio del uso de la computadora, una caracterización por 33 subgrafos prohibidos de la nueva clase; y vemos que como consecuencia de esta caracterización se obtiene un reconocimiento polinomial. Por último, mostramos que existen 396 formulaciones diferentes para el teorema de caracterización de Bouchet para grafos circulares.
format Tesis de Grado
author Czemerinski, Hernán
spellingShingle Czemerinski, Hernán
Grafos de Bouchet : una generalización de los grafos circulares
author_facet Czemerinski, Hernán
author_sort Czemerinski, Hernán
title Grafos de Bouchet : una generalización de los grafos circulares
title_short Grafos de Bouchet : una generalización de los grafos circulares
title_full Grafos de Bouchet : una generalización de los grafos circulares
title_fullStr Grafos de Bouchet : una generalización de los grafos circulares
title_full_unstemmed Grafos de Bouchet : una generalización de los grafos circulares
title_sort grafos de bouchet : una generalización de los grafos circulares
publishDate 2001
url https://hdl.handle.net/20.500.12110/seminario_nCOM000172_Czemerinski
work_keys_str_mv AT czemerinskihernan grafosdebouchetunageneralizaciondelosgrafoscirculares
_version_ 1807320806127042560

Ejemplares similares