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

137. Проверить формулу Эйлера для графов W₆и К_{2 n}.

138. Для шахматной доски размером К х К найдите числа p, q, r и убедитесь в справедливости теоремы Эйлера.

139. Обобщите формулу Эйлера для несвязных графов.

140. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

141. Мэрия решила построить в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между перекрестками, универсам. Сколько будет построено универсамов?

142. Какие из графов являются планарными:

143. Докажите, что, если в планарном графе каждая грань есть С_n (цикл длиныn),q=n*(p-2)/(n-2).

144. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?

145. При каких nграфы порядка 2nявляются планарными?

146. Печатная плата представляет собой пластинку из изолирующего материала, в специально изготовленные гнезда которой устанавливают электронные приборы. В качестве проводников, соединяющих эти приборы, служат напыленные металлические дорожки. Поскольку проводники не изолируются, то дорожки не должны пересекаться. Если это может произойти, то одну из дорожек переносят на другую сторону платы. Конструктор Иванов придумал схему печатной платы, которая состоит из 12 приборов и 32 проводников, соединяющих их. Можно ли изготовить такую плату так, что все проводники будут расположены на одной её стороне?

147. Докажите, что для плоского связного графа справедливо неравенство q<=3p-6

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

149. Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?

150. Докажите, что для любого плоского графа (в том числе и несвязного) справедливо неравенство q<=3p-6.

151. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, - не плоский.

152. В графе степень любой вершины не меньше шести. Доказать, что его нельзя нарисовать на плоскости, так чтобы никакие два ребра его не пересекались.

153. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо «красный'», либо «синий» граф не является плоским.

154. Покажите, что граф W₆стягиваем к графу К₄.

155. Докажите, что граф Петерсона не является планарным.

156. Инженер Иванов усовершенствовал свою плату. Теперь она имеет 9 приборов и 17 проводников. Схема платы представлена на рисунке. Можно ли изготовить такую плату так, что все проводники будут расположены на одной её стороне?

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

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

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

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

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

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

• 2

• 3