Розфарбовування ребер

Розфарбовування ребер — в теорії графів, це присвоєння кольорів ребрам графа, при якому не існує суміжних ребер однакового кольору. Таке розфарбування графа називають правильним розфарбуванням.

Триколірне (червоній, синій, зелений) розфарбування ребер на прикладі графа Дезарга

Проблема розфарбовування ребер полягає в з'ясуванні, чи можливо розфарбувати даний граф використовуючи не більше $n$ кольорів. Мінімально потрібна кількість кольорів для правильного розфарбування даного графа називається хроматичним індексом графа. Наприклад, граф праворуч може бути розфарбований трьома кольорами, але двох буде замало (існуватимуть суміжні ребра однакового кольору). Таким чином, його хроматичний індекс дорівнює три.

Історія

Вперше поняття було застосовано відносно планарних графів. В процесі розфарбовування округів Англії на карті, математик Френсіс Гатрі сформулював проблему чотирьох фарб, зазначивши, що чотирьох кольорів достатньо для розфарбування, в якому будь-які два суміжних регіони були різних кольорів. Його брат переповів проблему своєму вчителю математики, Ауґустусу де Моргану, котрий, в свою чергу, згадав про неї у листі до Вільяма Гамільтона в 1852 році. Артур Келі піднімав цю проблему на зустрічі Лондонського математичного товариства в 1878 році. У тому ж році Пітер Тейт першим запропонував вирішення цієї проблеми. Розфарбовування вершин первісного графа він звів до розфарбування ребер двоїстого графа і припустив, що задача завжди має рішення. У 1880 році Альфред Кемпе опублікував статтю, в якій стверджував, що йому вдалося вирішити проблему і на десятиліття проблема чотирьох кольорів вважалася вирішеною. За це досягнення Кемпе був обраний членом Лондонського Королівського товариства, а пізніше — президентом Лондонського математичного товариства.

У 1890 році Джон Хівуд знайшов помилку в доведенні Кемпе. У цій же статті він довів теорему п'яти фарб, показавши, що будь-яка плоска карта може бути розфарбована не більше, ніж п'ятьма кольорами. При цьому він опирався на ідеї Кемпе. У наступному столітті було розроблено велику кількість теорій намагаючись зменшити мінімальну кількість кольорів. Теорема чотирьох фарб була остаточно доведена в 1977 році вченими Кеннетом Аппелем і Вольфгангом Гакеном. Ідея доведення багато в чому опиралася на ідеї Гівуда і Кемпе, оминувши увагою більшість проміжних досліджень. Доведення теореми чотирьох кольорів є одним з перших, де був використаний комп'ютерний перебір.

У 1912 році Джордж Девід Біркгоф запропонував для вивчення проблем розфарбовування використовувати хроматичний многочлен, який пізніше було узагальнено многочленом Татта. Кемпе в 1879 році вже звертав увагу на загальний випадок, коли граф не є планарним. Багато результатів з узагальненнями розфарбування планарних графів на поверхні вищих порядків з'явилося на початку 20 століття.

У 1960 році Клод Берж, під впливом поняття нульової помилки ємності графа, представленого Клодом Шенноном, сформулював гіпотезу про досконалі графи. Вона залишалась непідтвердженою протягом 40 років, поки зрештою її не довели математики Марія Чудновська, Робертсон, Сеймур і Томас у 2002 році.

Розфарбовування графа як алгоритмічну проблему почали вивчати з 1970-х років: визначення хроматичного числа — одна з 21 NP-повних задач Карпа (1972). Приблизно в той же час були розроблені різноманітні алгоритми на базі пошуку з поверненням та рекурсивного видалення-стиснення Зикова. З 1981 року розфарбовування графа застосовується для розподілу регістрів у компіляторах.

Визначення

В подальшому, кажучи реберне розфарбування графа без додаткових зауважень, ми маємо на увазі правильне розфарбування ребер, яке заперечує існування двох суміжних ребер однакового кольору. Правильне розфарбування з використанням k кольорів — (правильне) реберне k-розфарбування і є еквівалентом проблеми множини ребер на k підмножин. A реберне 3-розфарбування кубічного графа іноді називають розфарбуванням Тейта.

Найменша кількість кольорів необхідна для реберного розфарбування графа G називається хроматичним індексом, або реберним хроматичним числом, χ′(G), також іноді $\chi _{1}(G)$. Граф є реберно k-хроматичним якщо його хроматичний індекс дорівнює k. Не треба плутати хроматичний індекс із хроматичним числом χ(G).

Властивості

В подальшому, хай Δ(G) позначає максимальну ступінь; і μ(G), складність (буде більше 1 тільки для мультиграфів). Деякі властивості χ′(G):

1. χ′(G) = 1 тоді і тільки тоді, якщо G є незалежною множиною ребер.
2. χ′(G) ≥ Δ(G).
3. χ′(G) ≤ Δ(G) + 1. (Теорема Візінга, названа на честь Вадима Візінга який винайшов її в 1964, розділив всі графи на 2 класи: Клас 1 графи із χ′(G) = Δ(G); Клас 2 графи із χ′(G) = Δ(G)+1).
4. χ′(G) ≤ Δ(G) + μ(G), де G може бути мультиграфом.
5. χ′(G) ≤ (3/2)Δ(G) для будь-якого мультиграфа Shannon (1949).
6. χ′(G) = Δ(G) якщо G дводольний граф. # χ′(G) = Δ(G) якщо G простий, планарний та Δ(G) ≥ 7. (Vizing (1965) combined with Sanders & Zhao (2001))
7. χ′(G) = Δ(G) для майже всіх графів Erdős & Wilson (1977).

Класифікація графів і знаходження їх хроматичного індексу

Як ми можемо бачити з наведеного вище χ′(G) дорівнює або either Δ(G), або Δ(G) + 1. Коли χ′(G) = Δ(G), G належить Класу 1; інакше, Класу 2. Holyer (1981) довів, що визначення належності простого графа до конкретного класу NP-повна задача. Однак, можна спробувати дати часткову характеристику. Наприклад, Vizing (1965) показав, що простий, планарний граф знаходиться в Класі 1 якщо його максимальна ступінь не менше 8. І навпаки, він помітив, що для максимального ступеня 2, 3, 4, і 5, існують прості графи з Класу 2. Наприклад, якщо почати з правильного багатогранника і заміняти кожне ребро на шлях з двох суміжних ребер, отримаємо простий планарний граф класу 2 із максимальним ступенем 3, 4, або 5. (Кожний цикл непарної кількості вершин є графом класу 2 з максимальним ступенем 2.) Візінг припустив наступні результати для двох випадків, які він не зміг розв'язати:

Всі прості, планарні графи з максимальним ступенем 6 або 7 належать класу 1 Vizing (1965).

Sanders & Zhao (2001) частково довели це припущення Візінга. Вони показали, що всі прості планарні графи з максимальним ступенем 7 належать класу 1. Таким чином нерозв'язаним залишився випадок для простого планарного графа з максимальним ступенем 6.

Застосування

Планування

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

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

Розподіл регістрів

Компілятор — це комп'ютерна програма яка переводить один комп'ютерний мову в іншій. Для поліпшення часу виконання результуючого коду, однією з технік компіляторної оптимізації, є розподіл регістрів, в якій найбільш часто використовувані змінні модульна програми зберігаються в швидкодійних регістрах процесора. В ідеальному випадку, змінні зберігаються в регістрах так, що вони всі знаходяться в регістрах під час їх використання.

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

Цифрові водяні знаки

Технологія цифрових водяних знаків дозволяє разом з даними (будь то медіафайли, виконувані файли та інші) передати якесь приховане повідомлення («водяний знак»). Таке приховане повідомлення може бути застосоване у захисті авторських прав для ідентифікації власника даних.

Це важливо, наприклад, для встановлення джерела їх розповсюдження нелегальним чином. Або ж для підтвердження прав на дані, наприклад — програмне забезпечення систем на кристалі.

Повідомлення можна закодувати в тому числі і в графі. Одну з таких технік запропонували Qu і Potkonjak (тому її іноді називають QP-алгоритмом) в.

Складається вона ось у чому: припустимо, у нас є граф $G$, розфарбування якого використовується в програмі — причому, використовується так, що припустимо поміняти вміст графа з невеликим збільшенням його хроматичного числа. Що важливо, одним з таких прикладів є граф несумісності (інтерференційний граф) розподілу регістрів процесора, про який говорилося вище, — а значить, ми зможемо закодувати послання в програмному продукті за допомогою розподілу регістрів.

Витягти його можна шляхом порівняння отриманого графа з вихідним; існують і способи упевнитися в тому, чи було якесь повідомлення закодовано в графі без використання вихідного — докладніше витяг описано, наприклад, в.

Розвиток і уточнення думок і, спроби поліпшення алгоритму відбувається в роботах,,.

Інші застосування

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

Розв'язування головоломки судоку можна розглядати як завершення розфарбовування 9 кольорами заданого графа з 81 вершиною.

Див. також

• Критичний граф
• Однозначно розфарбовуваний граф
• Повне розфарбування
• Розфарбовування графів
• Теорема де Брейна — Ердеша (теорія графів)
• Хроматичне число

Примітки

• Erdős, Paul; Wilson, Robin J. (1977), Note on the chromatic index of almost all graphs, Journal of Combinatorial Theory, Series B, 23: 255—257, doi:10.1016/0095-8956(77)90039-9.
• Holyer, Ian (1981), The NP-completeness of edge-coloring, SIAM Journal on Computing, 10: 718—720, doi:10.1137/0210055.
• Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, New York: Wiley-Interscience, ISBN 0-471-02865-7.
• Kőnig, D. (1916), Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, 77: 453—465, doi:10.1007/BF01456961.
• Sanders, Daniel P.; Zhao, Yue (2001), Planar graphs of maximum degree seven are class I, Journal of Combinatorial Theory, Series B, 83 (2): 201—212, doi:10.1006/jctb.2001.2047.
• Shannon, Claude E. (1949), A theorem on coloring the lines of a network, J. Math. Physics, 28: 148—151.
• Vizing, V. G. (1964), On an estimate of the chromatic class of a p-graph, Diskret. Analiz., 3: 25—30.
• Vizing, V. G. (1965), Critical graphs with given chromatic class, Metody Diskret. Analiz., 5: 9—17.

Посилання

• Доведення теореми Візінга [Архівовано 25 серпня 2002 у Wayback Machine.]
• Реберне розфарбування та хроматичний індекс [Архівовано 2 квітня 2015 у Wayback Machine.]
• Проблема чотирьох фарб [Архівовано 14 листопада 2014 у Wayback Machine.]
• Розфарбування п'ятьма фарбами [Архівовано 2 квітня 2015 у Wayback Machine.]