Algoritmos aleatorios para sistemas separadores.
Loading...
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
Dado un grafo G, una colección P de caminos de G es un sistema separador fuerte de caminos si para cada par de aristas distintas e y f hay un camino en P que contiene e pero no f. El proyecto enmarca el estudio de manera teórica y algorítmica de los sistemas separadores fuertes de caminos para el grafo bipartito completo Kn,m. Por el lado teórico, encontramos cotas para el tamaño mínimo de un sistema separador fuerte de caminos de Kn,m, y además proporcionamos grafos y digrafos auxiliares que permiten el estudio de los sistemas separadores de manera general. A partir de estos grafos y dígrafos diseñamos algoritmos para encontrar sistemas de caminos separadores fuertes, realizando su análisis teórico para el grafo Kn,m. Finalmente logramos implementar computacionalmente estos algoritmos, corroborando los resultados teóricos obtenidos por medio de un análisis experimental.
Description
Tesis presentada para optar al título de Ingeniero Civil Matemático
Keywords
Algoritmos, Grafos dirigidos, Teoría de grafos