Del teorema de grafos menores a las descomposiciones arbóreas
Date
2022-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Benemérita Universidad Autónoma de Puebla
Abstract
"El Teorema de Grafos Menores es uno de los resultados más importantes dentro de la Teoría de Grafos. Este teorema fue enunciado inicialmente como una conjetura por el matemático alemán Klaus Wagner en 1937. En esta conjetura se establecía la existencia, dentro de una sucesión contable de grafos nitos, de un par de grafos comparables bajo la relación menor. Por muchos años dicho planteamiento fue conocido como la Conjetura de Wagner, hasta su demostración, realizada por Neil Robertson y Paul D. Seymour, la cual les llevó alrededor 20 artículos, desarrollados en más de 20 años. El extenso trabajo de Robertson y Seymour en grafos menores trajo consigo repercusiones en otras ramas como: Teoría de grafos menores, teoría estructural de grafos y aplicaciones algorítmicas. Dentro de las aplicaciones algorítmicas sobresalen numerosas herramientas y métodos, como la descomposición arbórea, ancho arbóreo y otros más. También las clases de grafos que cumplen con la propiedad de ser menor cerrada pueden proporcionar una buena descripción de ciertas propiedades y proporcionar algoritmos eficientes para probar si un elemento dado satisface una propiedad determinada".
Description
Keywords
Citation
Collections
Document Viewer
Select a file to preview:
Can't see the file? Try reloading