Графовый полином

В математике графовый полином — это инвариант графа , значение которого является полиномом . Инварианты этого типа изучаются в алгебраической теории графов . ^[1] Важные графовые полиномы включают в себя:

• Характеристический многочлен , основанный на матрице смежности графа .
• Хроматический многочлен — многочлен, значения которого при целочисленных аргументах дают количество раскрасок графа этим количеством цветов.
• Дихроматический многочлен , обобщение хроматического многочлена с двумя переменными
• Полином потока — полином, значения которого при целочисленных аргументах дают число потоков, не равных нулю, с целочисленными величинами потока по модулю аргумента.
• (Обратная) дзета-функция Ихара , определяемая как произведение биномиальных членов, соответствующих некоторым замкнутым путям в графе.
• Многочлен Мартина, использованный Пьером Мартеном для изучения циклов Эйлера
• Сопоставительные многочлены — несколько различных многочленов , определяемых как производящая функция соответствий графа.
• Полином надежности — полином, описывающий вероятность сохранения соединения после независимых отказов ребер.
• Полином Тутта — полином от двух переменных, который можно определить (после небольшой замены переменных) как производящую функцию чисел связных компонент индуцированных подграфов данного графа, параметризованную числом вершин в подграфе.

Смотрите также

• Многочлен узла

Ссылки

1. Ши, Юнтан; Демер, Маттиас; Ли, Сюэлян; Гутман, Иван (2016), Графовые полиномы , Дискретная математика и ее приложения, CRC Press, ISBN 9781498755917