1. Найти хроматическое число графов

а)		б)
в)		г)
д)		е)

2. Привести пример графа, не имеющего треугольников, т.е. трехэлементных полных подграфов, у которых хроматическое число равно 5.

3. Граф назовем вершинно-критическим, если удаление любой вершины приводит к графу с меньшим хроматическим числом. Какие из следующих графов будут вершинно-критическими:

а)	графы а-г задачи 1	б)
в)		г)

4. Граф назовем реберно-критическим, если удаление любого ребра приводит к графу с меньшим хроматическим числом. Какие из следующих графов будут реберно-критическими.

а)	графы а-г задачи 1,	б)
в)	графы в,г задачи 3.

5. Пусть G – вершинно-критический и c(G)=k.

Доказать, что

а) G – связный граф,

б) степень каждой вершины не меньше k-1,

в) G не имеет точек сочленения.

6. Доказать, что всякий k–хроматический граф (т.е. граф G для которого c(G)=k) содержит вершинно-критический k–хроматический подграф. Найти такой подграф для графов задачи 1.

7. Пусть c(G)=k. Граф G называется однозначно раскрашиваемым, если каждая раскраска в k цветов определяет одно и тоже разбиение множества вершин. Какие из следующих графов будут однозначно раскрашиваемы

а)		б)
в)		г)

8. Реберной раскраской называется функция g: E®{1,2,…,k}, где E-множество ребер, k-натуральное число (число красок). Раскраска называется правильной, если для любых двух смежных ребер e₁ и e₂ выполняется неравенство g(e₁)¹g(e₂). Наименьшее число красок, необходимое для правильной реберной раскраски графа называется его хроматическим индексом. Найти хроматический индекс графов из задачи 1.

9. На предприятии планируется выполнить 8 работ: v₁,v₂,…v₈. Для выполнения этих работ необходимы механизмы а₁,а₂,…,а₆. Использование механизмов для проведения каждой из работ определяется следующей таблицей Т:

Никакой из механизмов не может быть занят одновременно на двух работах. Все работы выполняются за одно и тоже время t. Как распределить механизмы, чтобы суммарное время выполнения всех работ было наименьшим?

10. Решить задачу №9, если таблица Т имеет следующий вид:

11. Решить задачу №9, если таблица Т имеет следующий вид:

12. В учебном центре необходимо провести занятия по математике, физике, химии, иностранному языку и истории в группах А,В,С. Занятия проводятся преподавателями K,L,M. Следующая таблица Т указывает, какие занятия надо провести в группах и какими преподавателями они могут быть проведены:

Каждое занятие проводится в течение двух часов, включая перерывы. В центре имеются три аудитории, которые вмещают лишь одну из групп. Для занятий по физике и химии оборудована одна из этих аудиторий. Можно ли провести все необходимые занятия в течение одного рабочего дня (8 часов)? Если можно, то как это сделать?

13. Решить задачу №12, если таблица Т имеет следующий вид:

14. На многопроцессорном вычислительном комплексе необходимо выполнить 7 заданий v₁,…,v₇. Задания могут использовать общие данные, и в этом случае их выполнение не может проводиться одновременно:

Предположим, что все задания могут выполняться за одно и то же время t. За какое наименьшее время можно выполнить все задания? Какое количество процессоров может для этого понадобиться?

15. Решить задачу №14, если таблица Т имеет следующий вид: