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

Título:

Refutación a la conjetura de Boesch para clases de grafos de corango 7.

Otros títulos:

Coordinador:

Director:

Compilador:

Autor:

Rodríguez Otormín, Juan Manuel
Craviotto, Matías

Tutor:

Romero, Pablo

Tipo de documento:

Tesis de grado

Editor:

Palabras clave:

Confiabilidad
Grafo uniformemente más confiable
Teoría de grafos
Corango
Conjetura de Boesch
Conjetura de Ath y Sobel

Descriptores:

Año de publicación:

2024

Contenido:

Resumen:

Este proyecto de grado se enmarca en el estudio de confiabilidad de redes. Sea Cn,m la clase de todos los grafos simples y conexos con n vértices y m aristas. Sea G un grafo perteneciente a la clase Cn,m y ρ ∈ [0, 1]. La confiabilidad del grafo G evaluada en ρ, que se denota RG(ρ), es la probabilidad de que el subgrafo que resulta de eliminar a cada una de las aristas de G con probabilidad ρ y de manera independiente sea conexo. Decimos que un grafo G en Cn,m es uniformemente más confiable si para todo grafo H en Cn,m y todo ρ ∈ [0, 1] se cumple que RG(ρ) ≥ RH(ρ). En 1986, Boesch conjeturó que en cada una de las clases no vacías Cn,m existe al menos un grafo que es uniformemente más confiable. El corango de la clase Cn,m y de cada uno de los grafos de dicha clase vale m − n + 1. A partir de la literatura clásica de confiabilidad uniforme se concluye que en cada una de las clases no vacías Cn,m cuyo corango es 4 o menor existe exactamente un grafo que es uniformemente más confiable. Ath y Sobel conjeturaron que cada una de las clases Cn,m cuyo corango es c ∈ {5, 6, 7, 8} tales que n ≥ 2c − 2 tiene exactamente un grafo que es uniformemente más confiable. Recientemente se ha demostrado que existen infinitas clases Cn,m cuyos corangos son 5 o 6 para las cuales no existe ningún grafo uniformemente más confiable, por lo que las conjeturas de Boesch y Ath y Sobel no son ciertas para corangos 5 ni 6. El objetivo de este proyecto consiste en determinar si es cierta la conjetura de Ath y Sobel para aquellas clases de grafos Cn,m que poseen corango 7. Como resultado, hemos refutado la conjetura de Ath y Sobel para corango 7, construyendo al mismo tiempo una nueva familia de contraejemplos para la conjetura de Boesch. Concretamente, hemos demostrado que para cada entero s tal que s ≥ 9 no existe ningún grafo uniformemente confiable en C18s−6,18s. Nuestros estudios reflejan fuerte evidencia computacional de inexistencia de grafos uniformemente más confiables en otras clases de corango 7.

Descripción:

Editorial:

EN:

Financiadores:

Citación:

Rodríguez Otormín, J. y Craviotto, M. Refutación a la conjetura de Boesch para clases de grafos de corango 7 [en línea] Tesis de grado. Montevideo: Udelar. FI. INCO, 2024.

Citación:

metadata.cc.license.name:

Documento del Gobiberno:

URI:

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

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 (CC - By 4.0)

Cobertura geográfica:

Cobertura temporal:

metadata.dc.relation.IsVersionOf:

Clasificación:

Es versión de:

Colecciones:

Tesis de grado
FicherosDescripciónTamañoFormato
RC24.pdf Tesis de grado 576.02 KB Adobe PDF
Mostrar el registro Dublin Core completo del ítem