Abstract
El incontrolado desarrollo de las ciencias de la computación en las últimas décadas
ha provocado que actualmente se generen millones de bytes de contenido
cada minuto a lo largo del globo. Es por esto que la teoría de grafos, rama
dentro de las matemáticas discretas, cobra cada vez más importancia dentro de
las ciencias de la información. Esta teoría no solo nos permite modelar grafos,
sino que tambien permite obtener información a partir de redes de nodos. La
confluencia de las matemáticas con la informática en este ámbito es lo que hace
tan atractivo este proyecto como trabajo de fin de grado.
A lo largo de la presente memoria estudiaremos las triangulaciones de grafos,
comúnmente utilizadas con el objetivo de modelizar redes inalámbricas, y los
conjuntos dominantes, que proporcionan conjuntos de vértices característicos.
Este estudio está orientado bajo un punto de vista experimental, donde buscamos
obtener resultados a partir datos estadísticos gracias a muestras aleatorias de vértices.
Con el fin de conseguir dichas muestras, se ha desarrollado una aplicación
que permite visualizar grafos y generar datos estadísticos relativos a los conjuntos
dominantes y triangulaciones implementadas. Además, se han obtenido resultados
que han permitido establecer nuevas cotas experimentales, además de comprender
en mejor medida cuan de buenos eran los diferentes algoritmos propuestos.---ABSTRACT---The uncontrolled computer science development over the past decades has lead us
to a world where millions of unique bytes of information are being generated every
minute. That is the reason behind why graph theory, field which lies within the
discrete mathematics, has becomed increasingly significant for information technologies.
This theory not only implies modeling graphs, but also allows obtaining
information based on connected networks. The confluence between mathematics
and computer science in this field is what makes this project attractive as a final
degree portfolio.
Along this paper we will study graph triangulations, commonly used for
modeling wireless networks, and dominating sets, which provide sets of characteristic
nodes. This research is oriented under an experimental point of view,
where we try to obtain results upon statistical data thanks to randomly distributed
node samples. With the purpose of achieving this samples, we have developed an
application capable of visualizing graphs and generating statistical data regarding
the implemented dominating sets and triangulations. Moreover, acquired results
have permitted establishing new experimental boundaries, as well as led us to
understand which algorithm performed better among the proposed.
