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

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

180. Докажите, что число вершин (p), ребер (q) и граней (r) любого выпуклого многогранника связано формулой p–q+r=2.

181. Доказать, что граф правильного многогранника является плоским и правильным.

182. Найти гамильтоновы циклы на правильных графах.

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

184. Нарисуйте граф, изоморфный графу, изображенному на рисунке, так, чтобы внешней стала грань

∙ 2

∙ 3

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

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

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

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

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

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

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

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

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

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