4551
правка
Технологическое отображение последовательной схемы: различия между версиями
Материал из WEGA
Технологическое отображение последовательной схемы (посмотреть исходный код)
Версия от 13:59, 1 апреля 2019
, 1 апреля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Булева сеть может быть представлена в виде ориентированного графа со взвешенными ребрами, вершинами которого являются логические вентили, первичные входы и первичные выходы. Существует ориентированное ребро (u, v) с весом d, если u, после прохода через d триггеров, воздействует на v. | Булева сеть может быть представлена в виде ориентированного графа со взвешенными ребрами, вершинами которого являются логические вентили, первичные входы и первичные выходы. Существует ориентированное ребро (u, v) с весом d, если u, после прохода через d триггеров, воздействует на v. | ||
Логический конус для вершины может быть представлен в виде разреза, состоящего из входов конуса. Элемент разреза для v состоит из задающей вершины u и суммарного веса d на путях из u в v, обозначаемого | Логический конус для вершины может быть представлен в виде разреза, состоящего из входов конуса. Элемент разреза для v состоит из задающей вершины u и суммарного веса d на путях из u в v, обозначаемого <math>u^d</math>. Если u достигает v по нескольким путям с разным числом вентилей, u будет входить в разрез несколько раз с разными значениями d. К примеру, для конуса для z на рис 2 (2) соответствующий разрез будет иметь вид <math>\{ z^1, a^1, b^1 \}</math>. Разрез размера K называется K-разрезом. | ||
Пусть ( | Пусть <math>(u_i, v)</math> – ребро в N с весом <math>d_i</math>, а <math>C(u_i)</math> – множество K-разрезов для <math>d_i</math>, i = 1, ..., t. Обозначим за <math>merge(C(u_1), ..., C(u_t))</math> следующую операцию на множествах: | ||
<math>\{ \{ v_0 \} \} \cup \{ c^{d_1}_1 \cup ... \cup </math> | |||
где cdii = fud+di jud 2 cig для i = 1.. t. Очевидно, что merge(C(u1).. C(ut)) является множеством K-разрезов для v. | где cdii = fud+di jud 2 cig для i = 1.. t. Очевидно, что merge(C(u1).. C(ut)) является множеством K-разрезов для v. | ||
