gn="justify"> Будь-яке відображення f: V ® Nk, Пожалуйста ставити біля відповідність Кожній вершіні v V деяке натуральне число f (v) Nk, назівається розфарбування графа G. Число f (v) назівається Кольорах або номером фарби вершини v.
розфарбування f графа G назівається правильним, если для будь-якіх его суміжніх вершин v и w віконується f (v) f (w).
Мінімальне число k, для которого існує правильне розфарбування графа G, назівається хроматична числом графа G и позначається Xp (G).
Мінімальнім правильно розфарбування графа G назівається правильне розфарбування для k=Xp (G).
Для питань комерційної торгівлі тіпів графів візначіті хроматічні числа недоладно. Например, 1-хроматична є порожні графи G=(V,?) I только смороду. Хроматична число полного графа Kn дорівнює n, а хроматична число довільного двочасткового графа - 2. 2-хроматічні графи часто назівають біхроматічнімі.
очевидним є такі тверджень.
Лема. Если Кожна зв відаю компонента графа G потребує для свого правильного розфарбування НЕ более k фарб, то c (G)? k.
Лема. Граф є біхроматічній тоді и только тоді, коли ВІН двочастковій.
Зокрема, всі дерева и Прості цикли парної Довжина C2k є біхроматічні. У тієї ж годину, c (C2k + 1)=3.
Вікорістовуючі теорему Кеніга, громовідвід лему можна переформулюваті у такому виде.
Лема. Граф є біхроматічній тоді и только тоді, коли ВІН НЕ має ціклів непарної Довжину.
Проблема визначення, чи є завдань граф k-хроматична для Певного k, та проблема знаходження мінімального правильного розфарбування для заданого графа належати до класу задач, для якіх на сегодня НЕ існують (і є всі Підстави вважаті, что НЕ існують Взагалі) ефектівні точні алгоритми їх розв язку. Тому Важлива є результати, Які дозволяють оцініті значення хроматична числа c (G), віходячі з питань комерційної торгівлі характеристик та властівостей графа G.
Теорема. Позначімо через D (G) Найбільший зі степенів вершин графа G, тоді c (G)? D (G) +1.
Доведення Проведемо індукцією за кількістю n вершин графа G. Для трівіального графа (n=1) i графів з двома вершинами нерівність віконується.
Нехай тверджень теореми віконується для всіх графів з кількістю вершин t (t? 2). Розглянемо довільній граф G з t +1 вершиною. Вілучімо з G Деяк вершину v, дістанемо граф G? , Всі степені вершин которого НЕ перевіщують D (G). Отже, за припущені індукції, для правильного розфарбування G? нужно НЕ более чем D (G) +1 фарба. Правильне розфарбування для G дістанемо з правильного розфарбування графа G? , Если пофарбуємо вершину v у колір, відмінний від кольорів усіх суміжніх Із v вершин. Оскількі таких вершин не более, чем D (G), то для правильного розфарбування графа G достаточно D (G) +1 фарба.
Наслідок. Для правильного розфарбування довільного кубічного графа достаточно Чотири фарби.
Так склалось Історично, что окреме місце в Теорії графів займають дослідження з розфарбування планарних графів. Пов язано це зі славетним проблемою.Більше або гіпотезою чотірьох фарб.
Грані плоскої карти назвемо суміжнімі, если їхні Межі мают прінаймні Одне СПІЛЬНЕ ребро.
Гіпотеза чотірьох фарб вінікла у зв язку з розфарбування друкованне географічних карт (звідсі ї Термін плоска карта ) и формулювалась так:
Грані довільної плоскої карті можна розфарбуваті НЕ более чем чотірма фарбами так, что будь-які суміжні Грані матімуть Різні кольори .
Згідно з стало інше, рівносільне, формулювання гіпотезі чотірьох фарб.
Для правильного розфарбування вершин довільного планарного графа нужно НЕ более чотірьох фарб.
Ця гіпотеза вінікла в середіні ХIХ століття. Більше ста років Професійні та непрофесійні досліднікі намагаліся довести або спростуваті Цю гіпотезу. У результате багаторічних ДОСЛІДЖЕНЬ віявілось, что для вирішенню проблеми чотірьох фарб та патенти перевіріті ее справедливість для скінченного числа графів Певного увазі. Кількість варіантів, Які нужно Було перебраті, булу настолько великою, что только с помощью потужної ЕОМ, яка неперервно працювала течение более двох місяців, у тисяча дев'ятсот сімдесят шість году справедливість гіпотезі чотірьох фарб булу підтверджена. Однако такий фізичний експериментальний способ доведення НЕ зовсім влаштовує багатьох ПРОФЕСІЙНИХ математіків, и смороду продолжают Пошуки аналітичного доведення гіпотезі.
Зауважімо, что існують планарні графи, хроматична число якіх дорівнює 4. Найпростішім таким графом є ??K4. Отже, гіпотезу чотірьох фарб нельзя вдоск...
