WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Розфарбування графів - Реферат

Розфарбування графів - Реферат


Реферат на тему:
Розфарбування графів
Нехай G =(V,E ) довільний граф, а Nk={1,2,...,k }.
Будь-яке відображення f :V Nk, яке ставить у відповідність кожній вершині v V деяке натуральне число f (v) Nk, називається розфарбуванням графа G. Число f (v) називається кольором або номером фарби вершини v.
Розфарбування f графа G називається правильним, якщо для будь-яких його суміжних вершин v і w виконується f (v) f (w).
Мінімальне число k, для якого існує правильне розфарбування графа G, називається хроматичним числом графа G і позначається (G ).
Мінімальним правильним розфарбуванням графа G називається правильне розфарбування для k= (G ).
Для певних типів графів визначити хроматичні числа нескладно. Наприклад, 1-хроматичними є порожні графи G =(V, ) і тільки вони. Хроматичне число повного графа Kn дорівнює n, а хроматичне число довільного двочасткового графа 2. 2-хроматичні графи часто називають біхроматичними.
Очевидними є такі твердження.
Лема 3.6. Якщо кожна зв'язна компонента графа G потребує для свого правильного розфарбування не більше k фарб, то (G ) k.
Лема 3.7. Граф є біхроматичний тоді і тільки тоді, коли він двочастковий.
Зокрема, всі дерева і прості цикли парної довжини C2k є біхроматичні. У той же час, (C2k+1)=3.
Використовуючи теорему 3.12, останню лему можна переформулювати у такому вигляді.
Лема 3.8. Граф є біхроматичний тоді і тільки тоді, коли він не має циклів непарної довжини.
Проблема визначення, чи є заданий граф k-хроматичним для певного k, та проблема знаходження мінімального правильного розфарбування для заданого графа належать до класу задач, для яких на сьогодні не існують (і є всі підстави вважати, що не існують взагалі) ефективні точні алгоритми їх розв'язку [2,7,8]. Тому важливими є результати, які дозволяють оцінити значення хроматичного числа (G ), виходячи з певних характеристик та властивостей графа G.
Теорема 3.16. Позначимо через (G ) найбільший зі степенів вершин графа G, тоді (G ) (G )+1.
Доведення проведемо індукцією за кількістю n вершин графа G. Для тривіального графа (n=1) і графів з двома вершинами нерівність виконується.
Нехай твердження теореми виконується для всіх графів з кількістю вершин t (t 2). Розглянемо довільний граф G з t +1 вершиною. Вилучимо з G деяку вершину v, дістанемо граф G , всі степені вершин якого не перевищують (G ). Отже, за припущенням індукції, для правильного розфарбування G потрібно не більше ніж (G )+1 фарба. Правильне розфарбування для G дістанемо з правильного розфарбування графа G , якщо пофарбуємо вершину v у колір, відмінний від кольорів усіх суміжних із v вершин. Оскільки таких вершин не більше, ніж (G ), то для правильного розфарбування графа G достатньо (G )+1 фарба.
Наслідок 3.16.1. Для правильного розфарбування довільного кубічного графа достатньо чотири фарби.
Так склалося історично, що окреме місце в теорії графів займають дослідження з розфарбування планарних графів. Пов'язано це зі славетною проблемою або гіпотезою чотирьох фарб.
Грані плоскої карти назвемо суміжними, якщо їхні межі мають принаймні одне спільне ребро.
Гіпотеза чотирьох фарб виникла у зв'язку з розфарбуванням друкованих географічних карт (звідси й термін "плоска карта") і формулювалась так:
"Грані довільної плоскої карти можна розфарбувати небільше ніж чотирма фарбами так, що будь-які суміжні грані матимуть різні кольори".
Згодом з'явилось інше, рівносильне, формулювання гіпотези чотирьох фарб.
Для правильного розфарбування вершин довільного планарного графа потрібно не більше чотирьох фарб.
Ця гіпотеза виникла в середині ХIХ століття. Більше ста років професійні та непрофесійні дослідники намагалися довести або спростувати цю гіпотезу. В результаті багаторічних досліджень виявилось, що для вирішення проблеми чотирьох фарб необхідно перевірити її справедливість для скінченного числа графів певного виду. Кількість варіантів, які потрібно було перебрати, була настільки великою, що тільки за допомогою потужної ЕОМ, яка неперервно працювала протягом більше двох місяців, у 1976 році справедливість гіпотези чотирьох фарб була підтверджена. Однак такий "фізичний" експериментальний спосіб доведення не зовсім влаштовує багатьох професійних математиків, і вони продовжують пошуки аналітичного доведення гіпотези.
Набагато простіше можна отримати такі результати.
Теорема 3.17. Планарний граф є біхроматичний тоді і тільки тоді, коли степені всіх його граней парні.
Справедливість твердження теореми випливає з того, що в планарному графі, степені всіх граней якого парні, відсутні цикли непарної довжини (доведіть це самостійно). Отже, для нього виконується критерій леми 3.8.
Теорема 3.18. Для правильного розфарбування довільного планарного графа потрібно не більше шести фарб.
Доведення проведемо індукцією за кількістю n вершин планарного графа. Для n 6 твердження очевидне. Припустимо, що хроматичне число всіх планарних графів з t вершинами не перевищує 6 (t 6). Розглянемо довільний планарний граф G з t +1 вершиною. Згідно з наслідком 3.13.3 у графі G існує вершина v, степінь якої не більше 5. Вилучимо вершину v з графа G. Отримаємо граф G , вершини якого за припущенням індукції можна правильно розфарбувати не більше ніж у шість кольорів. Тоді правильне розфарбування для G отримаємо з одержаного правильного розфарбування графа G , надаючи вершині v колір, відмінний від кольорів усіх суміжних з нею вершин. Оскільки таких вершин не більше п'яти, то для виконання цієї процедури шести фарб буде достатньо. Отже, (G ) 6.
Пропонуємо самостійно переконатись у справедливості такого твердження.
Теорема 3.19. Для довільного планарного графа G виконується (G ) 5.
Нарешті, завершимо цю тему зауваженням, що існують планарні графи, хроматичне число яких дорівнює 4. Найпростішим таким графом є K4. Отже, гіпотезу чотирьох фарб не можна "вдосконалити", перетворивши у "гіпотезу трьох фарб".
Різноманітні точні та наближені алгоритми знаходження правильних розфарбувань графів можна знайти в монографії [8].
Список літератури
1. Харари Т. Теория графов.- М.,1973.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.- М., 1990.
3. Зыков А.А. Основы теории графов.- М., 1987.
4. Оре О. Теория графов.- М., 1980.
5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.
6. Уилсон Р. Введение в теорию графов.- М., 1977
7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978
8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980
Loading...

 
 

Цікаве