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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№	Тема	Литература
1	Основные определения и примеры графов.	1 (гл. 1 § 1); 5 (гл. 1); 6 (гл. 6 § 1); 7 (гл. 1); 8 (гл. 1 § 2); 10 (гл. 7 § 1); 11 (гл. 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)