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

UptoLike

ВУЗ: 

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

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

Рубрика: 

3
Теорема 1.2. Во всяком графе с
n
вершинами
2
n
(без
кратных рёбер и петель) найдутся, по меньшей мере, две вер-
шины с одинаковыми степенями.
Д о к а з а т е л ь с т в о. Пусть вершины с разными степе-
нями. Степень вершины может быть равна 1,0 nk . Пусть
есть вершина
i
v , 0deg
i
v , тогда найдётся вершина
j
v ,
1deg nv
j
. Но
j
v должна быть соединена с остальными, в
том числе с
i
v (противоречие). Поэтому найдутся две вершины с
одинаковыми степенями.
Определение 1.11. Граф называется полным, если каждые
две различные вершины соединены одним и только одним реб-
ром.
Теорема 1.3. В полном графе с
n
вершинами
2
1
nn
рё-
бер.
Д о к а з а т е л ь с т в о. Каждой вершине инцидентно
1n ребро, но в произведении
1nn каждое ребро учтено
дважды, поэтому число рёбер равно
2
1
nn
.
Определение 1.12. Путём в графе EVG , называется
любая последовательность вида
nnn
vvvvvvvvvv ,,,...,,,,,,,
12211100
. (1)
Число
n
называется длиной пути.
Определение 1.13. Цепью называется путь, в котором нет
повторяющихся рёбер.
Определение 1.14. Простой цепью называется путь без по-
вторения вершин.
Теорема 1.4. Если существует путь из вершины
v
в вер-
шину
u
uv , то из рёбер этого пути можно построить
uv – цепь.

Страницы