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
Otros Autores: Durán, Guillermo Alfredo
Formato: Tesis de grado publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 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 seminario:seminario_nCOM000172_Czemerinski
record_format dspace
spelling seminario:seminario_nCOM000172_Czemerinski2025-05-09T18:44:46Z Grafos de Bouchet : una generalización de los grafos circulares Czemerinski, Hernán Durán, Guillermo Alfredo 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. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2001-10-17 info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion application/pdf spa 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 spa
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.
author2 Durán, Guillermo Alfredo
author_facet Durán, Guillermo Alfredo
Czemerinski, Hernán
format Tesis de grado
Tesis de grado
publishedVersion
author Czemerinski, Hernán
spellingShingle Czemerinski, Hernán
Grafos de Bouchet : una generalización de los grafos circulares
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
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2001
url https://hdl.handle.net/20.500.12110/seminario_nCOM000172_Czemerinski
work_keys_str_mv AT czemerinskihernan grafosdebouchetunageneralizaciondelosgrafoscirculares
_version_ 1831983705071026176

Ejemplares similares