Métodos algebraicos para la determinación de grafos uniformemente más confiables

Abstract

Este proyecto se enmarca dentro del estudio de confiabilidad de redes. Sean n y m enteros tales que n ≥ 3 y n − 1 ≤ m ≤ n 2 (n 2), y sea Cn,m la clase de grafos conexos y simples con n vértices y m aristas. El co-rango de cada uno de los grafos dentro de la clase Cn,m es m − n + 1. Sea G un grafo en Cn,m y sea p ∈ [0, 1]. La confiabilidad RG(p) es la probabilidad de que el subgrafo que se obtiene de G tras retener a cada una de sus aristas independientemente con probabilidad p resulte conexo. Decimos que G es uniformemente más confiable si para cada grafo H en Cn,m y cada p ∈ [0, 1] se cumple que RG(p) ≥ RH(p). Boesch conjeturó en 1986 que cada una de las clases no vacías Cn,m posee algún grafo uniformemente más confiable. Posteriormente, en un trabajo colectivo, Boesch probó que cada una de las clases no vacías Cn,m de co-rango positivo no mayor que 3 posee un único grafo que es uniformemente más confiable. Además, en dicho trabajo se conjetura que, para cada entero n tal que n ≥ 6, existe un grafo uniformemente más confiable de co-rango 4 con n vértices que se obtiene mediante ciertas subdivisiones elementales del grafo bipartito completo K3,3. En 1994, Wang anunció que dicha conjetura es correcta y publicó su demostración. No obstante, un reciente artículo de Landgren y Steif en 2024 sugiere que hay errores en la demostración de Wang y que el resultado no es correcto. Dicho trabajo fue publicado en ArXiv y se encuentra bajo referato científico. De manera casi simultánea, Kahl y Luttrell definen el concepto de grafo Tutte-máximo que se basa en el polinomio de Tutte de un grafo, y prueban que cada grafo Tutte-máximo es uniformemente más confiable. En este proyecto se desea validar o refutar computacionalmente la afirmación realizada por Wang en 1994 utilizando métodos inspirados en grafos Tutte-máximos. Este proyecto de grado tiene tres objetivos. El primer objetivo consiste en familiarizarnos con los conceptos de grafo Tutte-máximo y de grafo uniformemente más confiable. El segundo objetivo consiste en desarrollar algoritmos eficientes para determinar el polinomio de Tutte para grafos de co-rango reducido. El tercer y último objetivo consiste en refutar o validar computacionalmente el teorema anunciado en 1994 por Wang. Nuestros resultados evidencian que la afirmación de Wang no es correcta y respaldan la corrección propuesta por Landgren y Steif.