Sistemas de caminos separadores de vértices en árboles.
Loading...
Date
2025
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
La separación de vértices en un grafo es un problema relevante en teoría de grafos, con aplicaciones en áreas como la codificación, las redes y los problemas de identificación. Un enfoque natural, es separar los vértices a través de familias de caminos. Una familia de caminos separadora de vértices en un grafo es un conjunto de caminos tal que, para cualquier par de vértices, existe un camino en la familia que contiene exactamente uno de estos vértices.
En este trabajo nos enfocamos en estudiar el tamaño mínimo de una familia de caminos separadora de vértices en árboles. Nos centramos en estudiar diferentes subfamilias de árboles, considerando propiedades estructurales de ellos. Presentamos resultados exactos para diversas familias de árboles y mejoramos cotas previamente conocidas, extendiéndolas a clases más generales de árboles. Además, demostramos que, en árboles con racimos de tamaño uno, el número de separación no puede determinarse únicamente en función de parámetros locales, lo que ilustra la complejidad del problema.
Description
Tesis presentada para optar al título de Ingeniera Civil Matemática
Keywords
Teoría de grafos, Estructuras de datos (ciencia de la computación), Árboles (Teoría de los grafos)