Optimización de la conectividad algebraica para caminos con pesos.

Cruz Ortega, Alonso

dc.contributor.author	Cruz Ortega, Alonso
dc.date.accessioned	2023-10-30T16:29:15Z
dc.date.available	2023-10-30T16:29:15Z
dc.date.issued	2023-07-13
dc.identifier.govdoc	LMATA .15183 2023
dc.identifier.other	ATD31
dc.identifier.uri	http://dgsa.uaeh.edu.mx:8080/bibliotecadigital/handle/231104/3376
dc.description	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.	es_ES
dc.language.iso	es	es_ES
dc.publisher	ICBI-BD-UAEH	es_ES
dc.subject	Teoría espectral de gráficas	es_ES
dc.subject	Conectividad algebraica	es_ES
dc.subject	Resistencia efectiva	es_ES
dc.subject	Optimización	es_ES
dc.subject	Álgebra lineal	es_ES
dc.subject	Matemáticas Aplicadas.	es_ES
dc.title	Optimización de la conectividad algebraica para caminos con pesos.	es_ES
dc.title.alternative	Matemáticas Aplicadas.	es_ES
dc.type	Tesis	es_ES