Registro:
| Documento: | Tesis de Grado |
| Título: | Caracterización estructural de los árboles de thinness propia 2 |
| Autor: | Maqueda, Ignacio |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2023 |
| Fecha en portada: | 2023 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Bonomo, Flavia |
| Consejero: | Pardal, Nina |
| Jurado: | Becher, Verónica Andrea; Lin, Min Chih |
| Idioma: | Español |
| Palabras clave: | ARBOLES; THINNESS PROPIA; CARACTERIZACIONESTREES; PROPER THINNESS; CHARACTERIZATIONS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000532_Maqueda |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000532_Maqueda.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000532_Maqueda |
| Ubicación: | Dep.COM 000532 |
| 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. Maqueda, Ignacio. (2023). Caracterización estructural de los árboles de thinness propia 2. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000532_Maqueda |
Resumen:
La thinness propia de un grafo es un invariante que generaliza a los grafos de intervalos propios. Todo grafo tiene un valor numérico de thinness propia y los grafos con thinness propia 1 coinciden con los grafos de intervalos propios. Un grafo es k-thin propio si sus vértices pueden ordenarse de manera que exista una partición de los vértices en k clases cumpliendo que para cada tripla de vértices r < s < t, tales que existe una arista entre r y t, se cumplen que si r y s pertenecen a la misma clase, entonces existe una arista entre s y t, y si s y t pertenecen a la misma clase, entonces existe una arista entre r y s. La thinness propia de un grafo es el menor valor de k tal que el grafo sea k-thin propio. En este trabajo nos enfocamos en el cálculo de la thinness propia para los árboles. Caracterizamos los árboles de thinness propia 2, tanto estructuralmente como por sus subgrafos inducidos minimales prohibidos. También mostramos por qué los resultados obtenidos para árboles de thinness propia 2 no pueden ser generalizados a árboles de thinness propia 3.
Abstract:
The proper thinness of a graph is an invariant that generalizes the concept of a proper interval graph. Every graph has a numerical value of proper thinness and the graphs with proper thinness 1 are exactly the proper interval graphs. A graph is proper k-thin if its vertices can be ordered in such a way that there is a partition of the vertices into k classes satisfying that for each triple of vertices r < s < t, such that there is an edge between r and t, it is true that if r and s belong to the same class, then there is an edge between s and t, and if s and t belong to the same class, then there is an edge between r and s. The proper thinness is the smallest value of k such that the graph is proper k-thin. In this work we focus on the calculation of proper thinness for trees. We characterize trees of proper thinness 2, both structurally and by their minimal forbidden induced subgraphs. We also show why the results obtained for trees of proper thinness 2 cannot be generalized to trees of proper thinness 3.
Citación:
---------- APA ----------
Maqueda, Ignacio. (2023). Caracterización estructural de los árboles de thinness propia 2. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000532_Maqueda
---------- CHICAGO ----------
Maqueda, Ignacio. "Caracterización estructural de los árboles de thinness propia 2". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2023.https://hdl.handle.net/20.500.12110/seminario_nCOM000532_Maqueda
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000532_Maqueda.pdf
Distrubución geográfica
