Элементы теории графов. Сюсюкалов А.И - 22 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

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

Рубрика: 

17
Теорема 4.3. Для плоского связного графа справедливо не-
равенство
63
VE
.
Д о к а з а т е л ь с т в о. По формуле Эйлера
2
FEV
,
но по теореме 4.2 FE
3
2
и 2
3
2
EEV , следовательно,
2
3
1
EV , отсюда
63
VE
.
4.2. Задачи
1. В стране 7 озер, соединенных между собой 10 каналами,
причем от любого озера можно доплыть до любого другого.
Сколько в этой стране островов?
2. В квадрате отметили 20 точек и соединили их непересе-
кающимися отрезками друг с другом и с вершинами квадрата
так, что квадрат разбился на треугольники. Сколько получилось
треугольников?
3. Докажите, что граф, имеющий 5 вершин, каждая из кото-
рых соединена ребром с любой другой, не является плоским.
4. а) Каждые две из 6 ЭВМ соединены проводом. Можно ли
все эти провода раскрасить в пять цветов так, чтобы из каждой
ЭВМ выходили пять проводов разного цвета?
б) Каждые две из 15 ЭВМ соединены проводом. Можно ли
все эти провода раскрасить в один из 14 цветов так, чтобы из
каждой ЭВМ выходили 14 проводов разного цвета?
5. Можно ли построить три дома, вырыть три колодца и со-
единить тропинками каждый дом с каждым колодцем так, чтобы
тропинки не пересекались?
6. Докажите, что в плоском графе есть вершина, степень ко-
торой не превосходит 5.
7. Докажите, что граф, имеющий 10 вершин, степень каж-
дой из которых равна 5, - не плоский.

Страницы