Page 71 - 4496

Теорема (Дирак, 1952). Якщо у зв'язному графі з п
вершинами (при n) степені всіх вершин більше або рівні
n/2, то граф гамільтонів.

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

Розфарбовувати можна як ребра графа, так і вершини.
Розглянемоо задачі про розфарбування вершин,. при цьому
вважаємо, що граф не орієнтований і не є мультграфом.
У неорграфі G(A,U) зважимо вершини цілими
позитивними числами й зажадаємо при цьому, щоб суміжним
вершинам були зіставлені різні числа. Якщо число трактувати
як номер фарби (кольору), то таке зважування вершин
називають розфарбуванням графа.
Розфарбування графа, у якому використовується
мінімальне число фарб, називається мінімальним. Число фарб
мінімального розфарбування є одною з характеристик графа й
називається хроматичним числом.
До завдання визначення мінімального розфарбування
графа зводяться багато завдань. Як приклад назвемо завдання
знаходження мінімального числа внутрішніх змінних у
програмі. При побудові програм необхідно вводити додаткові
тимчасові змінні, наприклад, змінну - лічильник циклу в
операторі for (int i=1; i<10; i++).
Якщо вершинам зіставити входження змінної в
програму, а ребром позначити залежність однієї змінної від
іншої, то ідентифікатору змінної буде відповідати фарба.
Дійсно, залежні змінні повинні мати різні імена. Тоді
знаходження мінімального числа внутрішніх змінних
зведеться до мінімального розфарбування вершин графа. У
цім трактуванні завдання розглядалося А.П. Єршовим, одним
з найбільших теоретиків і практиків програмування, що
запропонували цікавий евристичний алгоритм розв'язку цього
завдання.

А.П. Єршова
Уведемо поняття відстані між вершинами як довжину
мінімального шляху між ними. Назвемо множину вершин на
відстані одиниці від а 1-околом вершини а, p-околом вершини
а- а- множина вершин на відстані p від а.
68