Решение задачи: оптимальное расписание с помощью теории графов

Для решения этой задачи воспользуемся теорией графов, а именно — правильной раскраской вершин. 1. Построим граф конфликтов: Вершинами графа будут задачи \(v_1, v_2, v_3, v_4, v_5\). Ребро между двумя вершинами проводится в том случае, если задачи используют хотя бы один общий компьютер (то есть не могут выполняться одновременно). Составим список связей (конфликтов): \(v_1\) (комп. 1, 2) конфликтует с: — \(v_2\) (комп. 1) — \(v_3\) (комп. 1, 2) — \(v_4\) (комп. 1) — \(v_5\) (комп. 2) \(v_2\) (комп. 1) конфликтует с: — \(v_1\) (уже учтено) — \(v_3\) (комп. 1) — \(v_4\) (комп. 1) \(v_3\) (комп. 1, 2) конфликтует с: — \(v_1, v_2\) (уже учтено) — \(v_4\) (комп. 1) — \(v_5\) (комп. 2) \(v_4\) (комп. 1, 3) конфликтует с: — \(v_1, v_2, v_3\) (уже учтено) — \(v_5\) (комп. 3) \(v_5\) (комп. 2, 3) конфликтует с: — \(v_1, v_3, v_4\) (уже учтено) 2. Определим хроматическое число графа \(\chi(G)\): Заметим, что задачи \(v_1, v_3, v_4, v_5\) образуют цикл \(v_1 - v_5 - v_4 - v_3 - v_1\). Кроме того, в графе есть полные подграфы (клики). Например, вершины \(v_1, v_3, v_4\) соединены все друг с другом (так как все используют компьютер №1), что требует минимум 3 цвета. Попробуем раскрасить граф: — Цвет 1: \(v_1\) — Цвет 2: \(v_3\) (конфликтует с \(v_1\)) — Цвет 3: \(v_4\) (конфликтует с \(v_1\) и \(v_3\)) — Цвет 4: \(v_5\) (конфликтует с \(v_1, v_3, v_4\)). Проверим: \(v_5\) использует комп. 2 и 3. \(v_1\) использует комп. 2, \(v_3\) использует комп. 2, \(v_4\) использует комп. 3. Значит, \(v_5\) действительно конфликтует со всеми тремя и требует 4-й цвет. Задачу \(v_2\) можно покрасить в любой цвет, не конфликтующий с комп. 1 (например, в цвет задачи \(v_5\), так как они не имеют общих компьютеров). Минимальное количество цветов равно 4. Каждый цвет соответствует одному такту времени \(t\). 3. Вывод: Минимальное суммарное время выполнения всех задач равно \(4t\). Ответ: 4t