Соответствующий полином

В математических областях теории графов и комбинаторики многочлен сопоставления (иногда называемый ациклическим многочленом ) является производящей функцией числа сопоставлений различных размеров в графе. Это один из нескольких многочленов графа, изучаемых в алгебраической теории графов .

Определено несколько различных типов многочленов сопоставления. Пусть G — граф с n вершинами, а m _k — число k -реберных сопоставлений.

Один соответствующий многочлен G — это

${\displaystyle m_{G}(x):=\sum _{k\geq 0}m_{k}x^{k}.}$

Другое определение дает соответствующий многочлен как

${\displaystyle M_{G}(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}.}$

Третье определение — это многочлен

${\displaystyle \mu _{G}(x,y):=\sum _{k\geq 0}m_ {k}x^{k}y^{n-2k}.}$

Каждый тип имеет свое применение, и все они эквивалентны простыми преобразованиями. Например,

${\displaystyle M_{G}(x)=x^{n}m_{G}(-x^{-2})}$

и

${\displaystyle \mu _{G}(x,y)=y^{n}m_{G}(x/y^{2}).}$

Первый тип многочлена соответствия является прямым обобщением многочлена ладьи .

Второй тип многочлена соответствия имеет замечательные связи с ортогональными многочленами . Например, если G  =  K _{m , n} , полный двудольный граф , то второй тип многочлена соответствия связан с обобщенным многочленом Лагерра L _n ^α ( x ) тождеством:

${\displaystyle M_{K_{m,n}}(x)=n!L_{n}^{(mn)}(x^{2}).\,}$

Если G — полный граф K _n , то M _G ( x ) — многочлен Эрмита:

${\displaystyle M_{K_{n}}(x)=H_{n}(x),\,}$

где H _n ( x ) — «вероятностный полином Эрмита» (1) в определении полиномов Эрмита . Эти факты были отмечены Годсилом (1981).

Если G — лес , то его многочлен соответствия равен характеристическому многочлену его матрицы смежности .

Если G — путь или цикл , то M _G ( x ) — многочлен Чебышёва . В этом случае μ _G (1, x ) — многочлен Фибоначчи или многочлен Люка соответственно.

Полином соответствия графа G с n вершинами связан с полиномом его дополнения парой (эквивалентных) формул. Одна из них — простое комбинаторное тождество Заславского (1981). Другая — интегральное тождество Годсила (1981).

Аналогичное соотношение существует для подграфа G из K _{m , n} и его дополнения в K _{m , n} . Это соотношение, согласно Риордану (1958), было известно в контексте неатакующих размещений ладей и ладейных многочленов.

Индекс Хосоя графа G , его число соответствий, используется в хемоинформатике как структурный дескриптор молекулярного графа. Его можно оценить как m _G (1) (Gutman 1991).

Третий тип полинома соответствия был введен Фарреллом (1980) как версия «ациклического полинома», используемого в химии .

На произвольных графах или даже планарных графах вычисление полинома соответствия является #P-полным (Jerrum 1987). Однако его можно вычислить более эффективно, когда известна дополнительная структура о графе. В частности, вычисление полинома соответствия на n -вершинных графах древовидной ширины k является фиксированно-параметрически разрешимым : существует алгоритм, время выполнения которого для любой фиксированной константы k является полиномом от n с показателем, который не зависит от k (Courcelle, Makowsky & Rotics 2001). Полином соответствия графа с n вершинами и кликовой шириной k может быть вычислен за время n ^{O( k )} (Makowsky et al. 2006).

• Курсель, Б .; Маковски, JA; Ротикс, У. (2001), «О сложности фиксированных параметров задач перечисления графов, определяемых в монадической логике второго порядка» (PDF) , Дискретная прикладная математика , 108 (1–2): 23–52, doi :10.1016/S0166-218X(00)00221-3.
• Фаррелл, Э.Дж. (1980), «Соответствующий многочлен и его связь с ациклическим многочленом графа», Ars Combinatoria , 9 : 221–228.
• Годсил, CD (1981), «Многочлены Эрмита и соотношение двойственности для многочленов паросочетаний», Combinatorica , 1 (3): 257–262, doi :10.1007/BF02579331.
• Гутман, Иван (1991), «Многочлены в теории графов», в Бончев, Д.; Руврэ, Д. Х. (ред.), Химическая теория графов: Введение и основы , Математическая химия, т. 1, Тейлор и Фрэнсис, стр. 133–176, ISBN 978-0-85626-454-2.
• Джеррум, Марк (1987), «Двумерные системы мономер-димер не поддаются вычислительной обработке», Журнал статистической физики , 48 (1): 121–134, Bibcode : 1987JSP....48..121J, doi : 10.1007/BF01010403.
• Makowsky, JA; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Вычисление графовых полиномов на графах ограниченной кликовой ширины", Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06) ( PDF) , Lecture Notes in Computer Science, т. 4271, Springer-Verlag, стр. 191–204, doi :10.1007/11917496_18, ISBN 978-3-540-48381-6.
• Риордан, Джон (1958), Введение в комбинаторный анализ , Нью-Йорк: Wiley.
• Заславский, Томас (1981), «Комплементарные векторы соответствия и свойство расширения равномерного соответствия», Европейский журнал комбинаторики , 2 : 91–103, doi : 10.1016/s0195-6698(81)80025-x.