14.3: Фарбування вершин

Last updated
Save as PDF

Page ID: 64741

Joy Morris
University of Lethbridge

$ \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}}$

Припустимо, вам було поставлено завдання привласнити частоти мовлення вежам передачі. Вам надано список частот, які вам дозволено призначати. Є обмеження: вежі, які знаходяться занадто близько один до одного, не можна призначати однакову частоту, так як вони будуть заважати один одному.

Один із способів підходу до цієї проблеми - змоделювати її як графік. Вершини графа будуть представляти вежі, а ребра - вежі, які можуть заважати один одному. Ваше завдання полягає в тому, щоб призначити частоту кожній з вершин. Замість того, щоб писати частоту на кожній вершині, ми виберемо колір для представлення цієї частоти, і використаємо цей колір для фарбування вершин, яким ви призначаєте цю частоту.

Ось такий приклад.

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

Цей графік представляє вежі та їх інтерференційні схеми.

$clipboard_e8d83cbeaf0952764c72eb7a53422df4e.png$

Це являє собою можливе призначення$4$ кольорів вершинам. Колір кожної вершини (червоний, зелений, синій або жовтий) позначається написанням першої літери назви кольору на вершині).

$clipboard_eeb77390fd8f60f767aa564d4f7a2f92d.png$

Зверніть увагу, що ця забарвлення підпорядковується обмеженню, що перешкоджають вежам не призначаються однакові частоти.

Визначення: Правильне$k$-Vertex-Colouring

Правильне$k$ -vertex-coloring (або просто$k$ -coloring) графа$G$ - це функція, яка призначає кожній вершині$G$ одного з$k$ кольорів, так що сусідні вершини повинні бути призначені різні кольори.

Як і при фарбуванні країв, обмеження, що сусідні вершини отримують різні кольори, виявляється корисним обмеженням, яке виникає в багатьох контекстах. Ми часто представляємо$k$ кольори цифрами і$1, . . . , k$ позначаємо вершини відповідними цифрами, а не розфарбовуємо їх.

Визначення:$k$-Colourable

Графік$G$ є$k$ -colourable, якщо він допускає належне$k$ - (вершина-) забарвлення. Найменше ціле число,$k$ для$G$ якого$k$ -colourable називається хроматичним числом$G$.

Позначення

Хроматичне число$G$ позначається або просто тим$χ(G)$,$χ$ якщо контекст однозначний.

Ми залишаємо доказ наступного як вправу (див. Вправа 14.3.1 (2)).

Пропозиція$\PageIndex{1}$

Для кожного$n ≥ 1$,$χ(K_n) = n$.

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

Доведіть, що для графіка$G$,$χ(G) = 2$ якщо і тільки якщо$G$ це двосторонній граф, який має принаймні одне ребро.

Рішення

$(⇒)$Припустимо, що$χ(G) = 2$. Візьміть належне$2$ фарбування$G$ з кольорами$1$ і$2$. Нехай$V_1$ позначають набір вершин кольору$1$, і нехай$V_2$ позначають набір вершин кольору$2$. Оскільки забарвлення є правильним, немає ребер, обидві кінцеві вершини яких знаходяться в$V_1$ (оскільки це будуть сусідні вершини, обидві пофарбовані кольором$1$). Аналогічно, немає ребер, обидві кінцеві вершини яких знаходяться в$V_2$. Таким чином,$V_1$ множини і$V_2$ утворюють двосекційні$G$,$G$ так і двосторонні. Оскільки$2$ кольори повинні були правильно$G$ фарбуватися$G$, повинен мати принаймні один край.

$(⇐)$Припустимо, що$G$ є двостороннім,$V_1$ і що і$V_2$ утворюють двосекцію$G$. Пофарбуйте вершини$V_1$ кольором$1$ і розфарбуйте вершини$V_2$ кольором$2$. За визначенням bipartition жодна пара сусідніх вершин не може бути присвоєна однакового кольору. Таким чином, це правильне$2$ фарбування$G$, так що$χ(G) ≤ 2$. Оскільки$G$ має принаймні одне ребро, кінцеві точки цього краю повинні бути призначені різні кольори, тому$χ(G) ≥ 2$. Таким чином$χ(G) = 2$.

Приклад$\PageIndex{3}$

Покажіть, що для будь-якого$n ≥ 1$,$χ(C_{2n+1}) = 3$.

Рішення

Оскільки цей граф має ребро, кінцеві вершини якого повинні бути призначені різні кольори, ми бачимо це$χ(C_{2n+1}) ≥ 2$. Оскільки цикл непарної довжини не є двороздільним (див. Теорему 14.1.2), Приклад 14.3.2 показує$χ(C_{2n+1}) \neq 2$, що, так$χ(C_{2n+1}) ≥ 3$. Нехай цикл буде$(u_1, u_2, . . . , u_{2n+1}, u_1)$. Оскільки єдині ребра на графіку знаходяться між послідовними вершинами у цьому списку, якщо ми призначимо колір$u_1$$1 ≤ i ≤ n$, колір$2$$u_{2i}$ для та колір$3$$u_{2i+1}$ для for$1 ≤ i ≤ n$, це буде правильне$3$ -coloring.$1$ Таким чином,$χ(C_{2n+1}) = 3$.

Визначення:$k$-Critical

$G$Графік k-критичний$χ(G) = k$, якщо, але для кожного належного підграфа$H$$G$,$χ(H) < χ(G)$.

Пропозиція$\PageIndex{2}$

Будь-який$k$ -критичний графік пов'язаний.

Доказ

До протиріччя, припустимо, що$G$ це відключений$k$ -критичний граф,$G_1$ і нехай і$G_2$ бути (непорожніми) підграфами$G$ такого, що кожна вершина$G$ знаходиться в будь-якому$G_1$ або$G_2$, і немає ребра від будь-якої вершини$G_1$ до будь-якої вершина в$G_2$. За визначенням$k$ -критичний,$χ(G_1) < χ(G)$ і$χ(G_2) < χ(G)$. Але якщо ми$G_1$$χ(G_1)$ фарбуємо$G_2$$χ(G_2)$ кольорами та кольорами, оскільки немає краю від будь-якої вершини$G_1$ до будь-якої вершини$G_2$, це створює належне забарвлення$G$ з

\[\max(χ(G_1), χ(G_2)) < χ(G)\]

кольори. Це протиріччя служить для того, щоб довести, що кожен$k$ -критичний граф пов'язаний.

Теорема$\PageIndex{1}$

Якщо$G$$k$ -критично, то$δ(G) ≥ k − 1$.

Доказ: До протиріччя припустимо, що$G$ є$k$ -критичним і має$v$ максимум вершину валентності$k −2$. За визначенням$k$ -критичний,$G \setminus \{v\}$ повинен бути$(k −1)$ -кольоровим. Тепер, оскільки$v$ має не більше, ніж$k − 2$ сусідів, його сусідам можна призначити найбільш$k − 2$ різні кольори в цьому забарвленні. Тому серед кольорів, що використовуються в$(k − 1)$ -coloring$G \setminus \{v\}$, повинен бути колір, який не присвоюється жодному з сусідів$v$. Якщо призначити цей колір$v$, то в результаті буде правильне$(k − 1)$ -фарбування$G$, що суперечить$χ(G) = k$. Це протиріччя служить для того, щоб довести, що кожен$k$ -критичний граф має принаймні мінімальну валентність$k − 1$.

Слідство$\PageIndex{1}$

Для будь-якого графіка$G$,$χ(G) ≤ ∆(G) + 1$.

Доказ

$G$Дозволяти довільний графік. Видаляючи стільки ребер і вершин, скільки можна видалити, не зменшуючи хроматичне число (ми ніколи не можемо збільшити хроматичне число, видаляючи вершини або ребра, див. Вправа 14.3.1 (1)), ми бачимо, що$G$ повинен мати підграф,$H$ який є$χ(G)$ критичним. За теоремою 14.3.1 ми бачимо, що

\[δ(H) ≥ χ(G) − 1.\]

Таким чином, кожна вершина$H$ має валентність принаймні$χ(G) − 1$, так що в$G$, ці ж вершини все ще мають валентність принаймні$χ(G) − 1$. Для будь-якої такої вершини$v$ у нас є

\[∆(G) ≥ d(v) ≥ χ(G) − 1,\]

так$χ(G) ≤ ∆(G) + 1$.

Ми вже бачили дві сім'ї графіків, для яких досягається ця межа: для повних графіків ми маємо

\[∆(K_n) + 1 = (n − 1) + 1 = n = χ(K_n)\]

(див. Пропозиція 14.3.1); а для циклів непарної довжини ми маємо

\[∆(C_{2n+1}) + 1 = 2 + 1 = 3 = χ(C_{2n+1})\]

(див. Приклад 14.3.3). Насправді Брукс довів в 1941 році, що це єдині пов'язані графіки, за якими отримана ця межа.

Теорема$\PageIndex{2}$: Brook's Theorem

Якщо$G$ підключається і на кожен$n ≥ 1$,$G \ncong C_{2n+1}$ і$G \ncong K_n$, то$χ(G) ≤ ∆(G)$.

Доказ: Ми не будемо включати докази цього результату в цей курс. Ця теорема дозволяє визначити хроматичне число деяких графіків з дуже невеликою роботою.

Приклад$\PageIndex{4}$

Наступний дуже відомий граф називається графом Петерсена. Це винятковий графік у багатьох відношеннях, тому, коли математики намагаються придумати доказ або контрприклад у теорії графів, це часто є одним із перших прикладів, які вони перевірять. Знайдіть його хроматичне число.

$clipboard_ec0db06837b987f121c2d381120de1ad0.png$

Рішення

Ми маємо$∆ = 3$, і оскільки цей графік не є ні повним графіком, ні циклом непарної довжини, за теоремою Брукса це показує, що$χ ≤ 3$. Ми можемо знайти цикл довжини$5$ навколо зовнішнього краю графіка, тому цей графік не є двостороннім, але має ребро. Тому (на прикладі 14.3.2),$χ > 2$. Звідси$χ = 3$.

Вправа$\PageIndex{1}$

1) Доведіть, що якщо$H$ є підграфом$G$ тоді$χ(G) ≥ χ(H)$.

2) Доведіть пропозицію 14.3.1 шляхом індукції.

3) Доведіть слідство 14.3.1 шляхом індукції для кожного графа принаймні на одній вершині.

4) Для кожного$i$, припустимо$j ∈ \{4, 5, 6\}$, вам дано графік,$G$ який містить підграф ізоморфний до,$K_i$ і жодна вершина не має більше, ніж$j$ сусіди. Про що (якщо що) можна сказати$χ(G)$? Чи можете ви сказати більше, якщо знаєте, що$G$ пов'язано і не є ні повним графіком, ні циклом непарної довжини?

Вправа$\PageIndex{2}$

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

1) $clipboard_ebb943566c31d45fb179a3e11db027e16.png$