1. Universidad Autonoma del Estado de Hidalgo
  2. Tesis
  3. Tesis de Licenciatura
Por favor, use este identificador para citar o enlazar este ítem: http://dgsa.uaeh.edu.mx:8080/handle/231104/3376
Título : Optimización de la conectividad algebraica para caminos con pesos.
Otros títulos : Matemáticas Aplicadas.
Autor : Cruz Ortega, Alonso
Palabras clave : Teoría espectral de gráficas
Conectividad algebraica
Resistencia efectiva
Optimización
Álgebra lineal
Matemáticas Aplicadas.
Fecha de publicación : 13-jul-2023
Editorial : ICBI-BD-UAEH
Descripción : En nuestro trabajo, estudiamos dos cantidades que podrían considerarse como una manera de cuantificar el nivel de robustez de una gráfica (o grafo): la conectividad algebraica y la resistencia total. Las gráficas que consideramos son gráficas con pesos, esto es, gráficas tales que a cada arista se le ha asignado un valor positivo. Tanto la conectividad algebraica como la resistencia total se definen a partir del operador conocido como laplaciano u operador de Laplace de la gráfica, por lo que estas dos cantidades están, en un principio, relacionadas. Sin embargo, las definiciones de cada una de ellas son muy distintas y no es inmediato establecer alguna relación directa. La conectividad algebraica corresponde al valor del segundo eigenvalor más pequeño del laplaciano. Su estudio se remonta a los trabajos de Miroslav Fiedler quién estudió dicho valor para establecer algunas propiedades relacionadas con la conectividad de las gráficas. El estudio de los eigenvalores de operadores asociados a gráficas es lo que se conoce como teoría espectral de gráficas. Por otro lado, la resistencia total consiste en la suma de todas las distancias entre cada par de vértices de la gráfica, en donde, la distancia considerada es la métrica de resistencia efectiva. La métrica de resistencia efectiva tiene su inspiración en los circuitos eléctricos. Una de sus propiedades dice que vértices mejor conectados entre sí, en el sentido de que hay más caminos que unen dichos vértices, están más cerca. Es así que puede pensarse que la resistencia efectiva entre dos vértices es una manera de cuantificar el nivel de conexión que poseen y, por lo tanto, la resistencia total es una manera natural de cuantificar el nivel global de conexión de una gráfica. El objetivo central de este trabajo es presentar dos problemas de optimización de la conectividad algebraica. Primero, presentamos el problema, propuesto por Fiedler, que consiste en encontrar el valor máximo de la conectividad algebraica sujeta a que la suma de todos los valores que los pesos toman en las aristas de la gráfica sea constante. Fiedler denominó a tal valor como conectividad algebraica absoluta. Para abordar este problema, Fiedler en sus trabajos estudió el comportamiento de los eigenvectores asociados a la conectividad algebraica, que usualmente se conocen como vectores Fiedler y logró demostrar que el peso que proporciona la conectividad algebraica absoluta tiene la propiedad de que en aristas equivalentes toma el mismo valor. En este texto presentamos y explicamos la solución de tal problema, proporcionada por Fiedler, para los caminos de cualquier cantidad de vértices. La aportación original de nuestro trabajo es proponer el problema que consiste en hallar el valor máximo de la conectividad algebraica con la condición que la resistencia total de la gráfica esté fija, aunque, solo abordamos este problema en caminos. Los métodos que usamos se basan en los usados por Fiedler en sus trabajos. En especial, conjeturamos que el peso en el que se alcanza la conectividad algebraica máxima con resistencia total fija en un camino debe ser tal que en aristas equivalentes toma el mismo valor. Se presentan los cálculos de que la conjetura es cierta en el camino de tres y cuatro vértices, además, en tales caminos se presentan los cálculos para la solución del problema.
Documento del Gobiberno : LMATA .15183 2023
URI : http://dgsa.uaeh.edu.mx:8080/bibliotecadigital/handle/231104/3376
Aparece en las colecciones: Tesis de Licenciatura

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
ATD31.pdf1.2 MBAdobe PDFVisualizar/Abrir
Mostrar el registro Dublin Core completo del ítem


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.