ВУЗ:
Составители:
Рубрика:
82
унисторо-подобных элементов назовем неудаляемыми дугами и будем
изображать зачерненной стрелкой, чтобы отличать от обычных унисторных
дуг. Отображение НУИ с помощью неудаляемых дуг на унисторном графе
показано на рис. 1.12.1.
Рис. 1.12.1. Отображение НУИ на унисторном графе
Подсоединение к графу (обозначенному на рис. 1.12.1 овалом)
соответствует взятию суммарного алгебраического дополнения
∆(χ⇒НУИ)=
∆
(a+b)(c+d)
[41]. С математической точки зрения к нахождению суммарных
алгебраических дополнений сводятся многие другие задачи теории
электрических цепей (получение ССФ, определение чувствительности и т. д.)
[42]. По сути дела неудаляемые дуги с весами 1 и –1 были введены для
нахождения обычных алгебраических дополнений
Б.И.Блажкевичем еще в 1967
году. Ориентация ребер, исходящих из выходной вершины заземленного ОУ,
также ни что иное, как запрет на удаление дуг 1 и –1, которые отображают
передачу сигнала с неинвертирующего и инвертирующего входов ОУ.
Для иллюстрации предлагаемого алгоритма нахождения САД, который
реализован
Д.В. Шеиным в программе SYMB, рассмотрим пример получения
∆
(a+b)(c+d)
y-графа на рис. 1.12.2, а двумя способами: 1) на основе НУИ (см. рис.
1.12.2,б); 2) с помощью неудаляемых дуг (см. рис. 1.12.2,в).
Рис. 1.12.2. Пример нахождения суммарного алгебраического дополнения
Граф на рис. 1.12.2,б упрощается в результате удаления ребер 3 и 8,
стягивание которых приводит к замыканию генератора и приемника НУИ, что
не допускается по определению НУИ. Аналогично этому на графе рис. 1.12.2,в
поочередное стягивание ребер 3 и 8 влечет объединение неудаляемых дуг с
противоположным по знаку весом (1 и –1). Это не допускается, поскольку в
a
b
c
d
a
b
c
d
χ χ
-χ
-χ
χ
χ
a
b
c
d
1 2
3
4
5
6
7
8
а
б
в
a
b
c
d
12
3
4
5
6
7
8
a
b
c
d
1
2
3
4
5
6
7
8
1
1
-
1
-
1
a
c
6
6
-
1
ac
a
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
