Teorema de Tutte
Tutte theorem
- Fecha
- 1947 · fiabilidad alta
- Lugar
- Cambridge, Inglaterra, Reino Unido
- Autoría
- W. T. Tutte
- Ámbito
- Saber y símbolos
Qué se descubrió
Teorema de teoría de grafos que caracteriza los grafos finitos no dirigidos que admiten un emparejamiento perfecto, mediante una condición sobre el número de componentes de tamaño impar al eliminar cualquier subconjunto de vértices; es un caso especial de la fórmula de Tutte-Berge.
A qué dio paso
- Resultado fundacional de la teoría de emparejamientos
- Base de algoritmos polinómicos para comprobar la existencia de emparejamientos perfectos
- Influencia en la optimización combinatoria y la teoría de flujos en redes