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

UptoLike

ВУЗ: 

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

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

Рубрика: 

2
Определение 1.6. Говорят, что вершина
v
и ребро
e
инци-
дентны, если ребро
e
содержит вершину
v
.
Определение 1.7. Два ребра, инцидентные одной вершине,
называются смежными.
Определение 1.8. Степенью вершины
v
называется коли-
чество рёбер, инцидентных данной вершине.
Обозначается:
vdv deg .
Определение.1.9. Вершина называется чётной (нечётной),
если её степень – чётное (нечётное) число.
Определение 1.10. Граф без петель называется мультигра-
фом, граф без кратных рёбер и петель называется просто гра-
фом, граф, в котором есть петли, называется псевдографом.
В дальнейшем мы будем использовать геометрическое
представление графа. Вершины графа изображаются в виде то-
чек на плоскости. Если две вершины смежные,
то соответствующую пару точек соединяют ду-
гой-ребром. Например, на рис.1 изображен граф
Q , заданный множеством вершин
54321
,,,, vvvvvV и множеством рёбер
4321
,,, eeeeE .
Теорема 1.1. В любом графе qv
p
i
i
2deg
1
, где
p
– число
вершин, а
q
– число рёбер.
Д о к а з а т е л ь с т в о. Вычисляя сумму всех степеней, мы
получаем, что каждое ребро считается дважды, так как оно ин-
цидентно двум вершинам (петли также считаются дважды). По-
этому общая сумма будет равна удвоенному числу рёбер.
Следствие. В любом графе число вершин нечётной степени
чётно.
Д о к а з а т е л ь с т в о. В противном случае сумма степе-
ней вершин графа нечётна.

Страницы