ВУЗ:
Составители:
Рубрика:
17
другого
,
путешествуя
(
перемещаясь
)
по
смежным
ветвям
.
В
частном
случае
достижимыми
являются
узлы
ветви
.
Если
все
пары
узлов
некоторой
схемы
достижимы
,
то
схема
на
-
зывается
связной
.
Несвязную
схему
можно
представить
в
виде
двух
или
более
схем
,
называемых
компонентами
связности
схемы
.
В
каждой
компоненте
все
пары
узлов
связаны
отношением
достижимости
.
Вырожденным
случаем
компоненты
является
изолированный
узел
,
который
считается
простейшим
случаем
связной
схемы
.
Некоторое
подмножество
узлов
и
ветвей
схемы
называется
ее
подсхемой
.
Таким
образом
,
подсхема
рассматриваемой
схемы
может
быть
несвязной
и
,
в
предельном
случае
,
пустой
схемой
,
то
есть
схемой
без
элементов
.
Любую
схему
можно
считать
подсхемой
другой
,
более
сложной
схемы
.
Подмножества
ветвей
схемы
могут
образовывать
сечения
и
контуры
.
Сечение
(
обобщенный
узел
связной
схемы
) –
это
подсхема
,
при
удалении
ветвей
которой
из
исходной
схемы
получаются
две
компоненты
связности
.
При
этом
ни
одно
подмножество
ветвей
сечения
в
случае
удаления
их
из
первоначальной
схемы
не
обеспечивает
получение
несвязной
схемы
.
В
простейшем
случае
сечение
образуют
ветви
,
примыкающие
к
одному
из
узлов
схемы
.
Удаление
этих
ветвей
делит
схему
на
две
подсхемы
,
одна
из
которых
является
отдельным
(изолированным) узлом
.
K
-
разделимая
схема
–
это
схема
,
которая
утрачивает
связность
или
преобразуется
в
изолированный
узел
при
удалении
из
нее
по
меньшей
мере
K
узлов
с
инцидентными
ветвями
.
Число
K
называется
числом
разделимости
графа
.
При
K
= 1
получаем
схему
,
называемую
шарнирной
.
Подсхемы
этой
схемы
,
имеющие
только
один
общий
(
шарнирный
)
узел
,
также
называются
шарнирными
.
Частными
случаями
шарнирной
схемы
являются
дерево
(
мультидерево
),
схема
с
разомкнутой
ветвью
(
мультиветвью
)
и
схема
с
мостом
.
Степень
одного
из
узлов
разомкнутой
ветви
равна
единице
.
Мостом
называется
ветвь
или
мультиветвь
,
оба
узла
которой
являются
шарнирными
.
Узлы
,
которые
разделяют
схему
на
несвязные
части
,
называются
узлами
расчленения
исходной
схемы
или
внешними
узлами
(
полюсами
)
подсхем
,
получаемых
в
результате
ее
расчленения
по
этим
узлам
.
При
этом
оставшиеся
узлы
подсхем
будем
называть
их
внутренними
узлами
.
В
случае
2-
разделимой
схемы
имеем
два
полюса
,
поэтому
образующиеся
подсхемы
,
сочленение
которых
приводит
к
исходной
схеме
,
называются
двухполюсными
схемами
или
просто
двухполюсниками
.
Расчленение
схемы
на
две
части
называется
его
бисекцией
.
Контуром
называется
схема
,
имеющая
одинаковое
число
узлов
и
ветвей
,
удаление
любой
ветви
которого
приводит
к
образованию
путевого
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
