ВУЗ:
Составители:
Рубрика:
вершин с нечетной степенью должно быть четно.
Определение. Граф называется полным, если любые две его
вершины смежны. Полный граф с n вершинами имеет ребер.
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2
n
Определение.
Рассмотрим граф G=(V,E). Граф G
1
=(V
1
,E
1
) назы-
вается подграфом G=(V,E) тогда и только тогда, когда
1. V
1
⊆
V, E
1
⊆
E
2. Если ребро e
∈
E
1
инцидентно вершинам u и v
∈
V
1
, то ребро
e
∈
E, также инцидентно вершинам u,v
∈
V.
Маршруты, цепи, циклы
Определение. Конечная последовательность ребер e
1
, e
2
,…, e
n
графа G=(V,E) (не обязательно различных) называется маршрутом
длины n, если существует последовательность v
0
,v
1
,…,v
n
вершин
(не обязательно различных) таких, что e
i
инцидентно
1
(,),1,
ii
vvi n
−
= .
. Маршрут замкнут, если v
0
=v
n
(циклический мар-
шрут).
Определение
. Маршрут называется цепью, если все его ребра
различны и простой цепью, если все его вершины различны (в
этом случае и все ребра различны)
Определение.
Замкнутая цепь называется циклом и простым
циклом, если никакие вершины в ней не повторяются.
Связность
Определение . Граф G=(V,E) называется связным, если каждая
пара различных вершин может быть соединена, по крайней мере,
одной цепью. В противном случае граф называется несвязным.
Теорема.
Граф G=(V,E) связен тогда и только тогда, когда мно-
жество его вершин нельзя разбить на два непустых подмножества
V
1
и V
2
так, что обе граничные точки каждого ребра находятся в
одном и том же подмножестве.
Доказательство.
Пусть G несвязен. Выберем произвольную
вершину v
1
и пусть множество V
1
состоит из вершины v
1
вместе со
всеми вершинами, которые могут быть соединены с v
1
цепью. Т.к.
G несвязен, то V
1
≠
V. Поэтому дополнение V
2
=V-V
1
не пусто. По
построению множества V
1
ни одно ребро не соединяет вершину из
V
1
ни с одной вершиной из V
2
, т.е. получаем разбиение из форму-
лировки.
28
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »
