Многочлен Татта — различия между версиями
(→Основное определение) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 28: | Строка 28: | ||
{{Определение|definition= | {{Определение|definition= | ||
− | '''Ранговый многочлен''' '' | + | '''Ранговый многочлен''' (англ. ''Rank polynomial'') графа <tex> G </tex> есть многочлен от двух переменных, определяемый формулой: <br> |
<center><tex dpi = "140"> R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} </tex> </center> | <center><tex dpi = "140"> R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} </tex> </center> | ||
}} | }} | ||
Строка 94: | Строка 94: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Обозначим за <tex> S_n </tex> множество остовных деревьев <tex> T </tex> графа <tex> G </tex>. Будем говорить, что ребро <tex> p \in T</tex> '''внутренне активно''' (internally active) в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash t </tex>, таких что <tex> T \backslash p \cup {q} \in S_n</tex>. Аналогичным образом, будем говорить, что ребро <tex> p \in T</tex> '''внешне активно''' (externally active) в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash T </tex>, таких что <tex> T \backslash q \cup {p} \in S_n</tex>. Величиной внутренней (внешней) активности будем называть число внутренне (внешне) активных элементов в <tex> T </tex>; эти величины будем обозначать <tex> i(T) </tex> и <tex> e(T) </tex> соответственно. | + | Обозначим за <tex> S_n </tex> множество остовных деревьев <tex> T </tex> графа <tex> G </tex>. Будем говорить, что ребро <tex> p \in T</tex> '''внутренне активно''' (англ. ''internally active'') в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash t </tex>, таких что <tex> T \backslash p \cup {q} \in S_n</tex>. Аналогичным образом, будем говорить, что ребро <tex> p \in T</tex> '''внешне активно''' (англ. ''externally active'') в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash T </tex>, таких что <tex> T \backslash q \cup {p} \in S_n</tex>. Величиной внутренней (внешней) активности будем называть число внутренне (внешне) активных элементов в <tex> T </tex>; эти величины будем обозначать <tex> i(T) </tex> и <tex> e(T) </tex> соответственно. |
}} | }} | ||
Текущая версия на 19:17, 4 сентября 2022
Многочлен Татта — наиболее общая характеристика, описывающая комбинаторные свойства графа.
Основное определение
Определение: |
Рассмотрим граф
| , возможно c петлями и кратными рёбрами. Определим многочлен Татта (англ. Tutte polynomial) следующими рекурсивными соотношениями:
Из этого определения не очевидна корректность: почему полученная функция не зависит от порядка выкидывания рёбер? Однако, если определение корректно, , очевидно, является многочленом от двух переменных с целыми неотрицательными коэффициентами. Корректность мы докажем, связав многочлен Татта с другим многочленом — ранговым многочленом Уитни (Whitney rank polynomial).
Корректность определения, связь с ранговым многочленом
Определение: |
Пусть | — некоторый граф. Для множества через будем обозначать граф . Через будем обозначать число компонент связности графа . Рангом множества будем называть число .
Утверждение: |
Ранг множества равен количеству рёбер в любом остовном лесе графа . (под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф , что и ) |
Действительно, в каждой компоненте связности остовного леса рёбер на одно меньше чем вершин, а общее число вершин равно | .
Теперь определим сам ранговый многочлен:
Определение: |
Ранговый многочлен (англ. Rank polynomial) графа | есть многочлен от двух переменных, определяемый формулой:
Показатели в формуле раногового многочлена тоже имеют некоторый смысл. Величина равна , т.е. приросту числа компонент связности за счёт перехода к множеству рёбер . Мы будем обозначать эту величину через и называть числом важных для рёбер. (Их важно добавить к , чтобы получилось столько же компонент связности, сколько было изначально).
Величину будем называть числом лишних ребёр: именно столько рёбер можно выкинуть из множества , не меняя число компонент связности. Обозначать эту величину будем через .
Далее докажем следующую техническую лемму:
Лемма: |
Пусть фиксировано некоторое ребро и множество . Обозначим через ранги множества в графе , а через — ранги в графе . Тогда для множества выполняются следующие соотношения:
|
Доказательство: |
|
Теперь, собственно, докажем связь многочлена Татта с ранговым, откуда будет следовать корректность определения для многочлена Татта:
Теорема (Татта): |
Для любого графа выполнено равенство |
Доказательство: |
Если граф Далее, разберём несколько случаев:
|
Многочлен Татта дерева
Пусть
— дерево c вершинами. Тогда . Этот факт можно легко показать по индукции: в дереве любое ребро является мостом, после стягивания которого получается опять дерево с вершинами.Многочлен Татта цикла
Многочлен Татта полного графа
Определение: |
Пусть | , причём . Определим лексикографический порядок на множестве рёбер следующим образом: , если или .
Определение: |
Обозначим за | множество остовных деревьев графа . Будем говорить, что ребро внутренне активно (англ. internally active) в , если для всех , таких что . Аналогичным образом, будем говорить, что ребро внешне активно (англ. externally active) в , если для всех , таких что . Величиной внутренней (внешней) активности будем называть число внутренне (внешне) активных элементов в ; эти величины будем обозначать и соответственно.
Также приведём без доказательства теорему, которая связывает многочлен Татта и понятие остовного дерева:
Теорема (Татта): |
Пусть на с множеством остовных деревьев . Тогда |
Обозначение: Для простоты обозначим многочлен Татта для полного графа
за . Тогда имеет место следующая теорема:Теорема (Многочлен Татта полного графа): |
Доказательство: |
Зафиксируем остовное дерево . Рассмотрим ребро , которое разбивает на поддеревья и , и при этом вершина 0 лежит в . Пусть . Тогда докажем следующие два утверждения:
Понятно, что ребро Теперь необходимое тождество для полинома Татта полного графа может быть получено при подстановке равенств (1) и (2) в и суммировании по всем парам поддеревьев и всем рёбрам типа . |
Универсальное свойство многочлена Татта
Теорема: |
Пусть числовая функция на графах обладает следующими свойствами для некоторых констант :
|
Доказательство: |
Для доказательства проведём индукцию по количеству рёбер. Поскольку для пустого графа Пусть Пусть Пусть |
Связь с хроматическим многочленом
Теорема: |
Для графа и выполняется соотношение . |
Доказательство: |
Воспользуемся универсальным свойством многочлена Татта для функции |
Значения многочлена Татта
Теорема: |
Для любого графа верно, что:
|
Доказательство: |
Заметим, что
|