4551
правка
Технологическое отображение последовательной схемы: различия между версиями
Перейти к навигации
Перейти к поиску
м
Технологическое отображение последовательной схемы (посмотреть исходный код)
Версия от 14:06, 1 апреля 2019
, 1 апреля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
Пусть <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>(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 c^{d_t}_t | c_1 \in C(u_1), ..., c_t \in C(u_t), | c^{d_1}_1 \cup ... \cup c^{d_t}_t | \le K \}</math> | <math>\{ \{ v^0 \} \} \cup \{ c^{d_1}_1 \cup ... \cup c^{d_t}_t | c_1 \in C(u_1), ..., c_t \in C(u_t), | c^{d_1}_1 \cup ... \cup c^{d_t}_t | \le K \}</math>, | ||
где | где <math>c^{d_i}_i = \{ u^{d + d_i} | u^d \in c_i \}</math> для i = 1.. t. Очевидно, что <math>merge(C(u_1), ..., C(u_t))</math> является множеством K-разрезов для v. | ||
| Строка 50: | Строка 50: | ||
На рис. 4 изображены итерации перечисления 3-разрезов для схемы на рис. 1 (1) при слиянии разрезов в порядке i, x, y, z, o. В начале работы каждая вершина имеет собственный тривиальный разрез, включающий ее саму. В ряду 1 представлены новые разрезы, обнаруженные на первой итерации. На второй итерации обнаруживаются еще два новых разреза (для x). После этого выполнение процедуры останавливается, так как последующие слияния не приводят к выявлению новых разрезов. | На рис. 4 изображены итерации перечисления 3-разрезов для схемы на рис. 1 (1) при слиянии разрезов в порядке i, x, y, z, o. В начале работы каждая вершина имеет собственный тривиальный разрез, включающий ее саму. В ряду 1 представлены новые разрезы, обнаруженные на первой итерации. На второй итерации обнаруживаются еще два новых разреза (для x). После этого выполнение процедуры останавливается, так как последующие слияния не приводят к выявлению новых разрезов. | ||
FindAllCuts(N, K) | '''FindAllCuts'''(N, K) | ||
foreach | '''foreach''' вершины v в N '''do''' <math>C(v) \Leftarrow \{ \{ v^0 \} \}</math> | ||
while (находятся новые разрезы) do | '''while''' (находятся новые разрезы) '''do''' | ||
foreach | '''foreach''' вершины v в N '''do''' <math>C(v) \Leftarrow merge(C(u_1), ..., C(u_t))</math> | ||
Рисунок 3. Процедура перечисления разрезов | Рисунок 3. Процедура перечисления разрезов | ||