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