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

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

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.

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

Одновременно строится граф пересечений 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}

 

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

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

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.