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

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

162. Найдите двойственные графы для следующих графов:

163. Покажите, что граф, двойственный к колесу W_n, является колесом.

164. Плоский граф G имеет 7 вершин, 10 ребер и 5 граней. Сколько вершин, ребер и граней имеет двойственный к нему граф.

165. Докажите, что у выпуклого многогранника найдутся две грани с одинаковым числом ребер.

166. Докажите, что не существует выпуклого многогранника, у которого все грани шестиугольники.

167. Может ли существовать плоский граф с пятью гранями, в котором каждая пара граней является смежными?

168. Дан плоский граф, в каждой вершине которого сходится не более трех ребер. Докажите, что

∙ четное число граней имеет нечетное число смежных граней;

∙ существует грань, которая имеет не более пяти смежных с ней граней.

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

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

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

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

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

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

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

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

173. Приведите пример графа, последовательная раскраска вершин которого не является минимальной.

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

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

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

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

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

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

№	Тема	Литература
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); 14(гл. 3 § 1)
2.	Изоморфизм графов.	5 (гл. 1 § 1); 10 (гл. 7 § 1); 12 (гл. 1 § 1, гл. 2 § 2); 14(гл. 3 § 4)
3.	Способы описания графов.	1 (гл. 1 § 4); 2 (гл. 7 § 1); 5 (гл. 1 § 6); 6 (гл. 6 § 2); 7 (гл. 1 § 8); 10 (гл. 7 § 4); 11 (гл. 4 § 1); 14(гл. 3 § 4)
4.	Достижимость и связность.	1 (гл. 1 § 2); 5 (гл. 5 § 33); 6 (гл. 6 § 5, 6); 7(гл. 2);10 (гл. 8 § 1); 11 (гл. 4 § 3); 14(гл. 3 § 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); 14(гл. 3 § 10,11,12)
7.	Обходы графа.	1 (гл. 8 § 1, 4); 2 (гл. 7 § 3); 6 (гл. 6 § 3); 11 (гл. 4 § 9); 14(гл. 3 § 17)
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); 14(гл. 3 § 15,16)
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); 14(гл. 3 § 24, 25, 26)
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); 14(гл. 3 § 3)
24.	Плоские графы. Планарность.	1 (гл. 5 § 1); 5 (гл. 6 § 36); 10 (гл. 12 § 2); 11 (гл. 4 § 15); 12 (гл. 5 § 12); 14(гл. 3 § 20)
25.	Укладки графов	1 (гл. 5 § 11); 5 (гл. 6 § 41); 12 (гл. 2 § 4, гл. 5 § 14); 14(гл. 3 § 21)
26.	Формула Эйлера для плоских графов	1 (гл. 5 § 2); 5 (гл. 6 § 37); 12 (гл. 5 § 13); 14(гл. 3 § 20)
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); 14(гл. 3 § 22)
30.	Раскрашивание карт. Теорема.о пяти красках.	10 (гл. 12 § 2.3); 12 (гл. 6); 14(гл. 3 § 22)

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

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. Шапорев С.Д. Дискретная математика. –СПб:БХВ-Петербург, 2007
15. Яблонский С.В. Введение в дискретную математику. – М.: Высш. шк., 2002.

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

Оглавление

Введение.. 3

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

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

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

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

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

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

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

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

Сочетания. 14

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сочетания. 47

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

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

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

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

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

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

Введение в теорию графов.. 60

Основные определения. 61

Примеры графов. 62

Способы описания графа. 64

Матрица смежности. 64

Матрица инциденций. 65

Перечень ребер. 66

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

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

Связность в неориентированных графах. 67

Связность ориентированных графов. 67

Циклы.. 68

Эйлеров цикл. 68

Гамильтонов цикл. 69

Турниры.. 70

Деревья. 72

Планарные графы.. 73

Раскрашивание графов. 75

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

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

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

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

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

Циклы.. 85

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

Деревья. 88

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

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

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

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

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

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

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

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

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

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

Заводчикова Надежда Ивановна

Прусова Наталия Александровна

Дискретная математика

Редактор Иванова Н.А.

Подписано в печать 25.09.07 Формат бумаги 80х64 1/16

Печ. л. 5.5 Заказ 123 Тираж 100 экз.

Редакционно-издательский отдел Ярославского государственного педагогического университета имени К.Д.Ушинского (ЯГПУ)

150000, Ярославль, Республиканская, 108

ЛР №020080 от 19.12.97

Типография ЯГПУ

150000, Ярославль, Которосльная наб., 44

Дата добавления: 2014-12-29