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

UptoLike

ВУЗ: 

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

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

Рубрика: 

13
● Ориентированный путь из a в b задается последовательностью вершин
υ
0
υ
1
υ
2
… υ
n
, где a = υ
0
, b = υ
n
и (υ
i-1
, υ
i
) для 1
≤
i
≤
n – ориентированное ребро.
● Длиной ориентированного пути называется количество ориентирован-
ных ребер, входящих путь.
Пример. Для графа G, изображенного на рис. 1.22, графы на рис. 1.23 и 1.24 являются
подграфами. Ориентированные пути в G включают υ
0
υ
1
υ
2
υ
4
, υ
1
υ
2
υ
4
и υ
0
υ
3
υ
4
.
Рис. 1.22 Рис. 1.23 Рис.1.24
Теперь для заданного ориентированного графа G будет построен неори-
ентированный граф G
s
такой, что каждое ориентированное ребро G (исключая
петли) станет неориентированным ребром графа G
s
.
Пусть для каждого ориентированного графа G(V, E), E
′
= E - {( υ
,
υ) : υ
∈
V}, так что G
′
(V, E
′
) – ориентированный подграф графа G(V, E), в котором уда-
лены петли. Пусть R – симметричное замыкание множества E
′
, так что если (a,
b)
∈
E
′
, то (a, b), (b, a)
∈
R, а E
s
– множество ребер, представляющих отношение
R. В таком случае граф G
s
(V, E
s
) называется соотнесенным графом ориентиро-
ванного графа G(V, E).
● Ориентированный граф G(V, E) называется связным, если его соотне-
сенный граф является связным.
● Ориентированный граф называется сильно связным, если для любой па-
ры вершин a, b
∈
V существует ориентированный путь из a в b.
Пример. Для ориентированного графа на рис. 1.22 соотнесенным будет граф на рис.
1.25.
Рис. 1.25
υ
1
υ
0
υ
2
υ
4
υ
3
υ
1
υ
0
υ
2
υ
3
υ
0
υ
1
υ
3
υ
2
υ
4
υ
3
υ
4
υ
0
υ
2
υ
1

Страницы