UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 12

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваРозфарбування графів (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось3569
Скачало341
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

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

 

Нехай 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. Для правильного розфарбування довільного кубічного

графа достатньо чотири фарби.

 

Так склалося історично, що окреме місце в теорії графів займають

дослідження з розфарбування планарних графів. Пов’язано це зі славетною

проблемою або гіпотезою чотирьох фарб.

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ