Grafos uniformemente más confiables. Una prueba simple de la conjetura de Gross-Saccoman.

Abstract

Existe un amplio campo de aplicaciones de las técnicas de confiabilidad en redes, desde la comunicación y la computación, pasando por sistemas de transporte hasta sistemas eléctricos de potencia. En todos ellos sus componentes pueden fallar o degradarse y esto inevitablemente puede conducir a la incapacidad del sistema para soportar una operación requerida. Si pensamos en un grafo como representación de alguno de los sistemas anteriores, un problema importante en esta área es poder determinar la confiabilidad de dicho sistema a partir de la confiabilidad de sus componentes. La noción de confiabilidad de un grafo tiene distintas variantes y depende del tipo de fallas a considerar, ya sean vértices o aristas, como del modelo de confiabilidad a utilizar. En este trabajo, consideraremos que los vértices son perfectos y las aristas fallan de forma aleatoria e independiente, con probabilidad idéntica e igual a ρ.

Además, consideraremos el modelo de confiabilidad all-terminal, el cual se define como la probabilidad de que el subgrafo aleatorio resultante de eliminar las aristas que fallan sea conexo. Una vez que hemos modelado una red y definido una medida de confiabilidad, cabe preguntarse cómo podríamos diseñar una red que alcance la máxima confiabilidad. Podríamos sintetizar el problema de la siguiente manera. Fijados n y e, el problema consiste en encontrar un grafo simple con n vértices y e aristas que minimice la probabilidad de falla del grafo para un valor de ρ fijo. Como hay una cantidad finita de grafos con n vértices y e aristas, dicho grafo siempre existe, asumiendo un valor de ρ fijo. Siguiendo la misma línea, uno podría también dar un paso más ambicioso y preguntarse si existe un grafo simple que tenga la mayor confiabilidad para todos los valores de ρ dentro del intervalo [0, 1]. Entonces, diremos que un grafo es Uniformemente Más Confiable (UMRG, por sus siglas en inglés) si tiene la mayor confiabilidad entre todos los posibles grafos, con el mismo número de vértices y aristas, para todos los valores de ρ. Este concepto fue introducido por Boesch en 1986 y posteriormente en 1991 Boesch et al. demostraron que siempre existen grafos uniformemente más confiables para todas aquellas clases de grafos simples con n vértices y e aristas tales que e ≤ n + 2. Más tarde, en 1994, Wang demuestra que en cada clase de grafos simples tales que e = n + 3 y n ≥ 6 existe un único grafo que es UMRG. Trabajos más recientes prueban la existencia o inexistencia de grafos simples UMRG para valores particulares de e y n. Inmediatamente surge la pregunta de qué sucede si permitimos aristas múltiples y pasamos a considerar multigrafos. En 1997, Gross y Saccoman prueban que los UMRG dentro de las clases de grafos simples tales que e ≤ n + 2 también son uniformemente más confiables cuando extendemos las clases para incluir multigrafos. En ese mismo artículo, los autores conjeturan que para el caso en que e = n+3 el UMRG también es óptimo en multigrafos, lo cual es demostrado por Romero en 2020. En esta tesis se realiza una revisión bibliográfica de los artículos fundamentales del área y se presenta un resultado novedoso que culmina en la publicación de un artículo de co-autoría en la revista Networks: “A simple proof of the Gross- Saccoman multigraph conjecture” 1. En el mismo se introduce una prueba simple a la conjetura de Gross-Saccoman y se extiende la misma a pseudografos.