Технологическое отображение ППВМ: различия между версиями

Если <math>\langle u, v \rangle \in E</math>, u называется ''разветвлением на входе'' (fanin) вершины v, а v – ''разветвлением на выходе'' (fanout) вершины u. Для вершины v обозначим за input(v) множество ее fanin; аналогичным образом для подграфа H обозначим за input(H) множество отдельных вершин вне H, являющихся fanin для вершин из H. Если существует прямой путь в N из вершины u в вершину v, u называется ''предком'' v, а v – ''потомком'' u. Входной сетью вершины v, обозначаемой <math>N_v \;</math>, является подграф, содержащий вершину v и всех ее предков. ''Конусом'' не являющейся первичным входом вершины v, обозначаемым <math>C_v \;</math>, является подграф <math>N_v \;</math>, содержащий v и, возможно, некоторых из ее предков, не являющихся первичными входами, таких, что для любой вершины <math>u \in C_v \;</math> существует путь из u в v по <math>C_v \;</math>. Если <math>|input(C_v)| \le K \;</math>, <math>C_v \;</math> называется ''K-допустимым'' конусом. Сеть N является ''K-ограниченной'', если каждая вершина, не являющаяся первичным входом, имеет K-допустимый конус. ''Разрез'' по не являющейся первичным входом вершине v представляет собой биразбиение (X, X') вершин из <math>N_v \;</math>, такое, что X' является конусом v; input(X') называется <math>сечением</math> (X, X'), а n(X, X') = |input(X')| – ''размером'' разреза. Если <math>n(X, X') \le K \;</math>, то (X, X') является ''K-допустимым'' разрезом. Обозначим ''мощность'' разреза (X, X') как vol(X, X') = |X'|.