ВУЗ:
Составители:
Рубрика:
Последовательность обхода вершин "а-б-в-г" вместе с соответствующими ребрами называется пу-
тем "а-б-в-г".
Если существует путь из вершины "а" в вершину "г", то говорят, что "г" достижима из вершины
"а". Если такого пути нет, то вершина "г" не достижима из вершина "а".
Рис. 1.5 Путь на графе
а)
б)
Рис. 1.6 Подграфы:
а – связанные; б – изолированные
Если между вершинами "а" и "б" существует путь, говорят, что эти вершины связаны.
Часть графа называется подграфом. Если хотя бы одна вершина подграфа А связана с вершиной
подграфа В, то говорят, что эти подграфы связаны (рис. 1.6, а). Если же ни одна вершина подграфа А не
связана ни с одной вершиной подграфа В, то говорят, что эти подграфы изолированы (рис. 1.6, б).
Пути графа классифицируют, на рис. 1.7 представлена классификация этих путей.
Пути делятся на цепи и не цепи.
Цепь (рис. 1.8) отличается тем, что в ней нет общих ребер. Так, "а-б-в-г-д-в-б-е" (рис. 1.8, б) не яв-
ляется цепью, так как ребро s между "б" и "в" проходится дважды.
Путь "а-б-в-г-д-в-с" (рис. 1.8, а) является цепью.
Рис. 1.7 Классификация путей
а
в
г
б
ПУТЬ
ÑËÎÆÍÛÉ
ÖÈÊË
ÍÅ ÄÓÃÀ (ÏÓÒÜ)
ДУГА
ПРОСТОЙ
ЦИКЛ
ЦЕПЬ
НЕ ЦЕПЬ (путь)
ЦИКЛ
ÍÅ ÖÈÊË
s
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
