Декомпозиция графов.

Задача декомпозиции формулируется так:задан граф, для которого необходимо определить, является ли он произведением двух графов. В случае положительного ответа нужно найти графы - сомножители.

Семантика задачи. Описана система, функционирующая во времени. Необходимо определить, нельзя ли её представить в виде системы из двух независимых блоков, как описано выше. В этом случае систему можно описать гораздо проще. Так, если система имеет 100 состояний, то при положительном решении она будет описываться как два блока, каждый из которых имеет только десять состояний.

В предыдущем разделе было показано, что если граф представим произведением, то его матрица будет иметь вид правильной клеточной матрицы.

Рассмотрим ещё раз пример, приведённый в предыдущем разделе в табл. 3.10. Предположим, что в системе состояния пронумерованы следующим образом: 1=(1aa), 2=(1bb), 3=(3bb), 4=(2bb), 5=(3aa), 6=(2aa), то естьт.е. 3-ю
и 6-ю вершины поменяем местами. Тогда таблица примет видПолучим табл. 3.11.

Эта таблица уже не будет правильной клеточной матрицей, хотя она описывает граф, совпадающий с исходным с точностью до имён вершин.

Значит, если матрица графа не является правильной клеточной матрицей, но может быть получена из неё путём переименования вершин, то такой граф будет представлять собой произведение графов.

Есть ещё один простой критерий того, что граф не является произведением. Если Q=<C,T>, G=<A,R>, H=<B,S>, и Q=GxH, то имеет место условие:

|C|=|A|×|B|. Значит, если число вершин n графа есть простое число, то он не может быть представлен произведением графов.

Если n не простое и может быть выражено как n=kr , где k и r больше 1, то можно ставить задачу проверки этого графа на возможность представить его в виде произведения. Если граф содержит n вершин, то для проверки его необходимо в общем случае провести n! переименований. Уже для n=6 это число составит 720, для n=8 уже более 40000. Поэтому возникает необходимость сокращения объёма вычислений.

Возможность сокращения основана на следующем утверждении. Если граф представлен в виде правильной клеточной матрицы, то при переименовании вершин, связанных с переименованием вершин в одном графе-сомножителе, матрица останется правильной клеточной матрицей. Точно так же, если матрица не является правильной клеточной, то перестановка имен, связанная с изменением имён в одном графе-сомножителе, её правильной не сделает. Это значит, что если n=k×r, то необходимый перебор вариантов можно сократить в k!×r! раз. Например, перебор для n=6 сократится до 60 (6=2×3, сокращение в 2!×3!=12 раз).

Алгоритм декомпозиции

Рассмотрим еще раз операцию произведения. Если вершина а в первом графе-сомножителе имеет степень захода d_aa, а вершина b во втором графе имеет степень захода d_bb, в результирующем графе вершина (a,b) будет иметь степень захода (d_aad_bb). То же самое можно сказать и о степени исхода результирующего графа.

Алгоритм основан на том, что для каждой i –той вершины графа определяются все возможные разложения её степеней захода s_i=r_i×t_i, т.е. предполагается, что если задача решается и этой вершине сопоставлена пара (х,у), то эти вершины имеют степени захода r_i и t_i соответственно. То же самое относится к степени исхода вершины i: t_i=p_i×q_i.

Проведём разложения для всех степеней вершин. Построим два разбиения вершин: разбиение на к классов по l элементов p=(p1,p2,…,pк) и разбиение на l классов по к элементов r=(r1, r2, …, rl), n=k×l, чтобы произведением этих разбиений было разбиение на одноэлементные множества.

В один класс p попадут вершины а и b, если для них в разложении r_aa=r_bb и p_aa=p_bb.

В один класс r попадут вершины а и b, если в разложениях t_aa=t_b и q_a=q_b.

Если такие разбиения построить можно, то ему сопоставляется перестановка элементов по следующему правилу. Зафиксируем порядок блоков в разбиениях p и r. Сопоставим этому порядку перестановку: вначале старшинство определяется по разбиению p, затем внутри этих блоков - по разбиению r.

Рассмотрим метод на примере. Пусть граф описывается матрицей табл. 3/.12, разложения разложения s и t приведены в этой таблице. Значение степени, равное 0, представляется произведением 0 на произвольное число, обозначаемое как х. Первой задачей является задача выбора среди разложений тех, которые приведут к разбиениям вершин по степеням исхода и захода.

При выборе разложений будем учитывать следующее.

Для вершины 4 выбираем разбиение 2×2, так как вершиныу с сомножителем 4 в пару не найти. В разложения p вершины 4 и 5 должны быть в разных блоках, так как у них обе компоненты по s разные. То же самое по отношению t для вершин 3 и 4. Значит, 3 и 5 будут в одном блоке. Вершины 3 и 6 должны быть в одном блоке по t и в разных блоках по s, 1 и 5 – в разных блоках по t, чтобы по первой компоненте их можно было объединить в разложении r. Курсивом выделены разбиения. В итоге получаем разложение p={{1,4,6}, {2,3,5}}.

После этого однозначно получаем r={{1,5},{3,6},{2,4}}.

Зафиксируем порядок в этих разбиениях. Тем самым мы предполагаем, что если решение существует, то граф можно представить произведением двух графов, один из которых содержит 2 вершины (пусть, например, вершины а и b), второй содержит три вершины (пусть, например, 1, 2 и 3). Тогда вершинам первого блока разбиения p сопоставлены элементы декартова произведения с вершиной а в качестве первого слагаемого, для вершин второго блока первым слагаемым будет b.

Аналогично в соответствующем декартовом произведении вторым сомножителем для вершин первого блока разбиения r будет вершина 1, второго блока – вершина 2, третьего блока – вершина 3. Составим разбиениям p и r упорядочение <1,4,6,5,2,3>, которое «испортило» матрицу, исправим её, используя обратное упорядочение

1 2 3 4 5 6

1 5 6 2 4 3.

Применим эту перестановку к матрице, получим табл.3.13. Как видно из таблицы, она является правильной клеточной матрицей, что приводит к решению: граф представим произведением двух графов, матрицы смежности которых легко получаются из табл. 3.13 Матрицы графов-сомножителей представлены в табл. 3.14 и 3.15.