Элементы дискретной математики - 82 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

82
Плоские графы
161. Проверить формулу Эйлера для графов W
6
и К
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.
В графе степень любой вершины не меньше шести. Доказать, что его нельзя
нарисовать на плоскости, так чтобы никакие два ребра его не пересекались.

Страницы