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

Страницы работы

3 страницы (Word-файл)

Содержание работы

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

 


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

Алгоритм П.

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

1

2

3

4

v

1

1

0

1

0

2

0

1

.

.

  1.  Mij = ri v rj
    (пример логического ИЛИ над двумя строками таблицы, в этом примере i=1 и j=2 – прим. Д.)
  2. В полученной строке Mij ищем Mk = 0. Если нашли, переходим к пункту 5, если все Mk = 1, то к п. 6
  3. Строим mijk и повторяем п.4,5 пока не просмотрим все нули, после чего переходим к п.8
  4. ψγ = {xi, xj, xk}
  5. В rij ищется след. rij = 0, причем такой, чтобы xj ¢ ψj. Если все rij = 1, переходим к п.8
  6. i=i+1
    Если i<n, переходим к п.2
  7. Ψ = { ψ1, ψ2, …}

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

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

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

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

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

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

 => ,  и т.д

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

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

Итого:

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

Пример:

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

x1 x2 x3 x5 x6 x7 x4

1

2

3

4

5

6

7

Pi

R=

1

0

+

1

0

0

0

+

0

2

0

+

1

0

1

0

2

3

0

+

1

1

1

4

4

0

+

0

1

3

5

0

+

1

2

6

0

+

7

0

P(G) = 11

x1 x2 x3 x4 x5 x6 x7

 


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

1

2

3

4

5

6

7

Ψ1 = {U13, U37, U36, U35}

Ψ2 = {U13, U47, U37, U57}

Ψ3 = {U26, U24}

Ψ4 = {U26, U36, U35}

Ψ5 = {U24, U47, U57}

 
8

R=

1

1

1

1

0

0

0

0

0

2

1

1

0

1

0

0

1

1

3

1

0

1

1

1

1

0

0

4

0

1

1

1

0

0

0

0

5

0

0

1

0

1

0

1

1

6

0

0

1

0

0

1

1

0

7

0

1

0

0

1

1

1

0

8

0

1

0

0

1

0

0

1

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

Ψ1 и Ψ5

 
 


I=3; r3 v r7 = M37 = 11111110

M378 = 11111111

A=

Ψ1

Ψ2

Ψ3

Ψ4

Ψ5

Ψ1

0

6

6

5

7

Ψ2

0

6

7

6

Ψ3

0

4

4

Ψ4

0

6

Ψ5

0

G` \ H = {X2, X6}

 

Похожие материалы

Информация о работе