Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Б) відскановану (сфотографовану) квитанцію про сплату організаційного внеску.
  2. Б) відскановану (сфотографовану) квитанцію про сплату організаційного внеску.
  3. Минимизация издержек и оптимум производителя
  4. Минимизация числа состояний абстрактного автомата
  5. Мнение биографов и ученых (но не всех)
  6. Объем прямоугольного параллелепипеда равен 2520 см(в кубе),а площадь основания 168 см(в квадрате),и длина на 2 см больше ширины. Найдите сумму длин всех ребер параллелепипеда.

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

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

Р(Кn) = , (17.18)

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

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

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

(17.19)

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

Самый простой путь расположения полного графа для минимизации пересечений его ребер следующий. Сначала располагаются ребра Kn, образующие ГЦ в виде выпуклой фигуры, которая разбивает плоскость на две области. Все остальные ребра Kn, образующие множество U\Uг.ц., проводятся во внешней и выпуклой областях путем чередования, т.е. подмножество U1, инцидентное вершине x 1 – проведем во внутренней области, подмножество U2, инцидентное x 2 – во внешней, U3, инцидентное x 3, – во внутренней и т.д. Например, для графа Kn, n = 6 получим рис. 17.18.

Рис. 17.18. Граф K6

 

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

Рmin6) = 3.

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

Выделим в Kn ГЦ и все вершины и ребра ГЦ расположим в виде выпуклой фигуры. При этом n ребер из n(n – 1)/2 ребер Kn расположено на плоскости. Оставшиеся 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)

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

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

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

                                 
R8 =     ×           ×             ,
      ×           ×          
        ×       ×        
          ×   ×      
            ×   ×    
              ×       ×  
                ×           ×
                             

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

Рис. 17.19. Граф K8

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

U1 ­– (1,7)(2,6)(3,5), U5 – (1,3)(5,7)(4,8),

U2 – (2,7)(3,6), U6 – (1,4)(8,5),

U3 – (2,8)(3,7)(4,6), U7 – (2,4)(1,5)(8,6),

U4 – (3,8)(4,7), U8 – (1,6)(2,5).

U1, U2, U3, U4 – подмножества параллельных ребер, проведенных во внутренней области. Согласно формуле (17.21), L = 4 и число подмножеств в обоих областях одинаково U5, U6, U7, U8 – подмножества параллельных ребер, проведенных во внешней области.

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

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

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

,

 

                                     
      ×                 ×           .
        ×                 ×        
          ×                 ×      
            ×               ×    
R11 =             ×           ×  
                ×       ×
                  ×      
                    ×      
                      ×        
                        ×          
                          ×        
.

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

.

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

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

. (17.22)

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

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

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

                             
R7 =     ×         ×           .
      ×         ×        
        ×     ×      
          × ×    
            ×     ×  
              ×         ×
                ×        

На основе R7 построим оптимальное расположение этого графа K7.

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

.

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

. (17.23)

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

(17.24)

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

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

. (17.25)

Выражение (17.23) справедливо так как удаление вершины xi с Pmax со всеми инцидентными ей ребрами из Kn позволяет получить Kn-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. Сформулируйте основную идею алгоритмов минимизации пересечений ребер графа.


Дата добавления: 2015-10-26; просмотров: 428 | Нарушение авторских прав


Читайте в этой же книге: ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Геометрический метод решения | Расстояния на графах | ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Цикломатическое и хроматическое числа графа | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Числа внутренней и внешней устойчивости графа | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Нечеткие ориентированные графы |
<== предыдущая страница | следующая страница ==>
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ| Способы задания

mybiblioteka.su - 2015-2024 год. (0.014 сек.)