Материал: Алгоритм распознавания единичного интервального графа

Алгоритм распознавания единичного интервального графа

Введение

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

Интервальные графы - один из типов графов пересечений. Целью данной дипломной работы является изучить алгоритмы распознавания интервальных и единичных интервальных графов, реализовать их в виде компьютерной программы и провести тестовые расчеты на графах.

Интервальный граф - граф пересечений множества интервалов на прямой. Иными словами, вершинами интервального графа являются некоторые интервалы на прямой и любые две вершины соединяются ребром, если и только если соответствующие им интервалы пересекаются.

Рис.1 - Пример интервального графа

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

Единичные интервальные графы - граф пересечений интервалов одинаковой длины.

Применение интервальных графов:

Графы интервалов рассматривались для построения моделей

в биологии [1]

- при построении модели ДНК - участки ДНК, за которые отвечают разные гены, могут пересекаться;

в археологии[1]

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

для транспортных потоков[1]

- задача регулирования светофором движения транспорта на перекрестке.

И т.д.

В работе [2] D. G. Corneil был предложен трехмаховый (трехпроходный) алгоритм для распознавания единичных интервальных графов. Вершины графа упорядочиваются с помощью лексикографического поиска в ширину [3] в некоторую последовательность. Полученный порядок вершин проверяется на соответствие совершенному порядку исключения вершин [4] и делается вывод о том, является ли граф единичным интервальным. Для распознавания интервальных графов были предложены различные многомаховые алгоритмы, например в работе [5] предложен шестимаховый алгоритм, а в работе [6] четырехмаховый. В некоторых случаях алгоритм с сортировкой [7] может быть более эффективным, чем лексикографический поиск в ширину.

Задачи данной работы:

1. Изучить алгоритм распознавания единичного интервального графа с помощью трех проходов алгоритма лексикографического поиска.

2. Изучить алгоритм 4-махов для распознавания интервальных графов.

3. Реализовать алгоритмы в виде компьютерной программы.

4. Провести тестовые расчеты на графах (на корректность алгоритмов и на время работы алгоритмов).

1.      Некоторые сведения из теории графов

Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6].

Граф, или обыкновенный граф G - это упорядоченная пара G := (V, E), где V - это непустое множество вершин или узлов, а E - множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами.

Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| - порядком, число рёбер |E| - размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e={u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

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

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

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

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

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

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

Астероидальной тройкой (АТ) называются три вершины графа, что каждая пара таких вершин соединяется путём, не проходящим через замкнутую окрестность третьей вершины.

Теорема 1. Граф интервальный тогда и только тогда, когда он хордален и не содержит астероидальных троек [10].

Четыре вершины графа порождают клешню с центром в вершине , если  - три попарно несмежных соседа вершины .

Теорема 2. Интервальный граф является единичным интервальным тогда и только тогда, когда он не содержит порождённых клешней [11].

Единичный интервальный граф - граф пересечений интервалов одинаковой длины.

Пусть  граф с  вершинами и  порядок (последовательность) вершин . Порядок называется I-порядком графа, если для всех  и , выполняется  для всех . Порядок называется UI-порядком графа если  для всех .

Теорема 3. Граф интервальный тогда и только тогда, когда у него имеется I-порядок [12].

Теорема 4. Граф единичный интервальный тогда и только тогда, когда у него имеется UI-порядок [13].

Примеры некоторых различных типов графов:

)        Хордальный, не являющийся интервальным. (bdf астероидальная тройка - есть пути соединяющие каждую пару, не проходящие через закрытое множество соседей, Рис.2).

Рис.2

)        Интервальный, не являющийся единичным интервальным (клешня, попарно несмежные соседи - не соединяются ребрами, Рис.3).

Рис.3

)        Единичный интервальный (самый простой пример, Рис.4)

Рис.4

2.      Алгоритмы распознавания интервальных графов

Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке полученной последовательности вершин на условия UI или I порядка. В зависимости от типа графа используемые алгоритмы требуют различных дополнительных условий упорядочивания вершин графа.

2.1    Алгоритм поиска в ширину (BFS)

Данный алгоритм (англ. Breadth-First Search - BFS) позволяет упорядочить вершины графа в некоторую последовательность подмножеств. Суть алгоритма поиска в ширину в том, что начиная с заданной вершины, по очереди рассматриваем ее соседей, потом рассматриваем соседей ее соседей и т.д. (Рис.5)

Рис.5 - Порядок обхода вершин графа при алгоритме BFS: e [f d] [a b c]

Начиная с заданной вершины (первое подмножество с одной вершиной - вершина e) выбираются соседи данной вершины (второе подмножество - вершины f и d), затем соседи соседей (третье подмножество - вершины a,b,c) и так далее. В итоге все вершины образуют некоторую упорядоченную последовательность подмножеств. Следует отметить, что в каждом подмножестве вершины не упорядочены.

интервальный граф алгоритм программа

2.2    Поиск в ширину с дополнительной сортировкой (MNS)

Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных подмножествах алгоритма BFS (Рис.6). Для этого на этапе поиска соседей для каждой найденной вершины в новом подмножестве также суммируется число рёбер из текущего подмножества вершин. Сортируя вершины подмножества по данному параметру, получаем упорядоченную последовательность вершин в подмножестве.

Рис.6 - Порядок обхода вершин графа при алгоритме MNS: e [f d] b [a c]

На Рис.6 для третьего подмножества (a b c) вершина b имеет вес 2, а вершины a и c вес 1. Следует отметить, что вершины с одинаковым весом не упорядочены (например, вершины d и f и вершины a и c на Рис.4). Алгоритм MNS используется для распознавания единичных интервальных графов.

2.3    Лексикографический поиск в ширину (LBFS)

Данный алгоритм (англ. Lexicographic Breadth-First Search - LBFS) [3] позволяет еще дополнительно упорядочить вершины в найденных подмножествах алгоритмов, описанных выше. Схема работы алгоритма приведена на Рис.7.

Рис.7 - Порядок обхода вершин графа при алгоритме LBFS: e f d b a c

Сначала каждой вершине присваивается пустая лексикографическая метка. Первой выбирается заданная вершина e. Ей присваивается порядковый номер 6 (число вершин графа) и она исключается из дальнейшего рассмотрения. Соседям f и d присваивается лексикографическая метка 6. Далее выбирается вершина с наибольшей лексикографической меткой - таких вершин две: f и d. Пусть при произвольном выборе берется вершина f (порядковый номер 5). Алгоритм повторяется: соседям выбранной вершины f добавляется лексикографическая метка 5. Вершина d, уже имеющая метку 6 получает метку 65. Далее однозначно выбирается вершина d с лексикографически наибольшей меткой. И также однозначно вершины b a c.

Алгоритм LBFS позволяет получить упорядоченную последовательность вершин в отличие от последовательностей множеств вершин предыдущих алгоритмов. Однако, на некоторых этапах выполняется произвольный выбор вершин с наибольшими лексикографическими метками, что приводит к неоднозначностям: приведенный выше пример дает последовательность e f d b a c, но если на этапе случайной выборки из вершин f и d выбрать вершину d, то получится другой результат LBFS: e d f b c a. При конструировании многомаховых алгоритмов эта особенность алгоритма LBFS учитывается и не влияет на получаемый результат. Иногда результат работы алгоритма LBFS записывается в следующем виде, учитывающем случайные выборки: e [f d] b a c или e [d f] b c a. Выражения в квадратных скобках показывают, что выбор порядка вершин случаен.

Последовательность действий алгоритма LBFS записывается следующим образом [15]:

·        Инициализируется последовательность множеств Σ, состоящая из одного множества со всеми вершинами графа.

·        Инициализируется выходная пустая последовательность вершин.

·        Пока Σ не пустое:

·        Найти и удалить вершину v из первого множества в Σ

·        Если первое множество пустое - удалить его

·        Добавить v в выходную последовательность

·        Для каждого ребра v-w, такого что w содержится в множестве S в Σ:

·        Если множество S еще не заменялось при обработке v, то создать новое пустое множество T и расположить его перед S, иначе взять множество T перед S.

·        Переместить w из S в T и, если S станет пустым, удалить S из Σ.

Каждая вершина обрабатывается один раз, каждое ребро тестируется только при обработке соответствующих вершин, и каждая итерация внутреннего цикла требует не более некоторого постоянного числа операций. Значит, трудозатраты алгоритма LBFS линейно зависят от числа вершин и ребер графа.

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

На Рис.8 приведен интервальный граф с 22 вершинами.

Рис.8 - Интервальный граф из работы [5]

Начиная с вершины 20 алгоритм LBFS может получить следующий порядок вершин: 20 [8 [2 4] 21] [16 [15 [9 12 ]] 13 [11 14] 17 10 18 7 19 6] 5 3 1 22. У вершины 20 имеется 4 соседа с номерами 2, 4, 8 и 21. Последовательность множеств Σ: (2 4 8 21)(1 3 5-7 9-19 22). Из первого множества произвольно выбирается вершина 8. Ее соседи: 2, 4, 6, 7, 9-20. Новое Σ: (2 4)(21)(6 7 9-19)(1 3 5 22). Произвольно выбирается вершина 2. Новое Σ: (4)(21)(6 7 9-19)(1 3 5)(22). Далее однозначно выбираются вершины 4, а затем 21. В итоге для данного графа необходимо сделать всего 6 произвольных выборов вершин, остальные выбираются однозначно.

Для графа на Рис.7 последовательность множеств Σ на каждом этапе будет следующей: (a b c d e f), (d f)(a b c), (d)(a b)(c), (b)(a)(c).

2.4    Алгоритм LBFS+

Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан на случайных выборках, что не позволяет за один раз (проход, мах) получить искомые I или UI порядок вершин. Необходимы многомаховые алгоритмы. В этом случае последующие проходы могут использовать информацию с предыдущих этапов. Алгоритм LBFS+ [2] при необходимости выбора из множества вершин использует результат сортировки предыдущего этапа, что полностью исключает элемент случайности и дает однозначный результат.

2.5    Алгоритм "трех махов" для распознавания единичных интервальных графов

Этапы алгоритма [2]:

1.       σ ←LBFS

2.       σ+ ←LBFS(σ)

.        σ++ ←LBFS+(σ+)

4.       если σ++ является UI порядком то граф единичный интервальный, иначе нет.