Кластеризация на основе эффективности: различия между версиями

Пусть Г = (H= (У,Е'),ф,Е) – кластеризация G. Для v 2 V, v0 2 V0, в случае, если ф{у') = v, мы называем v0 копией v. Множество V0 состоит из всех копий вершин из V, встречающихся в кластеризации. Вершина v0 является первичным входом (первичным выходом, соответственно) кластеризации Г, если ф{у') является первичным входом (первичным выходом) сети G. Из определения ' следует, что H логически эквивалентна G.

Веса и задержки отдельных вершин G позволяют определить веса и задержки вершин H0 и задержку для кластеризации Г. Вес (соответственно, задержка) вершины v0 в V0 равен весу (задержке) ф(v). Вес любого кластера C 2 £, обозначаемый W(C), равен сумме весов вершин C. Задержка кластеризации определяется согласно обобщенной модели, предложенной Мургаи и коллегами [ ]: Задержка ребра (u0; v0) 2 E0 равна D (заданному параметру), если u0 и V принадлежат к разным элементам S, и нулю в противном случае. Задержка по пути в H0 равна сумме задержек ребер, составляющих путь. Наконец, задержка Г равна задержке пути в H0, имеющего максимальную задержку среди всех путей из PI в PO по H0.

Определение 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией w: V !>• R+, весовой емкостью M и функцией задержки 8: V !>■ R+. Мы говорим, что кластеризация Г = (Н,ф,Е) является допустимой, если для каждого кластера C 2 S значение W(C) не превышает M. Задача кластеризации схемы заключается в вычислении допустимой кластеризации Г сети G, такой, что задержка Г минимальна среди всех допустимых кластеризаций G.