4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 57: | Строка 57: | ||
''Таблица соединений схемы'' определяется как диграф N = (V, E), где V – множество вершин, представляющих логические вентили и регистры, а E – множество ребер, представляющих провода между вентилями и регистрами. Каждая вершина <math>v \in V \;</math> имеет вес <math>w(v) \in R^+ \;</math>. Общий вес подмножества <math>U \subseteq V \;</math> определяется как <math>w(U) = \sum_{v \in U} w(v) \;</math>. W = w(V) обозначает полный вес схемы. Сетка <math>n = (v, v_1, ..., v_l) \;</math> представляет собой множество ребер, исходящих из вершины v в N. Пусть даны две вершины s и t в N; ''s-t-разрез'' (далее для краткости просто «[[разрез]]») <math>(X, \bar{X}) \;</math> графа N представляет собой биразбиение вершин V, такое, что <math>s \in X \;</math> и <math>t \in \bar{X} \;</math>. ''Сетевым разрезом'' <math>net(X, \bar{X}) \;</math> разреза является множество сеток в N, инцидентных вершинам одновременно в <math>X \;</math> и <math>\bar{X} \;</math>. Разрез <math>(X, \bar{X}) \;</math> является ''минимальным сетевым разрезом'', если значение <math>|net(X, \bar{X})| \;</math> минимально среди всех s-t-разрезов N. На рис. 3 представлены сетка <math>a = (r_1 | ''Таблица соединений схемы'' определяется как диграф N = (V, E), где V – множество вершин, представляющих логические вентили и регистры, а E – множество ребер, представляющих провода между вентилями и регистрами. Каждая вершина <math>v \in V \;</math> имеет вес <math>w(v) \in R^+ \;</math>. Общий вес подмножества <math>U \subseteq V \;</math> определяется как <math>w(U) = \sum_{v \in U} w(v) \;</math>. W = w(V) обозначает полный вес схемы. Сетка <math>n = (v, v_1, ..., v_l) \;</math> представляет собой множество ребер, исходящих из вершины v в N. Пусть даны две вершины s и t в N; ''s-t-разрез'' (далее для краткости просто «[[разрез]]») <math>(X, \bar{X}) \;</math> графа N представляет собой биразбиение вершин V, такое, что <math>s \in X \;</math> и <math>t \in \bar{X} \;</math>. ''Сетевым разрезом'' <math>net(X, \bar{X}) \;</math> разреза является множество сеток в N, инцидентных вершинам одновременно в <math>X \;</math> и <math>\bar{X} \;</math>. Разрез <math>(X, \bar{X}) \;</math> является ''минимальным сетевым разрезом'', если значение <math>|net(X, \bar{X})| \;</math> минимально среди всех s-t-разрезов N. На рис. 3 представлены сетка <math>a = (r_1; g_1, g_2) \;</math>, сетевые разрезы <math>net(X, \bar{X}) = \{ b, e \} \;</math> и <math>net(Y, \bar{Y}) = \{ c, a, b, e \} \;</math> и минимальный сетевой разрез <math>(X, \bar{X}) \;</math>. | ||
Говоря формально, пусть даны пропорция r и коэффициент отклонения | Говоря формально, пусть даны пропорция <math>r \;</math> и коэффициент отклонения <math>\epsilon \;</math>. Задача ''r-сбалансированного биразбиения с минимальным разрезом'' заключается в нахождении биразбиения <math>(X, \bar{X}) \;</math> таблицы соединений N, такого, что (1) <math>(1 - \epsilon) rW \le W(X) \le (1 + \epsilon) rW \;</math> и (2) размер разреза <math>net(X, \bar{X}) \;</math> минимален среди всех разрезов, удовлетворяющих условию (1). Если r = 1/2, задача превращается в задачу сбалансированного биразбиения с минимальным разрезом. | ||
== Основные результаты == | == Основные результаты == |
правок