Caracterización estructural de algunos problemas en grafos circle y de intervalos

Mostrar todas las versiones(3)

Dada una familia de conjuntos no vacíos S= {Si}, se define el grafo de intersección de la familia S como el grafo obtenido al representar con un vértice a cada conjunto Si de forma tal que dos vértices son adyacentes sí y sólo si los conjuntos correspondientes tienen intersección no vacía. Un grafo...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Pardal, Nina
Otros Autores: Durán, Guillermo A.
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2020
Materias:
GRAFOS
CIRCULO
SUBGRAFOS PROHIBIDOS
COMPLETACION
MINIMAL
GRAPHS
CIRCLE
FORBIDDEN INDUCED SUBGRAPHS
COMPLETION
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n6763_Pardal
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n6763_Pardal
record_format dspace
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
topic GRAFOS
CIRCULO
SUBGRAFOS PROHIBIDOS
COMPLETACION
MINIMAL
GRAPHS
CIRCLE
FORBIDDEN INDUCED SUBGRAPHS
COMPLETION
MINIMAL
spellingShingle GRAFOS
CIRCULO
SUBGRAFOS PROHIBIDOS
COMPLETACION
MINIMAL
GRAPHS
CIRCLE
FORBIDDEN INDUCED SUBGRAPHS
COMPLETION
MINIMAL
Pardal, Nina
Caracterización estructural de algunos problemas en grafos circle y de intervalos
topic_facet GRAFOS
CIRCULO
SUBGRAFOS PROHIBIDOS
COMPLETACION
MINIMAL
GRAPHS
CIRCLE
FORBIDDEN INDUCED SUBGRAPHS
COMPLETION
MINIMAL
description Dada una familia de conjuntos no vacíos S= {Si}, se define el grafo de intersección de la familia S como el grafo obtenido al representar con un vértice a cada conjunto Si de forma tal que dos vértices son adyacentes sí y sólo si los conjuntos correspondientes tienen intersección no vacía. Un grafo se dice círculo si existe una familia de cuerdas L= {Cv} veG [fórmula aproximada, revisar la misma en el original] en un círculo de modo que dos vértices son adyacentes si las cuerdas correspondientes se intersecan. Es decir, es el grafo de intersección de la familia de cuerdas L. Existen diversas caracterizaciones de los mismos mediante operaciones como complementación local o descomposición split. Sin embargo, no se conocen aún caracterizaciones estructurales de los grafos círculo por subgrafos inducidos minimales prohibidos. En esta tesis, damos una caracterización de los grafos círculo por subgrafos inducidos prohibidos, restringido a que el grafo original sea split. Una matriz de0’s y1’s tiene la propiedad de los unos consecutivos (C1P) para sus filas si existe una permutación de sus columnas de forma tal que para cada fila, todos sus1’s se ubiquen de manera consecutiva. En esta tesis desarrollamos caracterizaciones por submatrices prohibidas de matrices de0’s y 1’s con la C1P para sus filas que además son2-coloreables bajo una cierta relación de adyacencia, y caracterizamos estructuralmente algunas subclases de grafos círculo auxiliares que se desprenden de estas matrices. Dada una clase de grafos [letra griega pi], una [letra griega pi] -completación de un grafo G= (V;E)es un grafo H= (V;E[F) [fórmula aproximada, revisar la misma en el original] tal que H pertenezca a [letra griega pi]. Una [letra griega pi] -completación H de G es minimal si H0=(V;E[F0) [fórmula aproximada, revisar la misma en el original] no pertenece a [letra griega pi] para todo F0 subconjunto propio de F. Una [letra griega pi] -completación H de G es mínima si para toda [letra griega pi] -completaciónH0= (V;E[F0) de G [fórmula aproximada, revisar la misma en el original], se tiene que el tamaño de F es inferior o igual al tamaño de F0. En esta tesis estudiamos el problema de completar de forma minimal a un grafo de intervalos propios, cuando el grafo de inputes de intervalos. Hallamos condiciones necesarias que caracterizan una completación minimal en este caso, y dejamos algunas conjeturas para considerar en el futuro.
author2 Durán, Guillermo A.
author_facet Durán, Guillermo A.
Pardal, Nina
format Tesis doctoral
Tesis doctoral
publishedVersion
author Pardal, Nina
author_sort Pardal, Nina
title Caracterización estructural de algunos problemas en grafos circle y de intervalos
title_short Caracterización estructural de algunos problemas en grafos circle y de intervalos
title_full Caracterización estructural de algunos problemas en grafos circle y de intervalos
title_fullStr Caracterización estructural de algunos problemas en grafos circle y de intervalos
title_full_unstemmed Caracterización estructural de algunos problemas en grafos circle y de intervalos
title_sort caracterización estructural de algunos problemas en grafos circle y de intervalos
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2020
url https://hdl.handle.net/20.500.12110/tesis_n6763_Pardal
work_keys_str_mv AT pardalnina caracterizacionestructuraldealgunosproblemasengrafoscircleydeintervalos
AT pardalnina structuralcharacterizationofsomeproblemsoncircleandintervalgraphs
AT pardalnina caracterisationstructurelledequelquesproblemesdanslesgraphesdecordesetdintervalles
_version_ 1782023029822324736
spelling tesis:tesis_n6763_Pardal2023-10-02T20:21:44Z Caracterización estructural de algunos problemas en grafos circle y de intervalos Structural characterization of some problems on circle and interval graphs Caractérisation structurelle de quelques problèmes dans les graphes de cordes et d’intervalles Pardal, Nina Durán, Guillermo A. Valencia-Pabon, Mario GRAFOS CIRCULO SUBGRAFOS PROHIBIDOS COMPLETACION MINIMAL GRAPHS CIRCLE FORBIDDEN INDUCED SUBGRAPHS COMPLETION MINIMAL Dada una familia de conjuntos no vacíos S= {Si}, se define el grafo de intersección de la familia S como el grafo obtenido al representar con un vértice a cada conjunto Si de forma tal que dos vértices son adyacentes sí y sólo si los conjuntos correspondientes tienen intersección no vacía. Un grafo se dice círculo si existe una familia de cuerdas L= {Cv} veG [fórmula aproximada, revisar la misma en el original] en un círculo de modo que dos vértices son adyacentes si las cuerdas correspondientes se intersecan. Es decir, es el grafo de intersección de la familia de cuerdas L. Existen diversas caracterizaciones de los mismos mediante operaciones como complementación local o descomposición split. Sin embargo, no se conocen aún caracterizaciones estructurales de los grafos círculo por subgrafos inducidos minimales prohibidos. En esta tesis, damos una caracterización de los grafos círculo por subgrafos inducidos prohibidos, restringido a que el grafo original sea split. Una matriz de0’s y1’s tiene la propiedad de los unos consecutivos (C1P) para sus filas si existe una permutación de sus columnas de forma tal que para cada fila, todos sus1’s se ubiquen de manera consecutiva. En esta tesis desarrollamos caracterizaciones por submatrices prohibidas de matrices de0’s y 1’s con la C1P para sus filas que además son2-coloreables bajo una cierta relación de adyacencia, y caracterizamos estructuralmente algunas subclases de grafos círculo auxiliares que se desprenden de estas matrices. Dada una clase de grafos [letra griega pi], una [letra griega pi] -completación de un grafo G= (V;E)es un grafo H= (V;E[F) [fórmula aproximada, revisar la misma en el original] tal que H pertenezca a [letra griega pi]. Una [letra griega pi] -completación H de G es minimal si H0=(V;E[F0) [fórmula aproximada, revisar la misma en el original] no pertenece a [letra griega pi] para todo F0 subconjunto propio de F. Una [letra griega pi] -completación H de G es mínima si para toda [letra griega pi] -completaciónH0= (V;E[F0) de G [fórmula aproximada, revisar la misma en el original], se tiene que el tamaño de F es inferior o igual al tamaño de F0. En esta tesis estudiamos el problema de completar de forma minimal a un grafo de intervalos propios, cuando el grafo de inputes de intervalos. Hallamos condiciones necesarias que caracterizan una completación minimal en este caso, y dejamos algunas conjeturas para considerar en el futuro. Given a family of nonempty sets S= {Si} [fórmula aproximada, revisar la misma en el original], the intersection graph of the family S is the graph with one vertex for each set Si, such that two vertices are adjacent if and only if the corresponding sets have non empty intersection. A graph is circle if there is a family of chords in a circle L=fCvgv2G [fórmula aproximada, revisar la misma en el original such that two vertices are adjacent if the corresponding chords cross each other. In other words, it is the intersection graph of the chord family L. There are diverse characterizations of circle graphs, many of them using the notions of local complementation or split decomposition. However, there are no known structural characterization by minimal forbidden induced subgraphs for circle graphs.In this thesis, we give a characterization by forbidden induced subgraphs of those splitgraphs that are also circle graphs. A (0;1)-matrix has the consecutive-ones property (C1P) for the rowsif there is a permutation of its columns such that the1’s in each row appear consecutively. In this thesis, we develop characterizations by forbidden subconfigurations of(0;1)-matrices with the C1P for which the rows are 2-colorable under a certain adjacency relationship, and we characterize structurally some auxiliary circle graph sub-classes that arise from these special matrices.Given a graph class [greek letter pi], a [greek letter pi]-completion of a graph G= (V;E) is a graph H= (V;E[F) [fórmula aproximada, revisar la misma en el original] such that H belongs to [greek letter pi]. A [greek letter pi]-completion H of Gis minimal ifH0= (V;E[F0) [fórmula aproximada, revisar la misma en el original] does not belong to [greek letter pi] for every proper subset F0ofF [fórmula aproximada, revisar la misma en el original]. A [greek letter pi]-completion H of G is minimum if for every [greek letter pi] -completionH0= (V;E[F0) [fórmula aproximada, revisar la misma en el original] of G, the cardinal of F is less than or equalto the cardinal of F0. In this thesis, we study the problem of completing minimally toobtain a proper interval graph when the input is an interval graph. We find necessary conditions that characterize a minimal completion in this particular case, and we leave some conjectures for the future. Fil: Pardal, Nina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2020-03-30 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral 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/tesis_n6763_Pardal

Ejemplares similares