Registro:
| Documento: | Tesis de Grado |
| Título: | Sobre la thinness en un grafo |
| Título alternativo: | On the thinness of a graph |
| Autor: | Brito, Gastón |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2020 |
| Fecha en portada: | 2020 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Bonomo, Flavia |
| Jurado: | Grippo, Luciano Norberto; Melgratti, Hernán Claudio |
| Idioma: | Español |
| Palabras clave: | GRAFO; THINNESS; INTERVALO; BOXICITY; INTERSECCION; BANDWIDTH; SMT; Z3GRAPH; THINNESS; INTERVAL; BOXICITY; INTERSECTION; BANDWIDTH; SMT; Z3 |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000574_Brito |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000574_Brito.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000574_Brito |
| Ubicación: | Dep.COM 000574 |
| 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. Brito, Gastón. (2020). Sobre la thinness en un grafo. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000574_Brito |
Resumen:
La thinness de un grafo, definida inicialmente en 2007, es un invariante que generaliza a los grafos de intervalos. Todo grafo tiene un valor numérico de thinness y los grafos con thinness 1 coinciden con los grafos de intervalos. Un grafo es k-thin si sus vértices pueden ordenarse de manera que exista una partición de los v´ertices en k clases cumpliendo que para cada tripla de vértices r < s < t si r y s pertenecen a la misma clase y existe una arista entre r y t, entonces existe una arista entre s y t. La thinness es el menor valor de k tal que el grafo sea k-thin. En este trabajo definimos un modelo de intersección para los grafos con thinness y thinness propia menor o igual a 2 restringiendo los grafos con boxicity 2. Se caracterizan los grafos k-thin y k-thin propios utilizando propiedades de la matriz de adyacencia. Se acota la thinness en relación al bandwidth de un grafo y se hace un resumen de las relaciones conocidas. Se calcula la thinness utilizando SAT Module Theory (SMT), tanto para determinar si vale la propiedad k-thin como para obtener el valor de la thinness mediante optimización. Se evalúa la performance sobre familias de grafos con los resolvedores Z3 Theorem Solver y OptiMathSat. Adicionalmente se utilizan las mismas técnicas para calcular una representación como una intersección de rectángulos en el plano.
Abstract:
The thinness of a graph, initially defined in 2007, is an invariant that generalizes the concept of an interval graph. Every graph has a numeric value of thinness and the graphs with thinness 1 are exactly the interval graphs. A graph is k-thin if its vertices can be sorted in a way that exists a partition with k classes with the property that for each triplet of vertices r < s < t if r and s belong to the same class and there is an edge between r y t, then an edge must exist between s and t. The thinness is the least value of k such that the graph is k-thin. In this work we define an intersection model for graphs with thinness and proper thinness lower or equal than 2 by restricting graphs with boxicity 2. The properties of adjacency matrices are used to characterize k-thin and proper k-thin graphs. A bound of the thinness with the bandwidth is obtained and a summary of the known relations is made. It is shown how to calculate the thinness with SAT Module Theory (SMT), both for checking the k-thin property and obtaining the thinness value with optimization. The performance of the Z3 Theorem Solver and OptiMathSat are analized. Additionally the same techniques are used to obtain a representation as an intersection of rectangles on the plane.
Citación:
---------- APA ----------
Brito, Gastón. (2020). Sobre la thinness en un grafo. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000574_Brito
---------- CHICAGO ----------
Brito, Gastón. "Sobre la thinness en un grafo". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2020.https://hdl.handle.net/20.500.12110/seminario_nCOM000574_Brito
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000574_Brito.pdf
Distrubución geográfica
