Хроматичний індекс

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Проблема реберного розфарбування полягає в тому, щоб виявити чи можливо розфарбовати даний граф використовуючи не більше 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 .

Посилання[ред.ред. код]