En matemáticas, una gráfica polinomial es una gráfica invariante cuyos valores son polinomios . Las invariantes de este tipo se estudian en la teoría de grafos algebraicos . [1] Los polinomios de gráficos importantes incluyen:
- El polinomio característico , basado en la matriz de adyacencia del gráfico .
- El polinomio cromático , un polinomio cuyos valores en argumentos enteros dan el número de coloraciones del gráfico con esa cantidad de colores.
- El polinomio dicromático , una generalización de 2 variables del polinomio cromático
- El polinomio de flujo , un polinomio cuyos valores en argumentos enteros dan el número de flujos en ninguna parte-cero con cantidades de flujo enteras módulo el argumento.
- La (inversa de) la función zeta de Ihara , definida como un producto de términos binomiales correspondientes a ciertos paseos cerrados en un gráfico.
- El polinomio de Martin , utilizado por Pierre Martin para estudiar los viajes de Euler
- Los polinomios coincidentes , varios polinomios diferentes definidos como la función generadora de los emparejamientos de un gráfico.
- El polinomio de confiabilidad , un polinomio que describe la probabilidad de permanecer conectado después de fallas en los bordes independientes.
- El polinomio de Tutte , un polinomio en dos variables que se puede definir (después de un pequeño cambio de variables) como la función generadora de los números de componentes conectados de subgrafos inducidos del gráfico dado, parametrizado por el número de vértices en el subgrafo.