Раскраски графа. 192. Найдите хроматические числа для:

192. Найдите хроматические числа для:

∙ вполне несвязного графа с n вершинами;

∙ полного графа с n вершинами;

∙ двудольного графа, доли которого имеют n и m вершин;

∙ дерева с n вершинами.

193. Для графов, изображенных на рисунке, найдите хроматические числа и какую-либо правильную раскраску.

194. Сколькими способами можно раскрасить полный помеченный граф на 6 вершинах шестью цветами? (Два способа считаются различными, если некоторая вершина при одном способе имеет один цвет, а при другом способе – другой.)

195. Определите хроматические числа для графов платоновых тел:

196. Граф называется критическим, если удаление любой его вершины вместе с инцидентными ей ребрами приводит к графу с меньшим хроматическим числом. Покажите, что К_n, является критическим графом при n >1.

197. Докажите, что всякий критический граф, являющийся k-хроматическим:

∙ связен;

∙ не имеет точек сочленения;

∙ степень каждой его вершины не меньше, чем k–1.

198. Коробка скоростей – механизм для изменения частоты вращения ведомого вала при неизменной частоте вращения ведущего. Это изменение происходит за счет того, что находящиеся внутри коробки шестерни вводятся в зацепление специальным образом. Одна из задач, стоящих перед конструктором коробки, заключается в минимизации числа валов, на которых размещаются шестерни.

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

		+		+	+		+
	+		+		+		+
		+			+	+
	+					+
	+	+	+				+
			+	+			+
	+	+			+	+

199. Образовавшийся коммерческий университет арендует здание для проведения занятий. В четверг проводится 7 лекций: право, английский язык, французский язык, экономика, менеджмент, маркетинг, этикет. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно. В таблице крестиком помечены лекции, которые не могут читаться одновременно. Определите минимальное время, за которое могут быть прочитаны лекции в четверг.

	П	А	Ф	Э	М	М	Э
Право		+		+			+
Англ. яз.	+		+		+	+
Фран. яз.		+			+	+	+
Экономика	+				+	+
Менеджмент		+	+	+		+
Маркетинг		+	+	+	+
Этикет	+		+

200. Задача распределения оборудования. Заданы множество работ и механизмов. Для выполнения каждой из работ требуются некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом ни один из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимально.

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

202. Известно, что на карте некоторой области нет точек, в которых сходятся границы нечетного числа районов. Докажите, что такую карту можно раскрасить двумя цветами так, что любые два соседних района будут покрашены разными красками.

203. Докажите, что для раскраски карты, полученной при пересечении прямых и окружностей на плоскости, достаточно двух цветов.

Список рекомендуемой литературы по теории графов

№	Тема	Литература
1.	Основные определения и примеры графов.	1 (гл. 1 § 1); 5 (гл. 1); 6 (гл. 6 § 1); 7 (гл. 1); 8 (гл. 1 § 2); 10 (гл. 7 § 1); 1 1(гл. 4 § 1); 12 (гл. 1 § 1, гл. 2 § 2, 3)
2.	Изоморфизм графов.	5 (гл. 1 § 1); 10 (гл. 7 § 1); 12 (гл. 1 § 1, гл. 2 § 2)
3.	Способы описания графов.	1 (гл. 1 § 4); 2 (гл. 7 § 1); 5 (гл. 1 § 6); 6 (гл. 6 § 2); 7 (гл. 1 § 8); 10 (гл. 7 § 4); 11 (гл. 4 § 1)
4.	Достижимость и связность.	1 (гл. 1 § 2); 5 (гл. 5 § 33); 6 (гл. 6 § 5, 6); 7(гл. 2);10 (гл. 8 § 1); 11 (гл. 4 § 3)
5.	Мосты, блоки, меры связности.	1 (гл. 2 § 2, гл. 8 § 2); 2 (гл.. 7 § 4); 5 (гл. 5 § 34); 6 (гл. 6 § 13); 10(гл. 7 § 2)
6.	Кратчайшие пути	1 (гл. 10); 2 (гл. 6 § 3, 4); 5 (гл. 12 § 76); 6 (гл. 6 § 9); 7 (гл. 8); 8 (гл. 3); 10 (гл. 8 § 7); 11 (гл. 4 § 5)
7.	Обходы графа.	1 (гл. 8 § 1, 4); 2 (гл. 7 § 3); 6 (гл. 6 § 3); 11 (гл. 4 § 9);
8.	Эйлеровы циклы в графах.	1 (гл. 3 § 1, гл. 8 § 5); 5 (гл. 7 § 43); 6 (гл. 6 § 7); 10 (гл. 10 § 2); 12 (гл. 3 § 6)
9.	Гамильтонов цикл на графе.	1 (гл. 3 § 2); 5 (гл. 7 § 44); 7 (гл. 10 § 2);10 (гл. 10 § 3); 12 (гл. 3 § 7)
10.	Задача коммивояжера	1 (гл. 13); 7 (гл. 10 § 5, 6, 7); 8 (гл. 7)
11.	Фундаментальные циклы и разрезы	6 (гл. 6 § 12); 10 (гл. 10 § 1); 11 (гл. 4 § 11, 12);
12.	Деревья. Эквивалентные определения деревьев	1 (гл. 2 § 1); 5 (гл. 2 § 13); 7 (гл. 7 § 1);10 (гл. 9 § 1); 12 (гл. 4 § 9)
13.	Каркас минимального веса	2 (гл. 7 § 2); 5 (гл. 2 § 15, гл. 12 § 75); 6 (гл. 6 § 8); 7 (гл. 7 § 3);10 (гл. 9 § 5)
14.	Двудольные графы.	6 (гл. 6 § 14); 10 (гл 7 § 3.2)
15.	Совершенное паросочетание и теорема Холла	5 (гл. 12 § 77); 7 (гл. 12); 10 (гл. 8 § 4); 12 (гл. 8 § 25)
16.	Теорема Менгера	5 (гл. 5 § 35); 10 (гл. 8 § 3); 12 (гл. 8 § 28)
17.	Максимальное паросочетание	2 (гл. 7 § 5); 5 (гл. 12 § 77); 7 (гл. 12);8 (гл. 5)
18.	Потоки в сетях	1 (гл. 11); 6 (гл. 6 § 10); 7 (гл. 11); 8 (гл. 4); 10 (гл. 8 § 5); 12 (гл. 8 § 29)
19.	Независимые и доминирующие множества	5 (гл. 4); 6 (гл. 6 § 11); 7 (гл. 3);10(гл. 11)
20.	Ориентированный граф	1 (гл. 1 § 3); 2 (гл. 6 § 1, 2); 5 (гл. 10 § 63, 64, 65); 12 (гл. 7 § 22)
21.	Достижимость, связность в орграфах	1 (гл. 8 § 3); 2 (гл. 6 § 7); 7 (гл. 2);10 (гл. 8 § 6)
22.	Эйлеров цикл в орграфах.	12 (гл. 7 § 23)
23.	Гамильтонов путь и цикл в орграфах.	12 (гл. 7 § 23)
24.	Плоские графы. Планарность.	1 (гл. 5 § 1); 5 (гл. 6 § 36); 10 (гл. 12 § 2); 11 (гл. 4 § 15); 12 (гл. 5 § 12)
25.	Укладки графов	1 (гл. 5 § 11); 5 (гл. 6 § 41); 12 (гл. 2 § 4, гл. 5 § 14)
26.	Формула Эйлера для плоских графов	1 (гл. 5 § 2); 5 (гл. 6 § 37); 12 (гл. 5 § 13)
27.	Стереографическая проекция.	5(гл. 6 §36); 12(гл. 2 §4)
28.	Двойственный граф	1 (гл. 5 § 4), 12 (гл. 5 § 15)
29.	Раскраски графов	1 (гл. 6); 5 (гл. 9); 10 (гл. 12 § 3); 11 (гл. 4 § 14); 12 (гл. 6)
30.	Раскрашивание карт. Теорема о пяти красках.	10 (гл. 12 § 2.3); 12 (гл. 6)

Список литературы

1. Асанов М. О., Баранский В. А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск, 2001.
2. Ахо А., Хокпкрофт Дж., Ульман Дж.Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001.
3. Бадин Н.М., Волченков С.Г., Дашниц Н.Л., Корнилов П.А. Ярославские олимпиады по информатике. – Ярославль, 1995.
4. Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.
5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.
6. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.
7. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
8. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.:Мир,1981.
9. Мельников О.И. Занимательные задачи по теории графов. – Минск.: Тетрасистемс, 2001.
10. Новиков Ф.А. Дискретная математика для программистов. – СПб.:Питер, 2001.
11. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2002.
12. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
13. Харари Ф. Теория графов. – М.: Мир,1973.
14. Яблонский С.В. Введение в дискретную математику. – М.: Высш. шк., 2002.

Использованы задачи с сайта www.zaba.ru.

Оглавление

Введение. 3

Комбинаторика. 3

Предмет комбинаторики. 3

Правила суммы и произведения. 5

Формула включения и исключения. 7

Размещения с повторениями. 9

Размещения без повторений. 11

Перестановки. 12

Перестановки с повторениями. 13

Сочетания. 15

Свойства чисел ..... 17

Сочетания с повторениями. 19

Комбинаторика разбиений. 21

Вероятность. 26

Бином Ньютона. 28

Треугольник Паскаля. 31

Полиномиальная формула. 32

Рекуррентные соотношения. 34

Асимптотики. 42

Задачи по комбинаторике. 44

Общие правила комбинаторики. 44

Формула включения и исключения. 46

Размещения с повторениями. 46

Размещения без повторений. 48

Перестановки. 49

Сочетания. 50

Сочетания с повторениями. 51

Разные задачи. 51

Комбинаторика разбиений. 55

Вероятность. 58

Бином Ньютона. Полиномиальная формула. 60

Рекуррентные соотношения. 60

Задачи по теории графов. 63

Основные определения и примеры графов. 63

Матрицы, ассоциированные с графом.. 65

Изоморфизм графов. 67

Достижимость и связность. 67

Циклы.. 70

Алгоритмы обхода связного графа. 71

Деревья. 73

Двудольные графы. 76

Ориентированные графы и мультиграфы.. 78

Игры и головоломки. 81

Плоские графы.. 82

Стереографическая проекция. 83

Двойственные графы.. 83

Раскраски графа. 84

Список рекомендуемой литературы по теории графов. 87

Список литературы.. 89

Корнилов Петр Анатольевич

Никулина Надежда Ивановна

Дата добавления: 2015-01-03