Por favor, use este identificador para citar o enlazar este ítem: https://hdl.handle.net/20.500.12008/53163

Título:

Grafos con dos terminales uniformemente más confiables bajo el modelo de falla de vértices : La conjetura de Brown es cierta cuando d=4

Otros títulos:

Coordinador:

Director:

Compilador:

Autor:

Miranda, Felipe

Tutor:

Romero, Pablo
Cancela Bosi, Héctor

Tipo de documento:

Tesis de grado

Editor:

Palabras clave:

Teoría de grafos
Confiabilidad de redes
Grafo con dos terminales uniformemente más confiables
Fallas de vértices

Descriptores:

Año de publicación:

2025

Contenido:

Resumen:

Un grafo con dos terminales G es un grafo que posee dos vértices distinguidos en V (G), denominados terminales. Sean n, m y d enteros positivos tales que n ≥ d − 1 y 1 ≤ m ≤ (n+2/2). Sea Td n,m el conjunto de todos los grafos con dos terminales que poseen exactamente n vértices no terminales, m aristas, y la distancia entre sus terminales es igual a d. Sea p un número real en [0, 1] y sea G un grafo con dos terminales en Td n,m. La confiabilidad de G se denota NRG(p) y se define como la probabilidad de que exista un camino entre los terminales de G en el subgrafo de G resultante de remover independientemente a cada uno de sus vértices no terminales con probabilidad 1 − p. Decimos que G es uniformemente más confiable en Td n,m si para todo H en Td n,m y todo p en [0, 1] se cumple que NRG(p) ≥ NRH(p). En trabajos previos se ha logrado caracterizar la existencia e inexistencia de grafos con dos terminales uniformemente más confiables en cada clase no vacía Td n,m cuando d es no mayor que 3. Brown et al. [Networks 76(3):414-426, 2020] conjeturaron que no existe ningún grafo con dos terminales uniformemente más confiable en Td n,m cuando d ≥ 4, n ≥ 2(d − 1) y 2d ≤ m ≤ (d − 2)⌊n /(d−1)⌋2 + ⌊n /d−1⌋ − 1. El objetivo de este proyecto de grado es analizar si la conjetura de Brown et al. es correcta cuando d = 4. Por un lado, se determinan propiedades inherentes a todos los grafos con dos terminales que son localmente más confiables en T4n,m cuando p es próximo a 1. Por otro lado, se demuestra que ninguno de dichos grafos con dos terminales es localmente más confiable cuando p es próximo a 0. Para llevar a cabo esta segunda fase se desarrolla una metodología novedosa basada en programación no lineal entera. Dicha metodología permite probar que la conjetura de Brown es cierta cuando d = 4, excepto en aquellos pares de enteros n y m tales que n ≥ 9 y m = 11. En dichos casos, se han desarrollado programas que permiten realizar un estudio computacional exhaustivo. Dicho estudio basado en asistencia computacional permite confirmar que la conjetura de Brown es correcta cuando d = 4.

Descripción:

Editorial:

Udelar. FI.

EN:

Financiadores:

Citación:

Miranda, F. Grafos con dos terminales uniformemente más confiables bajo el modelo de falla de vértices : La conjetura de Brown es cierta cuando d=4 [en línea] Tesis de grado. Montevideo : Udelar. FI. INCO, 2025.

Citación:

metadata.cc.license.name:

Documento del Gobiberno:

URI:

https://hdl.handle.net/20.500.12008/53163

ISBN:

e-ISBN:

ISSN:

ISMN:

Otros identificadores:

Título Obtenido:

Ingeniero en Computación

Facultad o Servicio que otorga el Título:

Universidad de la República (Uruguay). Facultad de Ingeniería

Licencia:

Licencia Creative Commons Atribución - No Comercial (CC - By-NC 4.0)

Cobertura geográfica:

Cobertura temporal:

metadata.dc.relation.IsVersionOf:

Clasificación:

Es versión de:

Colecciones:

Tesis de grado
FicherosDescripciónTamañoFormato
Mir25.pdf Tesis de grado 3.21 MB Adobe PDF
Mostrar el registro Dublin Core completo del ítem