Полином графа - Википедия - Graph polynomial

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

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

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

• Узел полином

Рекомендации

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