Tutte path

En teoría de grafos , un camino de Tutte es un camino${\displaystyle P}$dentro de un gráfico${\displaystyle G}$de tal manera que cada componente conectado que queda después de eliminar los vértices de${\displaystyle P}$de${\displaystyle G}$está conectado de nuevo a${\displaystyle P}$en un número limitado de vértices.

La definición precisa se basa en los siguientes términos: ^{[ 1 ]}

• ${\displaystyle P}$-puente : Para una ruta dada${\displaystyle P}$en un gráfico${\displaystyle G}$, a${\displaystyle P}$-bridge es o bien un único borde que no está en${\displaystyle P}$que conecta dos vértices de${\displaystyle P}$, o es un componente conectado del grafo que queda después de eliminar los vértices de${\displaystyle P}$, junto con todos los bordes que conectan este componente con${\displaystyle P}$.
• Punto de fijación : Los puntos de fijación de un${\displaystyle P}$-los puentes son los vértices del camino${\displaystyle P}$que están conectados por una arista a un vértice dentro del${\displaystyle P}$-puente.

Un camino de Tutte es entonces un camino${\displaystyle P}$en${\displaystyle G}$de tal manera que cada${\displaystyle P}$-puente que queda después de eliminar los vértices de${\displaystyle P}$de${\displaystyle G}$tiene como máximo tres puntos de unión al camino.${\displaystyle P}$. Además, si un${\displaystyle P}$-bridge contiene aristas de la cara exterior del grafo (en el contexto de grafos planares ), está restringido a tener como máximo dos puntos de conexión. ^{[ 2 ] [ 3 ]}

El concepto de caminos de Tutte se originó con el trabajo fundamental de WT Tutte en 1977. ^{[ 4 ]} Tutte demostró un resultado fundamental sobre la existencia de tales caminos en grafos planares:

Teorema de Tutte : Sea${\displaystyle G}$Sea un grafo planar 2-conexo con vértices distintos.${\displaystyle X}$y${\displaystyle Y}$en la cara exterior. Deje${\displaystyle \alpha }$ser un borde en la cara exterior. Entonces${\displaystyle G}$tiene un camino Tutte desde${\displaystyle X}$a${\displaystyle Y}$que utiliza borde${\displaystyle \alpha }$. ^{[ 4 ]}

Este resultado garantiza que los caminos de Tutte existen en grafos planares 2-conexos con puntos finales específicos y que contienen una arista específica, lo que los convierte en una poderosa herramienta estructural para analizar dichos grafos.

Durante muchos años, se desconocía si los caminos de Tutte podían calcularse en tiempo polinomial. Un avance significativo se produjo en 2015 cuando Schmid y Schmidt demostraron que los caminos de Tutte en grafos planares 3-conexos pueden hallarse en tiempo polinomial, con su algoritmo ejecutándose en tiempo cuadrático. ^{[ 5 ]} Este resultado se extendió posteriormente a grafos planares 2-conexos en 2018. ^{[ 2 ]}

En 2019, Biedl y Kindermann lograron otro avance importante al demostrar que los caminos de Tutte se pueden encontrar en tiempo lineal . ^{[ 6 ]} Su enfoque proporciona una nueva prueba de la existencia de caminos de Tutte en grafos planares 3-conectados que es constructiva y conduce directamente a un algoritmo eficiente. La clave reside en reducir el problema a encontrar caminos de Tutte en componentes 3-conectadas utilizando árboles SPQR , y luego manejar grafos 3-conectados con un análisis caso por caso basado en la estructura de pares de corte y la cara externa.

Una motivación clave para el estudio de los caminos de Tutte es su estrecha relación con los caminos y ciclos hamiltonianos , caminos y ciclos en un grafo que visitan cada vértice exactamente una vez. Un camino de Tutte es una relajación de este concepto; no requiere que todos los vértices estén en el camino. Sin embargo, las restricciones en los puentes proporcionan información estructural importante sobre el grafo, que luego puede usarse para encontrar un camino o ciclo hamiltoniano, especialmente en grafos planares.

Los caminos de Tutte se han aplicado para resolver varios problemas importantes en grafos planares:

• Árboles de expansión binarios : Todo grafo planar 3-conexo tiene un árbol de expansión de grado máximo 3 (también llamado árbol de expansión binario). Utilizando caminos de Tutte con sistemas de representantes distintos, estos árboles pueden construirse en tiempo lineal. ^{[ 6 ]}

• 2-walks : Un 2-walk de un grafo es un camino que visita cada vértice al menos una vez y como máximo dos veces. Todo grafo planar 3-conexo tiene un 2-walk, y utilizando el algoritmo de camino de Tutte de tiempo lineal, dicho camino se puede encontrar en tiempo lineal, mejorando la cota mejor anterior de${\displaystyle O(n^{3})}$. ^{[ 6 ]}

• Problema de la trayectoria hamiltoniana
• La conjetura de Tait
• Árbol SPQR

• Michael C. Wigal, Tutte Senderos y Cubiertas Uniformes