Pasar al contenido principal

Grafos de traza mínima con máxima cantidad de árboles recubridores

Fecha de inicio
Fecha de fin
Archivo
Folleto (512.71 KB)

Martes 7 de octubre a las 16:00 en la Sala 101
de la Facultad de Ingeniería.

Pueden acceder a más detalles de la presentación en el sitio EVA del
Coloquio:
https://eva.fing.edu.uy/mod/forum/discuss.php?d=331876

Sean muy bienvenidas/os.


Resumen: Un grafo G es t-óptimo si posee la máxima cantidad de árboles
recubridores dentro de todos los grafos con la misma cantidad de
vértices y aristas que G. Frank Boesch conjeturó en 1986 que todo grafo
t-óptimo debe ser casi regular.

Luis Petingi y José Rodríguez desarrollaron una metodología que permite
probar, entre otras cosas, que todo grafo multipartito completo casi
regular es t-óptimo.

En esta charla revisaremos la metodología desarrollada por Louis Petingi
y José Rodríguez. Veremos una generalización de dicha metodología
realizada conjuntamente con Luis Petingi que permite encontrar infinitos
grafos t-óptimos que además son de traza mínima.