1. Хроматические числа соответственно равны 4,3,3,4,4,4.

2. Указание. См. доказательство теоремы 5.2.

3. Вершинно-критическими будут графы 3в и 3г.

4. Реберно-критическими будут графы 3в и 3г.

5. Решение. Пусть G – несвязный граф. Тогда G распадается на компоненты связности G₁,G₂,…,G_c и c>1. Как отмечалось в §1, выполняется неравенство

c(G)=max{c(G₁),c(G₂),…,c(G_c)}.

Предположим для простоты, что максимум реализуется на c(G₁), т.е. c(G)=c(G₁). Тогда удаление вершины любой из компонент связности G₂,…,G_c не изменит хроматического числа всего графа. Следовательно, вершинно-критический граф является связным.

Докажем, что степень каждой вершины не меньше k-1. Предположим противное: в графе G существует вершина v′, такая что r(v′)<k-1. Тогда, поскольку G – вершинно-критический, то c(G-v′)£k-1. Это означает, что G-v′ можно правильно раскрасить k-1 краской. Но так как r(v′)<k-1, то при этой раскраске на вершины, смежные v′, будет израсходовано меньше, чем k-1 краска. Следовательно, одна из k-1 красок останется для вершины v′. Но это означает, что граф G можно правильно раскрасить k-1 краской. Противоречие показывает, что r(v)³k-1 для любой вершины v.

Убедимся теперь, что G не имеет точек сочленения. Предположим, что G имеет точку сочленения a. Тогда граф G-a является несвязным и распадается на компоненты связности H₁,H₂,…,H_d, d>1. Графы H_i+a для любого i можно правильно раскрасить k-1 краской. (Граф H_i+a – это граф, вершинно-порожденный множеством H_iÈ{a}). Действительно, удалим вершину v из компоненты связности, отличной от H_i. Так как граф G – вершинно-критический, то граф G-v можно правильно раскрасить k-1 краской. Но граф H_i+a – подграф граф G-v и поэтому c(H_i+a)£k-1. Очевидно, что все графы H_i+a можно правильно раскрасить так, что вершина а при любом i будет раскрашена одной и той же краской. Но тогда и весь граф G будет правильно раскрашен k-1 краской. Противоречие показывает, что G не имеет точек сочленения.

6. В случае а и г в качестве Н можно взять четырехэлементный полный подграф, в случае d-трехэлементный, а в случае в – цикл длины 5.

7. Однозначно раскрашиваемыми будут графы в случаях а,в и г.

8. Хроматический индекс соответственно равен

9. Решение. Рассмотрим граф G, множество вершин V которого состоит из планируемых работ, т.е. V={v₁,v₂,…,v₈}. Вершины v_i и v_j (при i¹j) соединим ребром в том и только в том случае, когда существует хотя бы один механизм, который используется при выполнении и той и другой работы. Мы получим граф, изображенный на рис.5.11.

Рис.5.11

Граф содержит четырехэлементный полный подграф {v₁,v₂,v₄,v₅}, поэтому для правильной раскраски графа потребуется, как минимум четыре краски. Раскрасим эти вершины так, как показано на рис.5.11. Далее, вершины v₃ и v₈ смежны между собой и смежны вершинам v₁ и v₅, раскрашенным первой и четвертой красками. Одна из этих вершин, следовательно, должна быть раскрашена второй, другая третьей красками. Осталось раскрасить вершины v₆ и v₇. Вершину v₆ красим первой, а v₇ – четвертой красками. Мы получили правильную раскраску графа четырьмя красками. Следовательно, все работы можно выполнить за время 4t по такому графику: сначала выполняются работы v₁ и v₆, затем v₂ и v₈, v₃ и v₄ и, наконец, v₅ и v₇.

10. Все работы могут быть выполнены за время 4t.

11. Все работы могут быть выполнены за время 3t.

12. Указание. Рассмотреть граф, вершинами которого являются занятия. (Граф, таким образом, будет иметь 10 вершин). Вершины соединить ребром, если занятия нельзя проводить одновременно. Это будет когда либо занятия проводятся в одной группе, либо одним преподавателем, либо в одной и той же аудитории (в случае занятий по физике и химии). Найти правильную раскраску полученного графа наименьшим числом цветов при дополнительном условии: число вершин, раскрашенных одной краской не должно превосходить трех (так как в центре имеется всего три аудитории). Ответ: занятия при указанных условиях провести можно. Например, сначала проводятся занятия (А,М), (В,Х) и (С,Ис), затем – (А,Х), (В,М) и (С,Ин), после этого – (А,Ф) и (В,Ин), и наконец, проводятся занятия (А,Ис) и (С,Ф). В обозначениях занятий первая компонента – наименование группы, вторая – наименование предмета.

13. Занятия при указанных условиях провести можно.

14. Указание. Рассмотреть граф, вершинами которого являются задания. Различные вершины соединить ребром, если задания используют общие данные. Найти хроматическое число c этого графа и соответствующую оптимальную раскраску. Тогда наименьшим временем выполнения будет ct, а количество процессоров рано наибольшему числу вершин, раскрашенных одной краской. Ответ: 4t, два процессора.

15. Наименьшее время выполнения всех заданий равно 2t, необходимы для этого четыре процессора.