ВУЗ:
Составители:
Рубрика:
92
допускается
, поскольку в получаемых при этом графах будет
отсутствовать хотя бы одна из неудаляемых дуг (их вес показан на рис.
1.11.2,в жирным шрифтом). В результате указанных упрощений
образуются графы, показанные на рис. 1.11.3,а,б.
Рис. 1.11.3. Преобразования графа с НУИ и графа с НУД
Выделим на графах рис. 1.11.3,а,б
y
-ребро с номером 6 по формуле
(1.3.2). Стягивание этого ребра на графе рис. 1.11.3,а приводит к удалению
ребер 4 и 7, как параллельных генератору и приемнику НУИ
соответственно. Аналогичная операция на графе рис. 1.11.3,б требует
удаления ребер 4 и 7, поскольку их поочередное стягивание привело бы к
удалению из графа всех НУД, что не допускается по их определению.
Производные от графов на рис. 1.11.3,а,б графы, полученные в результате
стягивания ребра 6, показаны на рис. 1.11.3,в,г соответственно. Очевидно,
определители этих графов равны
y
1
(
y
2
+
y
5
) +
y
2
y
5
.
В результате удаления ребра 6 образуются графы, показанные
на рис. 1.11.4,а,б. Рассмотрение этих графов показывает, что ребра 4 и 7 в
них требуют безусловного стягивания. Так, на рис. 1.11.4,а удаление
любого из них влечет получение вырожденного графа (∆ = 0). На рис.
1.11.4,б граф вырождается вследствие образования вершины, в которую
заходят НУД с противоположным знаками (при удалении ребра 7) или
вершины, из которой дуги только выходят (при удалении ребра 4). Таким
образом, из графов на рис. 1.11.4,а,б получаются графы, представленные
на рис. 1.11.4,в,г соответственно. Ребро 5 на рис. 1.11.4,в подлежит
удалению, как параллельное генератору (приемнику) НУИ. Аналогично
этому ребро 5 на рис. 1.11.4,г удаляется, как параллельное каждой из
оставшихся НУД. Отсюда получается, что определители графов на
рис. 1.11.4,а,б равны –
y
4
y
7
(
y
1
+
y
2
). Следовательно, искомое САД
∆
(a+b)(c+d)
=
y
6
[
y
1
(
y
2
+
y
5
) +
y
2
y
5
] –
y
4
y
7
(
y
1
+
y
2
).
а
a
b
c
d
1
2
4
5
6
7
б
a
b
c
d
1
2
4
5
6
7
1
1
-
1
-
1
в
a
b
c
d
1
2
5
г
a
b
c
d
1
2
5
1
1
-
1
Страницы
- « первая
- ‹ предыдущая
- …
- 90
- 91
- 92
- 93
- 94
- …
- следующая ›
- последняя »
