Математическое моделирование на графах. Часть 1. Берцун В.Н. - 10 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

10 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
ных вершине А, причем петля считается дважды). На рис. 1.7 пред-
ставлены графы с различными степенями вершин.
CA C
B
E
D
F
A
DB
A
D
B
C
ν
А
= 1 ν
F
= 2 ν
D
= 3, ν
А
= 2
Рис. 1.7
Вершина А является четной, если ν
А
– четно, и нечетной, если
ν
А
– нечетно. Вершины, у которых ν
А
= 1, называются висячими.
У полного графа с n вершинами степень любой вершины ν
А
= n – 1,
для изолированной вершины ν
А
= 0.
Утверждение 1.1. Во всяком графе G сумма степеней всех его
вершин число четное, равное удвоенному числу ребер графа.
Доказательство. При определении степеней вершин графа каж-
дое ребро учитывается два раза, поэтому
1
2
n
i
i
p
=
ν=
∑
,
где n – число вершин, p – число ребер. ■
Утверждение 1.2. Во всяком графе с n вершинами (n ≥ 2) всегда
найдется по крайней мере две вершины с одинаковыми степенями.
Доказательство. Каждая вершина графа с n вершинами может
иметь степень 0,1,2,…, n – 1. Пусть все вершины имеют разную сте-
пень. Но этого не может быть, так как если есть вершина степени 0,
то не может быть вершины степени n – 1 (так как она может быть
соединена всего лишь с n – 2 оставшимися вершинами). Таким обра-
зом, найдутся хотя бы две вершины с одинаковыми степенями. ■
Часть вершин графа G и все инцидентные к ним рёбра образуют
подграф графа G. Если такой подграф полный, то он называется кли-
кой графа G. Очевидно, что множество подграфов определяется ко-
личеством вершин исходного графа. Все вершины и часть инци-

Страницы