Граф пересечений. Определение двудольности. Алгоритм Петухова Г.П. Преобразование вершин

Одновременно строится граф пересечений G`

Для определения двудольности используется максимальные внутренне устойчивые множества (их можно построить методом Магу)

Алгоритм П.

1. В матрице R заменим все диагональные элементы на единицы. r_ii = 1
2.  В i-й строке находим элемент r_ij , j>i , переходим к пункту 3.Если все r_ij =1, то к п. 6

3.  M_ij = r_i v r_j
   (пример логического ИЛИ над двумя строками таблицы, в этом примере i=1 и j=2 – прим. Д.)
   
4. В полученной строке M_ij ищем M_k = 0. Если нашли, переходим к пункту 5, если все M_k = 1, то к п. 6
5. Строим mijk и повторяем п.4,5 пока не просмотрим все нули, после чего переходим к п.8
6. ψ_γ = {x_i, x_j, x_k}
7. В r_ij ищется след. r_ij = 0, причем такой, чтобы x_j ¢ ψ_j. Если все r_ij = 1, переходим к п.8
8. i=i+1
   Если i<n, переходим к п.2
9. Ψ = { ψ₁, ψ₂, …}

Выделение из графа пересечений G` макс. двудольного подграфа H`

Для этого введем следующий критерий:

αγδ= |Ψγ| + |Ψδ| - |Ψγ∩Ψδ|

Если αγδ= |Ψγ| + |Ψδ| = |X`| , т.е.  |Ψγ∩Ψδ| = 0, то граф G` двудольный и планарный.

Если это не так, то чем αγδ ближе к к |X`|, тем большее число ребер содержи выделенный двудольный граф, т.е. необходимо найти такие γ и δ, которые дают максимальный αγδ.

Максимальному H` в исходном графе G соответствует суграф H, содержащий максимальное число непересекающихся ребер.

 => _,  и т.д

Причем матрица получается из матрицы R_G` вычеркиванием строк и столбцов, соответствующих вершинам, попавшим в Ψγ и Ψδ.

получается из Ψ_G`, выкинув вершины, вошедшие в Ψγ и Ψδ и объединив одинаковые.

Итого:

1. По матрице R находится R<sub>G`</sub> и G`
2. Выделить Ψ_G`
3. Построить A _G`
4. max αγδ, Ψγ и Ψδ
5. Вершины из Ψγ и Ψδ образуют двудольный подграф H` и планарный суграф H
6. Ψ_G` ->  ;
   Если ≠ 0, то к п.3
7. Разбиение получено.

Пример:

Граф, что и в предыдущем примере. Преобразуем: (перенумеруем вершины)

x1 x2 x3 x5 x6 x7 x4

x1 x2 x3 x4 x5 x6 x7

Если гамильтонова цикла нет, то строим цепь и достраиваем до цикла, добавляя одно или несколько псевдоребер.

I = 1 ;  r1 v r4 = M14 = 11110000

M145 = 11111011

M1456 = 11111111

r1 v r7 = M17 = 11101110

M174 = 11111110

M1748 = 11111111

I = 2 ; r2 v r3 = M23 = 11111111

r2 v r5 = M25 = 11111011

M256 = 11111111

I=3; r3 v r7 = M37 = 11111110

M378 = 11111111

G` \ H = {X2, X6}