1. Разбиение графа на планарные суграфы

При разработке топологии возникает задача выделения из графа, описывающего схему, максимальных планарных суграфов (добавление любого ребра делает его непланарным).

Граф G(X,U) называется m-планарным, если существует m планарных суграфов L₁(X,Z₁), L₂(X,Z₂),…, L_m(X,Z_m), таких, что Наименьшее m называется толщиной графа.

8.1.1. Построение графа пересечений g’

Приняты следующие допущения:

1. Граф G имеет гамильтонов цикл;

2. Два ребра пересекаются только один раз;

3. Ребра, инцидентные одной вершине, не пересекаются;

4. Ребра графа не пересекают ребер гамильтонова цикла;

5. Ребра вершины х_j могут пересекать ребра вершины x_i при условии, что

j >i.

Рассмотрим некоторый граф G(X,U) (рис. 8.1).

p_i – число пересечений

ребер i-ой вершины.

. . .

Рисунок 8.1. Граф G(X,U)

Согласно п. 5 принятых допущений p₁=0.

Рассмотрим ребро (x₂x_n). Число его пересечений с ребрами вершины x₁

Ребро (x₂x_n-1) пересекает

ребер.

Общее число пересечений ребер вершины x₂

Для вершины x_k

Общее число пересечений ребер графа

Проще определять число пересечений по матрице соединений R. Будем использовать треугольную часть матрицы. Учитывая, что ребра графа не пересекают ребер гамильтонова цикла, в матрице R единицы, соответствующие гамильтонову циклу, заменим на "×".

		1	2	3	…	n-1	n
	1	0	×		R2n		×
	2		0	×			r2n
R(G)=	3			0	×
	...					×
	n-1					0	×
	n						0

Определим p_2n, для чего в матрице R выделим подматрицу R_2n. Сумма единиц подматрицы R_2n соответствует p_2n. Для p_2(n-1) выделим R_2(n-1) и т.д. от R_2n до R_(n-2)n. Одновременно строим граф пересечений G^'. Ребра графа G, не имеющие пересечений в G^' не учитываются. Для определения двудольности G^' используем максимальные внутренне устойчивые множества.

8.1.2. Нахождение максимальных внутренне устойчивых множеств

Для нахождения МВУМ при раскраске графа применялся метод Магу. Рассмотрим другой алгоритм, а именно - модифицированный алгоритм Г.А. Петухова.

1. В матрице R заменим все диагональные элементы на "1", r_jj =1. Положим i=1, α=1;

2. В i-той строке находим элементы r_ij = 0 (j>i). Номера нулевых элементов помещаем в список J(j). Если все r_ij =1, то ψ_α={x_i}, α= α+1, перейти к п.7;

3. Записываем дизъюнкцию M_ij= r_i  r_j;

4. В строке M_ij находим m_k=0 (k >j), если все m_k=1, то перейти к п. 6;

5. Записываем дизъюнкцию M_ijk= M_ij  r_k; Переходим к п. 4.

6. Если в дизъюнкции нет ни одного нулевого элемента, ψ_α={x_i, x_j, x_k…},

α = α+1.

Пока в списке J(j) есть не рассмотренные элементы, выбрать следующий нулевой элемент и перейти к п. 3;

7. Положить i= i+1, пока i<n перейти к п.2;

8. Семейство внутренне устойчивых множеств Ψ_G' построено.