En los campos matemáticos de la teoría de grafos y la combinatoria , un polinomio coincidente (a veces llamado polinomio acíclico ) es una función generadora de la cantidad de coincidencias de varios tamaños en un gráfico. Es uno de los varios polinomios de grafos que se estudian en la teoría de grafos algebraicos .
Definición
Se han definido varios tipos diferentes de polinomios coincidentes. Sea G una gráfica con n vértices y sea m k el número de coincidencias de k -edge.
Un polinomio coincidente de G es
Otra definición da el polinomio coincidente como
Una tercera definición es el polinomio
Cada tipo tiene sus usos y todos son equivalentes mediante simples transformaciones. Por ejemplo,
y
Conexiones con otros polinomios
El primer tipo de polinomio coincidente es una generalización directa del polinomio de torre .
El segundo tipo de polinomio coincidente tiene conexiones notables con polinomios ortogonales . Por ejemplo, si G = K m , n , el gráfico bipartito completo , entonces el segundo tipo de polinomio coincidente está relacionado con el polinomio de Laguerre generalizado L n α ( x ) por la identidad:
Si G es el gráfico completo K n , entonces M G ( x ) es un polinomio de Hermite:
donde H n ( x ) es el "polinomio de Hermite del probabilista" (1) en la definición de polinomios de Hermite . Estos hechos fueron observados por Godsil (1981) .
Si G es un bosque , entonces su polinomio coincidente es igual al polinomio característico de su matriz de adyacencia .
Si G es un camino o un ciclo , entonces M G ( x ) es un polinomio de Chebyshev . En este caso μ G (1, x ) es un polinomio de Fibonacci o un polinomio de Lucas respectivamente.
Complementacion
El polinomio coincidente de una gráfica G con n vértices está relacionado con el de su complemento por un par de fórmulas (equivalentes). Uno de ellos es una identidad combinatoria simple debida a Zaslavsky (1981) . La otra es una identidad integral debida a Godsil (1981) .
Existe una relación similar para un subgrafo G de K m , n y su complemento en K m , n . Esta relación, debida a Riordan (1958), se conocía en el contexto de las colocaciones de torres no atacantes y los polinomios de torres.
Aplicaciones en informática química
El índice de Hosoya de un gráfico G , su número de coincidencias, se utiliza en quimioinformática como descriptor estructural de un gráfico molecular. Puede evaluarse como m G (1) ( Gutman 1991 ).
El tercer tipo de polinomio coincidente fue introducido por Farrell (1980) como una versión del "polinomio acíclico" utilizado en química .
Complejidad computacional
En gráficas arbitrarias, o incluso gráficas planas , calcular el polinomio coincidente es # P-completo ( Jerrum 1987 ). Sin embargo, se puede calcular de manera más eficiente cuando se conoce la estructura adicional sobre el gráfico. En particular, calcular el polinomio coincidente en n gráficos de vértices de ancho de árbol k es manejable con parámetros fijos : existe un algoritmo cuyo tiempo de ejecución, para cualquier constante fija k , es un polinomio en n con un exponente que no depende de k ( Courcelle, Makowsky y Rotics 2001 ). El polinomio coincidente de un gráfico con n vértices y ancho de clique k puede calcularse en el tiempo n O ( k ) ( Makowsky et al. 2006 ).
Referencias
- Courcelle, B .; Makowsky, JA; Rotics, U. (2001), "Sobre la complejidad de parámetros fijos de los problemas de enumeración de gráficos definibles en lógica monádica de segundo orden" (PDF) , Matemáticas aplicadas discretas , 108 (1–2): 23–52, doi : 10.1016 / S0166 -218X (00) 00221-3.
- Farrell, EJ (1980), "El polinomio coincidente y su relación con el polinomio acíclico de un gráfico", Ars Combinatoria , 9 : 221-228.
- Godsil, CD (1981), "Polinomios de Hermite y una relación de dualidad para polinomios de emparejamiento", Combinatorica , 1 (3): 257-262, doi : 10.1007 / BF02579331.
- Gutman, Ivan (1991), "Polinomios en teoría de grafos", en Bonchev, D .; Rouvray, DH (eds.), Teoría de gráficos químicos: Introducción y fundamentos , Química matemática, 1 , Taylor & Francis, págs. 133–176, ISBN 978-0-85626-454-2.
- Jerrum, Mark (1987), "Los sistemas bidimensionales de monómero-dímero son computacionalmente intratables", Journal of Statistical Physics , 48 (1): 121-134, doi : 10.1007 / BF01010403.
- Makowsky, JA; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Calcular polinomios de gráficos en gráficos de ancho de camarilla acotado", Proc. 32 ° Taller internacional sobre conceptos teóricos de gráficos en informática (WG '06) (PDF) , Lecture Notes in Computer Science, 4271 , Springer-Verlag, págs. 191-204, doi : 10.1007 / 11917496_18.
- Riordan, John (1958), Introducción al análisis combinatorio , Nueva York: Wiley.
- Zaslavsky, Thomas (1981), "Vectores complementarios de coincidencia y la propiedad de extensión de coincidencia uniforme", European Journal of Combinatorics , 2 : 91–103, doi : 10.1016 / s0195-6698 (81) 80025-x.