АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

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

Задача. Розфарбувати вершини графа так, щоб будь-які дві суміжні вершини були розфарбовані в різні кольори, при цьому число використаних кольорів повинне бути найменшим. Це число називається хроматичним (кольоровим) числом графа, будемо його позначати  (G) (якщо G – даний граф). Якщо число , то граф називається k-розфарбовуваним.

Функцією Гранди називається функція на вершинах графа, що відображає вершини в множину {1,2,…, a},причому якщо вершина xi пофарбована в кольори з номером k, то функція Гранди h(xi) = k.

Ясно, що для даного графа хроматичне число є єдиним, але функцій Гранди може бути дуже багато. Природно, що знайти хоча б одну функцію Гранди - це значить, знайти одну з можливих “найкращих” розфарбувань (таких розфарбувань може бути багато).

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

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

Перейдемо до опису алгоритму знаходження найкращого розфарбування вершин графа. Нехай маємо граф G, знайдемо в ньому будь-яку МНС, яку позначимо S1, і всі вершини, що входять у цю МНС, пофарбуємо в кольори № 1. Далі, видалимо з даного графа всі вершини, що входять у цю МНС (разом з ребрами), і для нового графа знову знайдемо МНС, що позначимо S2. Ці нові вершини пофарбуємо в кольори № 2, потім видалимо ці вершини із графа разом з відповідними ребрами й знову знаходимо МНС, що пофарбуємо в кольори № 3, і т.д. Можна довести, що при будь-якому способі здійснення цієї процедури прийдемо до найкращого розфарбування й знайдемо деяку функцію Гранди й хроматичне число даного графа.

Приклад. У графа (рис. 3.12, а) є 3 максимально незалежних систем вершин: {5}, {1,3} й {2,4}. Ясно, що при будь-якій процедурі знаходження хроматичного числа в цьому графі, одержимо число 3.

Теорема. Якщо максимальний ступінь вершин у графі дорівнює r, те хроматичне число цього графа не перевершує r + 1. При цьому хроматичне число графа дорівнює r + 1 тільки у двох випадках: по-перше, якщо граф є повним й, по-друге, якщо r = 2 і при цьому даний граф містить контур непарної довжини (такий граф зображений на рис. 3.12, б, максимальний ступінь його вершин – 2, а хроматичне число – 3). У всіх інших випадках хроматичне число графа не перевершує максимального ступеня вершин.

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

Граф називається плоским, якщо він намальований на площині, причому будь-які 2 ребра можуть перетинатися тільки у вершині.

Графи називаються ізоморфними, якщо існує така нумерація вершин у цих графах, що вони мають ту саму матрицю суміжності (фактично ізоморфні графи – це однакові графи, які відрізняються тільки іншим зображенням).

Рисунок 3.12 – Ізоморфні графи

Можна довести, що хроматичне число планарних графів менше або дорівнює 5. Однак Августом де Морганом (1850) була висунута гіпотеза про те, що хроматичне число планарних графів менше або дорівнює 4. Цій проблемі було присвячено величезне число математичних робіт. Зрештою, удалося звести цю проблему до дослідження вірності цієї гіпотези для досить великої кількості типів графів ( 30 тис.), що й було зроблено за допомогою комп'ютерів (1976). Гіпотеза про чотири фарби виявилася справедливою, а сама проблема перейшла в задачу про спрощення доказу гіпотези про чотири фарби.

Відзначимо найвідомішу інтерпретацію проблеми про чотири фарби. Нехай є географічна карта. Чи можна, використовуючи тільки 4 фарби, зобразити цю карту так, щоб сусідні країни (що мають загальну границю) були пофарбовані в різні кольори? Зрозуміло, що у відповідному графі вершинами є країни, а суміжними вершинами є сусідні країни. Ясно, що отриманий граф є планарним, і після 1976 р. відповідь на це питання є позитивною.

Замітимо, що в теорії графів ставиться часто питання про реберне розфарбування графів. Яке мінімальне число кольорів (це число іноді називають реберно-хроматичним) потрібно, щоб розфарбувати ребра графа так, що будь-які 2 суміжні ребра (тобто 2 ребра, що мають загальну вершину) були б пофарбовані в різні кольори? Для реберно-хроматичного числа графа справедлива теорема.

Теорема Візинга. Якщо в графі максимальний ступінь вершин дорівнює r, то реберно-хроматичне число дорівнює або r, або r +1.

Помітимо, що дотепер відсутні уточнення критеріїв для графів, коли ж саме реберно-хроматичне число дорівнює r, а коли r + 1.

Очевидно, що найпростіший алгоритм знаходження реберно-хроматичного числа (і відповідного розфарбування ребер) полягає в наступному: по даному графі будуємо так званий двоїстий граф: ребра графа відповідають вершинам нового (двоїстого) графа, причому, якщо 2 ребра мають загальну вершину, то вони є суміжними й у двоїстому графі з'єднані ребром. Після цього розфарбовуємо щонайкраще вершини двоїстого графа й, переходячи до “старого” графу, одержуємо (одну з можливих) найкращих реберних розфарбувань графів.

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

Дата добавления: 2015-09-27 | Просмотры: 1062 | Нарушение авторских прав