stify"> робіт потрібно хоча б один загальний ресурс, тобто коли . Це означає, що i-я і роботи не можуть виконуватися одночасно. Розмальовка графа визначає тоді деякий розподіл ресурсів (по виконуваних робіт), причому таке, що роботи, відповідні вершин одного кольору, виконуються одночасно. Найкраще використання ресурсів (тобто виконання всіх n робіт за найменший час) досягається при оптимальній розфарбуванні вершин графа .
Завдання складання розкладів
Припустимо, що потрібно прочитати кілька лекцій за найкоротший час. Читання кожної лекції окремо займає одну годину, але деякі лекції не можуть читатися одночасно (наприклад, їх читає один і той же лектор). Побудуємо граф G, вершини якого биективно відповідають лекціям, і дві вершини суміжні тоді і тільки тоді, коли відповідні лекції не можна читати одночасно. Очевидно, що будь-яка правильна розмальовка цього графа визначає допустиме розклад: лекції, відповідні вершин графа, складовим кольоровий клас, читаються одночасно. І, назад, будь-яке припустиме розклад визначає правильне розфарбування графа G. Оптимальні розкладу відповідають мінімальним розмальовки, а число годин, необхідне для прочитання всіх лекцій, одно .
Задача розподілу обладнання
Задані безлічі і робіт і механізмів відповідно. Для виконання кожної з робіт потрібен якийсь час, однакове для всіх робіт, і деякі механізми. При цьому ніякої з механізмів не може бути одночасно зайнятий у декількох роботах. Потрібно розподілити механізми так, щоб загальний час виконання всіх робіт була мінімальною.
Побудуємо граф G, поклавши VG = Vи оголосивши вершини v i і v j суміжними тоді і тільки тоді, коли для виконання робіт v i і v j потрібно хоча б один загальний механізм. При правильній розмальовці графа Gработи, відповідні вершин одного кольору, можна виконувати одночасно, а найменший час виконання всіх робіт досягається при мінімальній розмальовці.
Оцінки хроматичного числа
Оскільки завдання правильної розмальовки точно вирішити важко, то актуальні оцінки хроматичного числа, що виражаються в термінах більш-менш просто вичіслімих параметрів графа. Розглянемо деякі теореми та оцінки, пов'язані з хроматичним числах .
Позначимо через безліч всіх породжених...
