Page 73 - 4496

 призначення співробітників на посаді;
 розподілу товарів зі складів по торговельних точках.
У всіх цих завданнях вихідна множина складається із
двох різних за змістом підмножин, а зв'язки можуть бути
тільки між елементом одного й елементом другого із цих
підмножин.
Властивість біхроматичного графа визначає наступна
теорема.
Теорема. Граф є біхроматичним тоді й тільки тоді,
коли він не містить циклів непарної довжини.
Необхідність доводиться просто: якщо в графі
перебуває цикл непарної довжини, розфарбування двома
фарбами його вершин неможлива. Достатність доводиться
складніше й тут не приводиться.

Задача. Розфарбувати вершини графа так, щоб будь-які
дві суміжні вершини були розфарбовані в різні кольори, при
цьому число використаних кольорів повинне бути
найменшим. Це число називається хроматичним (кольоровим)
числом графа, будемо його позначати (G) (якщо G –
даний граф). Якщо число , то граф називається k-
розфарбовуваним.
Функцією Гранди називається функція на вершинах
графа, що відображає вершини в множину {1,2,…, a},причому
якщо вершина x i пофарбована в кольори з номером k, то
функція Гранди h(x i) = k.
Ясно, що для даного графа хроматичне число є єдиним,
але функцій Гранди може бути дуже багато. Природно, що
знайти хоча б одну функцію Гранди - це значить, знайти одну
з можливих “найкращих” розфарбувань (таких розфарбувань
може бути багато).
Відмітимо, що якщо даний граф є повним, тобто будь-
які дві вершини є суміжними, то хроматичне число такого
графа дорівнює п, де п – число вершин.
Набір вершин графа називається максимальною
незалежною системою (МНС), якщо будь-які дві вершини із
цього набору не є суміжними й не можна включити в цей
набір іншу вершину, щоб ця умова збереглася. Помітимо, що
знаходження МНС у графі досить просто: беремо довільну
70