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

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

Определение

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

Один совпадающий полином G — это

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

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

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

Третье определение - это полином

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

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

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

и

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

Соединения с другими полиномами

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

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

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

Если G — полный граф Kn _: , то ( _MG x ) — полином Эрмита

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

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

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

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

Дополнение

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

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

Приложения в химической информатике

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

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

Вычислительная сложность

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

Ссылки

• Курсель, Б. ; Маковский, Дж. А.; Ротикс, У. (2001), «О сложности задач перечисления графов с фиксированным параметром, определяемых в монадической логике второго порядка» (PDF) , Discrete Applied Mathematics , 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), «Двумерные системы мономер-димер вычислительно неразрешимы», Journal of Statistical Physics , 48 ​​(1): 121–134, Bibcode : 1987JSP....48..121J , doi : 10.1007/ БФ01010403 .
• Маковский, Дж. А.; Ротикс, Уди; Авербуш, Илья; Годлин, Бенни (2006), «Вычисление полиномов графа на графах ограниченной ширины клики», Proc. 32-й международный семинар по теоретико-графовым концепциям в информатике (WG '06) (PDF) , Конспекты лекций по информатике, том. 4271, Springer-Verlag, стр. 191–204, номер документа : 10.1007/11917496_18 , ISBN.  978-3-540-48381-6 .
• Риордан, Джон (1958), Введение в комбинаторный анализ , Нью-Йорк: Wiley .
• Заславский, Томас (1981), «Дополнительные векторы соответствия и свойство равномерного расширения соответствия», Европейский журнал комбинаторики , 2 : 91–103, doi : 10.1016/s0195-6698(81)80025-x .