Оглавление
Многочлен Татта
-
Определение и свойства многочлена Татта
- Многочлен Татта — это многочлен, который описывает количество раскрасок графа.
- Он был введен в 1966 году и назван в честь математика Р. Х. Татта.
- Многочлен Татта тесно связан с хроматическим многочленом и другими важными математическими объектами.
-
Связь с другими математическими объектами
- Многочлен Татта связан с хроматическим многочленом, который описывает количество раскрасок вершин графа.
- Он также связан с многочленом Джонса, который описывает количество раскрасок ребер графа.
-
Теоремы и алгоритмы
- Теорема Татта утверждает, что многочлен Татта является многочленом от двух переменных, который описывает количество раскрасок графа.
- Алгоритм удаления-сокращения позволяет эффективно вычислять многочлен Татта для связных графов.
- Существуют также алгоритмы, которые используют исключение Гаусса для вычисления многочлена Татта в некоторых ограниченных случаях.
-
Вычислительная сложность и приложения
- Вычисление многочлена Татта является #P-сложной задачей, даже для плоских графов.
- Многочлен Татта используется для решения задач, связанных с раскраской графов и статистическими суммами моделей Изинга.
-
Примеры и частные случаи
- Многочлен Татта имеет различные частные случаи, включая вычисление статистической суммы модели Изинга и многочлена Джонса.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.
Полный текст статьи: