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

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. Коробка скоростей – механизм для изменения частоты вращения ведомого вала при неизменной частоте вращения ведущего. Это изменение происходит за счет того, что находящиеся внутри коробки шестерни вводятся в зацепление специальным образом. Одна из задач, стоящих перед конструктором коробки, заключается в минимизации числа валов, на которых размещаются шестерни.

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

	1	2	3	4	5	6	7
1		+		+	+		+
2	+		+		+		+
3		+			+	+
4	+					+
5	+	+	+				+
6			+	+			+
7	+	+			+	+

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

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