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

UptoLike

ВУЗ: 

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

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

Рубрика: 

8
Рис. 1.9
● Граф G называется связным, если имеется путь между любыми двумя
его различными вершинами.
Пример. Граф на рис. 1.10 не связный. Например, нет пути из υ
0
в υ
3
и между υ
2
и υ
4
.
Рис. 1.10
Возвращаясь к рассмотрению графа на рис. 1.9, следует отметить, что
путь υ
0
υ
1
υ
2
υ
5
υ
4
υ
1
υ
2
υ
5
υ
7
можно сократить до υ
0
υ
1
υ
2
υ
5
υ
7
. Поскольку вершина
υ
1
повторялась, необходимо удалить часть пути между двумя появлениями
вершины υ
1
и после первого появления вершины υ
1
переходить сразу к υ
2
.
Таким образом, если путь включает какую-либо вершину υ
i
более чем
один раз, его можно сократить, удалив υ
i
и вершины, лежащие на пути между
двумя появлениями вершины υ
i
. Проведенные рассуждения дают возможность
сформулировать следующую теорему.
ТЕОРЕМА 1.3. Пусть G = G(V, E) – граф. Если существует путь из вер-
шины υ
i
в вершину υ
j
, тогда существует простой путь из вершины υ
i
в вершину
υ
j
.
Комбинируя определение связного графа и теорему 1.3, приходим непо-
средственно к следствию:
Следствие. Граф G является связным тогда и только тогда, когда между
любыми двумя его вершинами существует простой путь.
● Пусть G = G(V, E) – граф. Подграф G
′
графа G называется компонентой
графа G, если выполнены следующие два условия:
1. G
′
– непустой связный граф.
2. G
′′
– связный подграф графа G и G
′
≼
G
′′
, тогда G = G
′′
. Отсюда G
′′
–
максимальный связный подграф графа G.
υ
0
υ
1
υ
2
υ
3
υ
4
υ
5
υ
6
υ
7
υ
0
υ
1
υ
2
υ
3
υ
4

Страницы