El Polinomio de Tutte

Abstract

RESUMEN: El Polinomio de Tutte es una herramienta importante para el estudio de grafos y redes, que generaliza a la vez al Polinomio Cromático, el Polinomio de Flujos, así como de otros invariantes de un grafo. Su definición está basada en usar recursivamente las operaciones de borrado y contracción de aristas del grafo inicial hasta obtener una expresión polinómica final. De hecho, es común hablar de la “universalidad” de este polinomio, en el sentido de que cualquier invariante que se pueda obtener con recursiones de este tipo es una especialización del mismo. Por último, la definición del polinomio se extiende a matroides, objetos abstractos cuya combinatoria captura la independencia lineal en espacios vectoriales y que se relacionan con los grafos a través de sus matrices de incidencia.

ABSTRACT: The Tutte polynomial is an important tool for analyzing properties of graphs and networks, generalizing at the same time the Chromatic polynomial, the Flow polynomial, and other graph invariants. It is defined via a recursive formula using deletion and contraction operation on the initial graph, until a final polynomial expression is obtained. In fact, it is a “universal” invariant, in the sense that all functions that can be created by this type of deletion/contraction recurrence are specializations of it. Lastly, the definition of this polynomial extends to matroids, abstract objects whose combinatorics captures the preperties of linear independence in vector spaces. Matroids are related to graphs via their incidence matrices.