Формула удаления-сокращения

В теории графов формулой /рекурсией удаления-сокращения является любая формула следующей рекурсивной формы:

f(G)=f(G\setminus e)+f(G/e).

Здесь G — граф, f — функция на графах, e — любое ребро G , G \ e обозначает удаление ребра, а G / e обозначает сжатие . Тутте называет такую функцию W-функцией . ^[1] Эту формулу иногда называют фундаментальной теоремой о приведении . ^[2] В этой статье мы сокращаем DC .

Р.М. Фостер уже заметил, что хроматический полином является одной из таких функций, и Тутте начал открывать больше, включая функцию f = t ( G ), подсчитывающую количество остовных деревьев графа (см. также теорему Кирхгофа ). Позже выяснилось, что полином потока — это еще один; и вскоре Тутте обнаружил целый класс функций, называемых полиномами Тутте (первоначально называвшимися дихроматами ), которые удовлетворяют DC. ^[1]

Примеры

Связующие деревья

Количество связующих деревьев $t(G)$ удовлетворяет ДК. ^[3]

Доказательство. $t(G\setminus e)$ обозначает количество остовных деревьев, не включая e , тогда как $t(G/e)$ число, включая e . Чтобы увидеть второе, если T является остовным деревом G , то сжимание e создает другое остовное дерево G. $G/e$ . дерево T И наоборот, если у нас есть остовное $G/e$ , то расширение ребра e дает два несвязных дерева; добавление e соединяет их и дает связующее дерево G .

Хроматические полиномы

Хроматический полином $\chi _{G}(k)$ подсчет количества k -раскрасок G удовлетворяет не DC, а слегка модифицированной формуле (которую можно сделать эквивалентной): ^[1]

\chi _{G}(k)=\chi _{G-e}(k)-\chi _{G/e}(k).

Доказательство. Если e = uv , то k -раскраска G совпадает с k -раскраской G \ e, где u и v имеют разные цвета. Есть $\chi _{G\setminus e}(k)$ тотальные раскраски G \ e . Теперь нам нужно вычесть те, где u и v окрашены одинаково. Но такие раскраски соответствуют k -раскраскам $\chi _{G/e}(k)$ где u и v объединены.

Это свойство можно использовать, чтобы показать, что хроматический полином $\chi _{G}(k)$ действительно является полиномом от k . Мы можем сделать это с помощью индукции по числу ребер, заметив, что в базовом случае, когда ребер нет, есть $k^{|V(G)|}$ возможные раскраски (которые являются полиномом от k ).

Алгоритм удаления-сокращения

См. также

Цитаты

^ Jump up to: ^а ^б ^с Тутте, WT (январь 2004 г.). «Граф-полиномы» . Достижения прикладной математики . 32 (1–2): 5–9. дои : 10.1016/S0196-8858(03)00041-1 .
^ Донг, Ко и Тео (2005)
^ «Удаление-сжатие и хроматические полиномы» (PDF) . Архивировано из оригинала (PDF) 4 мая 2019 года.

Цитируемые работы

Донг, FM; Кох, КМ; Тео, КЛ (июнь 2005 г.). Хроматические полиномы и цветность графов . Всемирная научная. дои : 10.1142/5814 . ISBN 978-981-256-317-0 .

[:0-1] Jump up to: ^а ^б ^с Тутте, WT (январь 2004 г.). «Граф-полиномы» . Достижения прикладной математики . 32 (1–2): 5–9. дои : 10.1016/S0196-8858(03)00041-1 .

[2] Донг, Ко и Тео (2005)

[3] «Удаление-сжатие и хроматические полиномы» (PDF) . Архивировано из оригинала (PDF) 4 мая 2019 года.

[1]

[2]

[3]