ВУЗ:
Составители:
Рубрика:
Глава 1. Основные понятия теории графов 25
пенью входа) ν – число входящих дуг. Очевидно, что в графе⎯G для
изолированной вершины степень входа и степень выхода равны ну-
лю. Если в вершине графа есть только выходящие дуги, то она назы-
вается источником, если есть только входящие дуги, то она называ-
ется стоком. На рис. 1.26 вершина С является стоком, а вершина В –
источником.
Путем в графе⎯G от вершины А
1
к А
n
называется последователь-
ность ориентированных ребер (А
1
, А
2
), …, (А
n–1
, A
n
) такая, что конец
каждого предыдущего совпадает с началом следующего. Очевидно,
что если в⎯G есть путь от А и В, то пути В к А может не быть. Если
существует ориентированный путь от A к В, то говорят, что B дос-
тижима из А. Длина пути измеряется числом дуг в пути. В графе⎯G
расстояние d(A, B) от вершины А до В, определяется длиной крат-
чайшего пути от А до В. Если пути от А к В нет (вершина В не дос-
тижима из А), то длина пути между этими вершинами считается бес-
конечной (d(A, B) = ∞). Например, у графа на рис. 1.28 d(A, B) = 1,
d(C, B) = 2, d(B, C) = ∞.
AB
С
D
E
Рис. 1.28
Очевидно, что можно провести аналогию между понятием пути и
цепи в неориентированном графе. Для орграфов цепь называется
путем, простая цепь – простым путем, цикл (замкнутая цепь) –
контуром, а простой цикл – простым контуром.
Орграф называется сильным (сильно связным), если любые две
его вершины достижимы друг для друга и односторонним, если для
любой пары его вершин, по меньшей мере, одна достижима из дру-
гой.
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
