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

UptoLike

ВУЗ: 

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

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

Рубрика: 

7
сумма степеней всех вершин нечетная. Но это противоречит теореме 1.1., по-
этому мы пришли к противоречию. Следовательно, теорема справедлива.
● Граф G
′
(V
′
, E′) называется подграфом графа G(V, E), обозначается
G′(V′, E′)
p G(V, E), если V′ ⊆ V, E
′
⊆ E.
Таким образом, каждая вершина в G
′
является вершиной в G, и каждое
ребро в G′ является ребром в G.
Пример. Графы, изображенные на рис. 1.5, 1.6, 1.7, являются подграфами графа на
рис.1.8.
●
Рис. 1.5 Рис. 1.6 Рис. 1.7 Рис. 1.8
Путь (маршрут) в графе – это совокупность ребер, которые объединены
вместе с вершинами так, что вдоль них можно двигаться по графу. Для удобст-
ва договоримся использовать символы υ
0
, υ
1
, υ
2
, υ
3
, …, υ
k
, u и υ для обозначения
вершин.
● Пусть G = G(V, E) – граф с вершинами υ
0
, υ
1
, …, υ
k
∈
V и ребрами e
1
, e
2
,
…, e
k
∈ E.
Путем длины k из υ
0
в υ
k
(или между υ
0
и υ
k
) называется последователь-
ность υ
0
e
1
υ
1
e
2
υ
2
e
3
υ
3
… υ
k
e
k
υ
k
такая, что e
i
= {υ
i-1
υ
i
}. Путь длины k имеет k
ребер.
В общем случае путь будет обозначаться через υ
0
, υ
1
, υ
2
, …, υ
k
.
Каждые два последовательных ребра пути имеют общую вершину, по-
этому являются смежными.
● Простым путем из υ
0
в υ
k
называется путь, в котором нет повторяю-
щихся вершин.
Пример. В графе, изображенном на рис. 1.9.
Из υ
0
в υ
7
ведут пути υ
0
υ
1
υ
2
υ
5
υ
7
,
υ
0
υ
1
υ
2
υ
5
υ
4
υ
1
υ
2
υ
5
υ
7
,
υ
0
υ
1
υ
4
υ
5
υ
4
υ
5
υ
7,
υ
0
υ
3
υ
4
υ
6
υ
7
длины 4, 8, 6 и 4 соответственно. Пути υ
0
υ
1
υ
2
υ
5
υ
7
и υ
0
υ
3
υ
4
υ
6
υ
7
являются простыми.
a b c
d e ƒ
c
a
d e ƒ d
b c a
e
a
d
e ƒ
b c

Страницы