Графы и сети. Харитонова Е.В. - 7 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

6
● Графы, определенные выше, называют простыми графами.
● Ребро, которое соединяет вершину саму с собой, называется петлей.
Если в графе допускается наличие петель, то он называется графом с
петлями.
Если в графе допускается наличие более одного ребра между двумя вер-
шинами, то он называется мультиграфом.
Если каждая вершина графа
отмечена, то граф называется размеченным.
Если же допускается как наличие петель, так и существование более од-
ного ребра между двумя вершинами, то такой объект называют псевдографом.
● Степенью вершины υ, обозначается deg(υ), называется количество ре-
бер, инцидентных этой вершине. Вершина степени 0 называется изолированной.
Пример. В графе, показанном на рис. 1.4, вершины a и c – смежные, а e
1
, e
2
и e
3
– -
смежные ребра. Однако, вершины a и f смежными не являются, а e
2
и e
5
не являются смеж-
ными ребрами. Вершины b, c, d имеют степень 2, в то время как вершины a и f имеют сте-
пень 3.
Рис. 1.4
ТЕОРЕМА 1.1. Сумма степеней вершин графа всегда четная.
Доказательство. Поскольку каждое ребро графа имеет два конца, сте-
пень каждого конца увеличивается на 1 за счет одного ребра. Таким образом, в
сумму степеней всех вершин каждое ребро вносит 2 единицы, поэтому сумма
должна в два раза превышать число ребер. Следовательно, сумма является чет
-
ным числом.
ТЕОРЕМА 1.2. В любом графе количество вершин нечетной степени
четно.
Доказательство. Доказательство проведем методом от противного:
предположив, что теорема не верна, найдем противоречие, из которого будет
следовать, что теорема справедлива. Если теорема не верна, то имеется нечет-
ное количество вершин, степени которых нечетны. Но сумма степеней вершин
с четными степенями четна. Сумма степеней всех вершин есть сумма степеней
вершин с нечетными степенями плюс сумма степеней вершин с четными степе-
нями. Поскольку сумма нечетного числа и четного числа есть число нечетное,
а
e
1
e
2
e
3
b d c
e
5
e
6
ƒ
e
4

Страницы