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

UptoLike

ВУЗ: 

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

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

Рубрика: 

13
8. На плоскости дано 100 окружностей, составляющих
связную (не распадающуюся на части) фигуру. Доказать, что эту
фигуру можно нарисовать, не отрывая карандаша от бумаги и
не проводя дважды одну и ту же линию.
3. ДЕРЕВЬЯ
3.1. Определения и свойства
Определение 3.1. Деревом называется связный граф без
циклов.
Таким образом, в дереве невозможно, передвигаясь по раз-
личным рёбрам, вернуться в исходную вершину.
Определение 3.2. Висячей вершиной называется вершина,
из которой выходит ровно одно ребро.
Наглядное представление для дерева можно получить с по-
мощью следующей конструкции (см. рис. 12). Из вершины
0
v
проведём рёбра в соседние вершины
1
v ,
2
v ,
3
v , из них проведём рёбра к их «со-
седям»
4
v ,
5
v ,
6
v ,
7
v ,
8
v ,
9
v ,
10
v и
т.д. Исходная вершина
0
v называется
корнем. Отметим, что каждая вершина
может быть корнем.
Теорема 3.1. Граф, в котором любые две вершины соеди-
нены ровно одной цепью, является деревом.
Д о к а з а т е л ь с т в о. Граф связен. Пусть в нём есть
цикл, тогда любые две вершины цикла соединены по крайней
мере двумя путями. Противоречие.
Теорема 3.2. В дереве любые две вершины соединены ровно
одной цепью.
Д о к а з а т е л ь с т в о. Пусть найдутся две вершины, со-
единённые двумя разными путями; а) если эти пути не имеют
общих рёбер, то из них получим цикл; б) если пути имеют об-
щие рёбра, то выберем первую вершину
0
v , в которой пути рас-
ходятся. За вершиной
0
v на первом пути выберем вершину
1
v ,

Страницы