Структурные модели сложности орграфов

программный орграф модель сложность Кроме моделей СС в виде индексов и вектор-индексов, реализованы и более сложные структурные модели сложности — b-модели в базисе ОЦФ. Данный класс моделей СС впервые предложен Коховым В. А. [Кохов, 2002]. b-модель представляет собой двудольный граф со структурными весами на вершинах и рёбрах [Незнанов, 2005]. Левая доля — элементы базиса (то есть типы фрагментов орграфа); правая доля — помеченные фрагменты; ребро проводится в случае, если помеченный фрагмент, задаваемый весом вершины левой доли вкладывается во фрагмент, тип которого совпадает с типом, задаваемым весом вершины правой доли. Веса рёбер отражают либо число вложений, либо относительные вклады помеченных фрагментов в общую сложность орграфа. В сравнении с индексами и вектор-индексами СС b-модели имеют намного большую дискриминирующую способность, позволяют решать новые классы задач, но требуют больше памяти и имеют большую сложность построения. В таблице 3 приведен пример графов с эквивалентными значениями индекса СС ISSC (G₁/OCF) = ISSC (G₂/OCF) = 43, но имеющие различные b-модели. Прорисовка диаграмм выполнена идентичным методом для визуального сравнения.

Табл. 3.

Диаграмма графа G1.	Диаграмма графа G2.
Диаграмма b-модели графа G1.	Диаграмма b-модели графа G2.