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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

179. Инженер Иванов придумал схему печатной суперплаты, которая может заменить целый компьютер. Плата состоит из 200 приборов и 2000 проводников. Ясно, что для реализации такой схемы нужно будет использовать многослойную плату, на которой проводники будут располагаться в разных слоях. Докажите, что разработанную схему нельзя изготовить в виде трехслойной платы.