Минимизация пересечений ребер графов

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

Пусть дан полный граф K_n = (X, U). Если его расположить на плоскости таким образом, чтобы образовалась выпуклая фигура, а вершины соединялись прямолинейными ребрами, тогда число пересечений в таких графах определится по формуле

                         Р(К_n) = ,                                (17.18)

при n ³ 4. Причем в каждой точке пересекается не более двух ребер. Тогда для K₄: P(K₄) = 1, P(K₅) = 5, P(K₆) = 15.

Любой планарный граф может быть расположен на плоскости таким образом, что все его ребра есть прямые линии.

Верхняя оценка числа скрещиваний (минимального числа пересечений полного графа) дана Гаем:

                          (17.19)

Существует гипотеза Харари – Хилла. Верхняя оценка минимального числа пересечений в полном графе (формула Гая (17.19)) является точным значением.

Самый простой путь расположения полного графа для минимизации пересечений его ребер следующий. Сначала располагаются ребра K_n, образующие ГЦ в виде выпуклой фигуры, которая разбивает плоскость на две области. Все остальные ребра K_n, образующие множество U\U_г.ц., проводятся во внешней и выпуклой областях путем чередования, т.е. подмножество U₁, инцидентное вершине x ₁ – проведем во внутренней области, подмножество U₂, инцидентное x ₂ – во внешней, U₃, инцидентное x _3, – во внутренней и т.д. Например, для графа K_n, n = 6 получим рис. 17.18.

Рис. 17.18. Граф K ₆

 

Тогда Р(K_n) при таком расположении равно 4. А число скрещиваний, согласно (17.18), запишется:

Р_min(К₆) = 3.

Опишем процедуру расположения полного графа с минимальным числом пересечений.

Выделим в K_n ГЦ и все вершины и ребра ГЦ расположим в виде выпуклой фигуры. При этом n ребер из n(n – 1)/2 ребер K_n расположено на плоскости. Оставшиеся n(n – 1)/2 – n ребер, т.е. n(n – 3)/2 ребра необходимо расположить внутри и вне выпуклой фигуры с наименьшим числом пересечений.

Проведем сначала подмножества ребер:

U _i = { u (i, i + 2), u (i - 1, i + 3),..., u (i - q + 1, i + q + 1)}, где

                                                    (17.20)

если i = 1, то i - 1 = n, i - 2 = n – 1,....

Заметим, что ребра подмножества U _i располагаются “параллельно” друг другу, не пересекаясь между собой.

Далее аналогично проводим подмножество ребер U _i ’. Очевидно, что в полном графе с любым числом вершин ребра подмножеств U _i и U _i ’ не пересекаются между собой. Увеличивая i на единицу, проведем новые подмножества ребер U _{i +1}, U _{i +1’}, которые минимальным образом пересекаются с ребрами предыдущих множеств.

Следующие подмножества ребер, которые минимальным образом пересекаются с уже расположенными, проводятся аналогично до тех пор, пока число таких подмножеств во внутренней области не будет равно

                                                      (17.21)

Остальные подмножества ребер, дополняющие граф до полного, проводятся во внешней области. То есть, начиная с подмножества U_L+1, аналогичные “параллельные” подмножества проводятся во внешней области ГЦ. При этом, если в графе К_n число вершин n – четно, то у него одинаковое число подмножеств “параллельных” ребер во внешней и внутренней областях ГЦ. Соответственно при n - нечетном в одной области будет на одно подмножество больше, чем в другой.

Информацию о расположении ребер в K_n запишем в видоизмененной матрице смежности.

Для K_n (n = 8) она запишется:

		1	2	3	4	5	6	7	8	1	2	3	4	5	6
R8 =	1	0	×					1	×							,
	2		0	×			1	1	1	×
	3			0	×	1	1	1	–	–	×
	4				0	×	1	–	–	–	–	×
	5					0	×	–	–	–	–		×
	6						0	×	–	–				×
	7							0	×						×
	8								0

а K₈, расположенный на основе матрицы R₈, имеет вид (рис. 17.19).

Рис. 17.19. Граф K ₈

Подмножества параллельных ребер имеют вид:

U₁ ­– (1,7)(2,6)(3,5),    U₅ – (1,3)(5,7)(4,8),

U₂ – (2,7)(3,6),            U₆ – (1,4)(8,5),

U₃ – (2,8)(3,7)(4,6),    U₇ – (2,4)(1,5)(8,6),

U₄ – (3,8)(4,7),            U₈ – (1,6)(2,5).

U₁, U₂, U₃, U₄ – подмножества параллельных ребер, проведенных во внутренней области. Согласно формуле (17.21), L = 4 и число подмножеств в обоих областях одинаково U₅, U₆, U₇, U₈ – подмножества параллельных ребер, проведенных во внешней области.

Величина Р(K₈) = 18, это соответствует формуле Гая (17.19) (при этом 9 пересечений внутри ГЦ и 9 пересечений вне ГЦ).

Итак, для получения расположения графа на плоскости с P_min(G) необходимо единицы и черточки матрицы размещать в соответствующих диагоналях. Число диагоналей необходимо определять по формуле (17.21). Каждая диагональ должна быть заполнена элементами полностью. Заполнение диагоналей можно начинать с любой строки матрицы.

Построим, например R₁₁. По (17.21) определим число диагоналей, соответствующих “подмножествам параллельных ребер”.

,

 

		1	2	3	4	5	6	7	8	9	10	11	1	2	3	4	5
	1	0	×								1	×						.
	2		0	×						1	1	1	×
	3			0	×				1	1	1	1	1	×
	4				0	×		1	1	1	1	1	1	–	×
R11 =	5					0	×	1	1	1	1	1	–	–	–	×
	6						0	×	1	1	1	–	–	–	–	–	×
	7							0	×	1	–	–	–	–	–
	8								0	×	–	–	–	–
	9									0	×	–	–
	10										0	×
	11											0	×

.

Построение диагоналей начнем с первой строки матрицы. Тогда по формуле (17.19) для K₁₁ получим:

.

Рассмотрим случай, когда число вершин K_n четно. Пусть имеется расположение K_n на плоскости с минимальным числом пересечений P_n,min. Заметим, что в полном графе с четным n, ребра, инцидентные вершине x_i, обладают одинаковыми свойствами по отношению к числу пересечений с ребрами инцидентными любой другой вершине x_j (i, j Î I = {1, 2,..., n}, i Ï j). Поэтому ребра, инцидентные x_i, имеют такое же число пересечений, как и ребра, инцидентные любой вершине x_j. Это вытекает из способа построения графа.

Каждое пересечение образуется наложением двух ребер, концы которых лежат в 4 вершинах. Поэтому каждое пересечение учитывается 4 раза. Общее число пересечений K_n равно

                                          .                                      (17.22)

При удалении из K_n любой вершины с инцидентными ей ребрами получим K_n-1, с минимальным числом пересечений.

Справедливость этих утверждений покажем построением видоизмененных матриц.

Например, в приведенной выше матрице R8 удалим, например, третью строку и третий столбец. Получим:

		1	2	4	5	6	7	8	1	2	4	5	6
R7 =	1	0	×				1	×						.
	2		0	×		1	1	1	×
	4			0	×	1	1	–	–	×
	5				0	×	–	–	–	–	×
	6					0	×	–	–			×
	7						0	×					×
	8							0	×

На основе R₇ построим оптимальное расположение этого графа K₇.

По формуле (17.19) имеем

.

Тогда для любого K_n с четным n запишем

                                        .                                 (17.23)

Из (17.23) получаем

                                                                          (17.24)

при n º 0 (mod 2) и n ³ 6.

Для K_n n ¹ 0 (mod 2) также имеет место выражение (17.22). Тогда

                                          .                                   (17.25)

Выражение (17.23) справедливо так как удаление вершины x_i с P_max со всеми инцидентными ей ребрами из K_n позволяет получить K_n-1 с четным числом вершин с минимумом пересечений.

На основе (17.25) и (17.22) получим

                                        .                          (17.26)

После преобразования (17.26) получим

                                                                           (17.27)

при n ¹ 0 (mod 2) и n ³ 7.

Объединяя (17.24) и (17.27) в одно выражение, получим

                                 .                             (17.28)

После преобразования (3.28) можно получить для

                         n – четного ,                 (17.29)

                         n – нечетного ,                 (17.30)

что доказывает верхнюю оценку Гая и гипотезу Харари–Хилла, о том что верхняя оценка (17.19) является точным значением.

Рассмотрим ряд эвристик, применяемых для минимизации пересечений ребер графа.

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

Э.2. В графе определяется ребро с наибольшим числом пересечений. Через него проводится секущая ось и весь граф перемещается по правую или левую часть от секущей оси. Далее процесс продолжается аналогично. При этом возможно несколько вариантов. Перед переносом графа проводить анализ: не приведет ли перемещение к увеличению числа пересечений. Тогда необходимо переходить к другой секущей оси и т.д.

Э.3. Минимизация пересечений при расположении ребер во внутренней и внешней областях ГЦ. Отсутствие ребер ГЦ позволит только уменьшить число пересечений за счет проведения некоторых ребер в том месте, где отсутствуют ребра ГЦ. Основная идея алгоритма следующая. Для обоих областей ГЦ строятся матрицы смежности. Далее определяется “отклонение” для каждого ребра G. Под отклонением ребра графа G понимается разность между числом пересечений этого ребра со всеми остальными, когда оно во внутренней и внешней областях ГЦ, затем строится матрица отклонений, из которой выбирается элемент, имеющий максимальное значение. Ребро, соответствующее этому элементу, выносится во внешнюю область ГЦ. Далее процесс продолжается аналогично, пока все элементы матрицы не станут отрицательными.

На основе эвристик разрабатываются эффективные алгоритмы минимизации пересечений ребер графовых моделей в любой области науки и производства.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Дайте определение и приведите примеры плоских и планарных графов.

2. Дайте определение плоской карты.

3. Запишите теорему Эйлера о плоской карте.

4. Дайте определение максимально планарного графа.

5. Приведите теоремы о планарности графов.

6. Каким образом можно связать понятия двойственности и планарности графов?

7. Какие графы являются гомеоморфными?

8. Поясните понятия толщины графа и числа скрещиваний.

9. Приведите эвристики для определения планарности графа.

10. Сформулируйте основную идею алгоритмов минимизации пересечений ребер графа.