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

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

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

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

Индекс статей, связанных с тем же именем

Эта статья индекса набора включает список связанных элементов, которые имеют одно и то же имя (или похожие имена).
Если внутренняя ссылка неправильно привела вас сюда, вы можете изменить ссылку, чтобы она указывала прямо на нужную статью.