Skip to main content
LibreTexts - Ukrayinska

5.9: Хроматичний многочлен

  1. Last updated
  2. Save as PDF
  • Page ID
    64341

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Тепер перейдемо до кількості способів розфарбовування графіка\(G\)\(k\) кольорами. Звичайно, якщо\(k< \chi(G)\), це нуль. Ми шукаємо функцію, яка\( P_G(k)\) дає кількість способів фарбування\(G\)\(k\) кольорами. Деякі графіки легко зробити безпосередньо.

    Приклад\(\PageIndex{1}\)

    Якщо\(G\) це\(K_n\)\( P_G(k)=k(k-1)(k-2)\cdots(k-n+1)\), а саме, кількість перестановок\(k\) речей, прийнятих\(n\) за один раз. Вершина 1 може бути забарвлена будь-яким з\(k\) кольорів, вершина 2 будь-яким з решти\(k-1\) кольорів і так далі. Зверніть увагу, що коли\(k< n\),\( P_G(k)=0\). За допомогою вправи 1.E.9.5 в розділі 1.E ми також можемо написати\( P_G(k)=\sum_{i=0}^n s(n,i)k^i\).

    Приклад \(\PageIndex{2}\)

    Якщо\(G\) має\(n\) вершини і немає ребер,\(P_G(k)=k^n\).

    Враховуючи, що\(P_G\) це не важко обчислити\(\chi(G)\); наприклад, ми могли б просто підключити цифри до\(1,2,3,\ldots\) тих пір,\(k\) поки не буде\(P_G(k)\) нульовим. Це говорить про те, що обчислення буде складно (тобто трудомістким)\(P_G\). Ми можемо надати легку механічну процедуру обчислення, досить схожу на алгоритм, який ми представили для обчислень\(\chi(G)\).

    \(G\)Припустимо\(e=\{v,w\}\), є край\(P_{G-e}(k)\), і розглянемо, кількість способів\(G-e\) розфарбовування\(k\) квітами. Деякі з забарвлень також\(G-e\) є розмальовками\(G\), але деякі ні, а саме ті, в яких\(v\) і\(w\) мають однаковий колір. Скільки їх там? З нашого обговорення алгоритму\(\chi(G)\) ми знаємо, що це кількість забарвлень\(G/e\). Таким чином,\[ P_G(k)=P_{G-e}(k)-P_{G/e}(k). \nonumber\] Оскільки\(G-e\) і\(G/e\) обидва мають менше ребер\(G\), ніж, ми можемо обчислити,\(P_G\) застосовуючи цю формулу рекурсивно. Зрештою, нам потрібно обчислити лише\(P_G\) для графіків без країв, що легко, як у прикладі\(\PageIndex{2}\).

    Оскільки\(P_G(k)=k^n\) коли не\(G\) має країв, то легко побачити, і довести шляхом індукції, що\(P_G\) є поліном.

    Теорема \(\PageIndex{1}\)

    Для всіх\(G\) на\(n\) вершині,\(P_G\) є поліном ступеня\(n\), і\(P_G\) називається хроматичним поліном\(G\).

    Доказ

    Доказом є індукція на кількість ребер в\(G\). Коли не\(G\) має ребер, це приклад\(\PageIndex{2}\).

    В іншому випадку, за індукційною гіпотезою,\(P_{G-e}\)\(P_{G/e}\) є поліном ступеня\(n\) і\( P_G=P_{G-e}-P_{G/e}\) є поліномом ступеня\(n-1\), так і поліном ступеня\(n\).

    Хроматичний поліном графа має ряд цікавих і корисних властивостей, деякі з яких досліджуються у вправах.

    Автори та авторства