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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И т.д.

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

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

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

Изучить алгоритм 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].

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

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

Рис.2

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

Рис.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(у)

3. у++ <LBFS+(у+)

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

Следует отметить, что проверка на UI порядок также требует обхода всех вершин и ребер графа и, как показали расчеты, занимает процессорное время сравнимое с этапами LBFS. То есть данный алгоритм условно можно назвать «четырехмаховым».

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

Для единичного интервального графа, показанного на Рис.9 необходимы три прохода для получения UI порядка:

у = c [b d] a e

у+ = e d [b c] a

у++ = a b c d e

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

В трехмаховом алгоритме возможно использование алгоритма MNS и MNS+ [7], вместо LBFS и LBFS+.

2.6 Алгоритм LBFS*

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

Пусть множество вершин с лексикографически наибольшим номером.

Пусть и

пусть некоторая вершина такая что

Необходимая вершина выбирается следующим образом: когда иначе когда и когда

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

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

1. д <LBFS

2. у <LBFS+(д)

3. Расчет и для всех вершин

4. с <LBFS*(у)

5. ф <LBFS+(с)

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

7. если ф является I порядком, то граф интервальный, иначе «граф не интервальный».

Следует отметить, что в данном алгоритме на каждом из 6 этапов выполняется полный обход вершин и ребер графа, то есть условно данный алгоритм «шестимаховый».

3. Программные модули проекта

Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное приложение, которому в виде параметров командной строки можно передать необходимые для работы данные. Общий объем всех кодов с комментариями более 2500 строк и около 100 кбайт.

3.1 Представление графа в памяти ЭВМ

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

Таблица 1 - значения элементов массива ig представляющего граф в памяти ЭВМ

ig[0]	Размерность массива минус 1
ig[1]	Начало списка соседей вершины 1 - число вершин N плюс 2
ig[2]	Начало списка соседей вершины 2
…
ig[N]	Начало списка соседей вершины N
ig[N+1]	Конец списка вершины N - размерность массива
ig[N+2]	Соседи вершины 1
…
ig[ig[2]-1]	Соседи вершины 1
ig[ig[2]]	Соседи вершины 2
…
ig[ig[3]-1]	Соседи вершины 2
ig[ig[3]]	Соседи вершины 3
…
…
ig[ig[N+1]-1]	Соседи вершины N
---	Элемента с номером ig[N+1] в массиве нет.

Размерность массива составляет число вершин графа плюс удвоенное число ребер плюс два.

Для поиска соседей вершины i (1 <= i <= N) используется цикл for (j=ig[i]; j<ig[i+1]; j++) и номера соседей ig[j].

Число соседей вершины i (1 <= i <= N) составляет ig[i+1]-ig[i].

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

3.2 Программа задания единичного интервального графа

Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается граф, имя файла для записи результатов (Рис.10, Рис.11). Если имя файла имеет расширение bin, то записывается двоичный файл, иначе текстовый, что удобно для визуального контроля и отладки.

Рис.10



Рис.11

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

Изменяя длину отрезка графа можно для заданного числа вершин изменять число ребер графа.

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

3.3 Программа задания интервального графа

Программа задания интервального графа была реализована по аналогии с программой задания единичного интервального графа. Изменения коснулись алгоритмов задания связей графа с помощью I-порядка. Для каждой вершины случайно задается число соседей вверх, например, для вершины j число r, 0 <= r <= N-j. Считаем, что вершина связана ребрами с вершинами j+1, j+2, ... , j+r. Для вершины возможны соседи и с меньшими номерами - соответствующие ребра задаются для вершин с меньшими номерами. Таким образом, интервальный граф задается с помощью всего одного массива целых чисел размерностью N. Сразу известно число ребер графа V - это сумма всех элементов массива. Для того, чтобы преобразовать эти данные о связности интервального графа в виде представленный в таблице 1, необходим временный массив размерностью 4*V для хранения списков ребер, так как мы не знаем заранее, сколько ребер у каждой вершины. При формировании временного массива легко выполняются проверки на связность графа - может оказаться так, что никакие из вершин с меньшими номерами не связаны ребрами с рассматриваемой вершиной (и значит со всеми остальными). Так как перебор вершин и формирование их ребер осуществляется последовательно снизу вверх, то если у рассматриваемой вершины кроме первой в списках нет ребер, то имеет место несвязность графа. Граф легко сделать связным, если соединить ребром рассматриваемую вершину с предыдущей. После этого данные из временного массива можно записать в необходимом формате таблицы 1, также как для единичного интервального графа выполнить перемешивание номеров вершин, и записать результат в текстовом или двоичном виде в выходной файл.

Входные параметры программы задания интервального графа: число вершин, параметр Лямбда (Число ребер / Число вершин), имя файла для записи результатов.

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

Пример работы программы показан на Рис.12

Рис.12

3.4 Программа задания случайных графов Эрдёша - Реньи

Программа реализует алгоритм задания случайных графов Эрдёша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер выбираются случайным образом. Используются списки ребер, как в программе задания интервальных графов. Для связности графа при необходимости добавляются дополнительные ребра. Для этого используется рекурсивный алгоритм закраски вершин графа. Как показали тестовые расчеты, такой алгоритм дает хорошие результаты для графов с большим числом вершин, но небольшим соотношением Число Ребер / Число Вершин. Если это соотношение увеличивается, то время работы программы сильно растет из-за необходимости проверок на уже наличие в графе нового случайного ребра: при этом идет перебор всех соседей одной из вершин. Для задания графов с относительно небольшим числом вершин и большим числом ребер был разработан и реализован другой алгоритм задания графов Эрдёша-Реньи. Так как число вершин невелико, то связность такого графа можно задавать с помощью матрицы связности, где для каждого возможного ребра есть отдельный элемент матрицы. Кроме того, если задаваемое число ребер превышает половину максимального числа ребер графа, то эффективнее задавать случайным образом отсутствующие ребра. Из полученной матрицы связности далее формируются списки ребер, выполняется проверка на связность и формирование нужных текстовых или двоичных файлов так же, как и в первом варианте алгоритма. Два реализованных алгоритма позволили задавать случайные графы Эрдёша-Реньи с любым числом вершин и ребер, ограниченным только оперативной памятью ЭВМ.

3.5 Программа добавления/удаления ребер графа

Входные параметры: входной файл, выходной файл, номер вершины, номер вершины.

Если задаваемые номера вершин положительные, то добавляется соответствующее ребро, иначе удаляется. На Рис.13 Рис.14 показаны оба варианта соответственно.

Программа считывает входные данные, добавляет или удаляет данные для каждой вершины ребра со смещением списков и записывает итоговые данные в файл. Файлы могут быть как двоичные, так и текстовые сформированные программами задания единичного или интервального графа или с добавленными/удаленными ребрами.



Рис.13

Рис.14

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

Программа реализует алгоритм трех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным или нет, а также время работы алгоритма и программы. На Рис.15 и Рис.16 показаны оба варианта.

Рис.15

Рис.16

Первоначальный вариант программы реализовывал алгоритмы MNS и MNS+ (обозначим, как MNS3). После реализации алгоритма LBFS и алгоритма четырех махов стало возможным легко и быстро реализовать алгоритм трех махов с использованием LBFS и LBFS+ (обозначим, как LBFS3). Ниже приводится сравнение быстродействия этих алгоритмов.

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

Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным, интервальным или не интервальным, а также время работы алгоритма и программы. На Рис.17, Рис.18 и Рис.19 показаны все три варианта.

Рис.17



Рис.18

Рис.19

Для отладки программы был реализован алгоритм выдачи последовательности вершин лексикографического поиска каждого этапа, на экран.

3.8 Подпрограмма изменения последовательности вершин графа

На этапе отладки алгоритма четырех махов возникла следующая проблема: результат расчета мог зависеть от входной последовательности вершин графа. Если изначально вершины расположены в нужном порядке, то распознавание интервального графа выполняется успешно, если вершины перемешаны, то результат был нестабилен. Перемешивание вершин случайным образом выполняется при задании графов. Для отладки кода была реализована отдельная подпрограмма, которая сохраняя структуру ребер графа, перемешивает вершины графа в памяти программы. Это позволило быстро выполнять тестирование кода на одном и том же графе, но с разной последовательностью вершин и отладить алгоритм LBFS*. Результаты, полученные с помощью данного алгоритма, приведены в разделе 4.1.

4. Результаты численных экспериментов

Численные эксперименты были проведены для следующих целей:

· Подтверждение корректности алгоритмов.

· Подтверждение линейности временных затрат алгоритмов.

В расчетах были использованы три алгоритма:

· Алгоритм четырех махов (обозначим, как LBFS4, раздел 2.7);

· Алгоритм трех махов LBFS3 (раздел 2.5);

· Алгоритм трех махов MNS3 (раздел 2.5).

Все три алгоритма распознают единичные интервальные графы,

В программах LBFS3 и MNS3 встроен алгоритм проверки на I и UI порядок (UI включает в себя проверку на I порядок), что в некоторых случаях позволило определить интервальные графы. Конечно, это получается случайно, если порядок вершин изменить, то программы LBFS3 и MNS3 выдадут: граф не является интервальным.

Все программы также определяют, является ли граф связным.

4.1 Тестирование алгоритма четырех махов

Для подтверждения работоспособности алгоритма четырех махов были проведены серии расчетов на тестовом графе с 22 вершинами (Рис.8, раздел 2.3). В расчетах случайным образом менялся порядок вершин и контролировались выходные данные. Во всех расчетах было получено, что граф является интервальным. Некоторые из возможных получаемых порядков вершин на каждом из 4 этапов приведены на Рис.20. Если расчет начинается с вершин 4, 21 или 22, то в итоговом порядке вершины расположены по возрастанию. Если расчет начинается с других вершин, то UI порядок будет обратным, отсортированным по правой границе интервалов, и не по убыванию порядковых номеров. Во всех случаях для данного графа на третьем этапе получается одинаковая последовательность вершин, хотя и не являющаяся UI порядком, что требует четвертого окончательного прохода и сортировки.

Рис. 20- Результаты работы LBFS4 на каждом этапе для 8 запусков

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

4.2 Исследования временных затрат алгоритмов

Исследования временных затрат алгоритмов были проведены для трех вариантов программ: LBFS4, LBFS3, MNS3; для двух вариантов сборки исполняемого файла: Debug и Release (без оптимизации и с оптимизацией кода); для трех типов графов: единичный интервальный, интервальный, случайный Эрдёша-Реньи. В сериях расчетов одновременно пропорционально увеличивалось число вершин и ребер графа для проверки линейности трудозатрат алгоритмов. Также были проведены две серии расчетов для графов с различным соотношением числа ребер к числу вершин: 25 и 1000. В расчетах контролировалось время выполнения алгоритма. Результаты засечек приведены в таблицах 2-5 и на рисунках 21, 22 в виде графиков.

Таблица 2 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Debug. Число Ребер / Число вершин ~25

Число вершин, тысяч	Число ребер	LBFS 4	LBFS 3	MNS 3
		ед.инт.	инт.	случ.	ед.инт.	инт.	случ.	ед.инт.	инт.	случ.
20	500537	0.889	1.155	2.655	0.842	0.76	1.721	0.187	0.214	0.598
40	998937	1.544	2.214	5.028	1.17	1.517	3.685	0.343	0.462	1.186
60	1498010	2.449	3.464	7.959	1.779	2.269	5.331	0.499	0.674	1.934
80	1997430	4.02	4.503	10.13	2.481	3.037	7.199	0.718	0.9	2.54
100	2497160	5.07	5.687	12.88	2.948	3.748	9.049	0.889	1.104	3.301
120	2996730	5.726	6.838	15.77	3.51	4.569	11.14	1.092	1.34	3.834
140	3496650	6.349	8.071	18.31	4.664	5.352	12.91	1.577	1.54	4.506
160	3996480	8.034	9.177	20.92	5.164	6.046	14.71	1.513	1.752	5.047
180	4497290	8.096	10.39	23.6	6.115	6.854	16.66	2.184	2.007	5.916
200	4997230	10.37	11.47	26.28	7.27	7.589	18.45	2.215	2.235	6.326
220	5497100	10.93	12.62	28.96	7.753	8.332	20.38	2.106	2.447	7.41
240	5995570	11.45	13.74	31.42	7.675	9.041	22.24	2.387	2.698	8.016
260	6496380	12.68	14.9	34.45	8.143	9.798	23.95	2.527	2.904	8.62
280	6998290	13.65	16.16	37.17	9.142	10.65	25.9	2.886	3.084	9.348
300	7500650	14.29	17.31	39.73	9.843	11.39	27.69	3.042	3.312	10.05
320	8000110	16.08	18.44	42.44	10.10	12.09	29.63	3.338	3.564	10.85
340	8499520	16.38	19.49	45.06	10.62	12.85	31.44	3.407	3.789	11.42
360	8998140	17.64	20.76	47.92	11.34	13.64	33.55	3.686	4.006	12.22
380	9497400	19.78	21.93	50.44	11.94	14.51	35.47	4.056	4.247	12.93
400	9995670	20.49	23.17	52.98	13.01	15.29	37.21	4.109	4.473	13.6
420	10494700	21.09	24.27	55.77	13.36	16	38.89	4.288	4.689	14.25
440	10993800	22.62	25.37	58.33	14.73	16.72	40.8	4.504	4.891	15.1
460	11494100	23.80	26.58	61.18	15.69	17.51	42.81	4.765	5.134	15.63
480	11995100	24.20	27.71	63.75	15.91	18.36	44.58	5.023	5.341	16.4
500	12495700	24.67	28.93	66.49	16.20	19.08	46.65	5.242	5.573	17
520	12996400	26.02	30.11	69.23	16.97	19.9	48.46	5.429	5.789	17.74
540	13497300	27.19	31.24	71.83	18.00	20.57	50.22	5.567	5.995	18.56
560	13996200	28.79	32.33	74.34	19.16	21.36	51.97	5.852	6.257	19.16
580	14495400	29.45	33.57	77.5	19.99	22.09	53.87	6.052	6.468	19.72

Таблица 3 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Release. Число Ребер / Число вершин ~25

Число вершин, тысяч	Число ребер	LBFS 4	LBFS 3	MNS 3
		ед.инт.	инт.	случ.	ед.инт.	инт.	случ.	ед.инт.	инт.	случ.
20	500537	0.509	0.576	2.058	0.276	0.323	1.373	0.133	0.141	0.55
40	998937	0.966	1.098	3.778	0.574	0.679	2.988	0.273	0.282	1.072
60	1498010	1.526	1.728	6.171	0.839	0.988	4.292	0.417	0.444	1.775
80	1997430	1.928	2.184	7.846	1.11	1.306	5.744	0.555	0.592	2.386
100	2497160	2.403	2.735	9.758	1.385	1.642	7.12	0.702	0.747	3.068
120	2996730	2.987	3.389	12.13	1.73	2.051	9.055	0.835	0.912	3.592
140	3496650	3.5	3.962	14.22	2.004	2.37	10.44	0.981	1.042	4.153
160	3996480	4	4.534	16.33	2.293	2.73	11.94	1.133	1.19	4.739
180	4497290	4.52	5.122	18.37	2.591	3.07	13.55	1.261	1.347	5.438
200	4997230	4.976	5.687	20.35	2.861	3.432	14.85	1.4	1.497	6.102
220	5497100	5.519	6.251	22.45	3.156	3.725	16.37	1.554	1.658	6.939
240	5995570	6.061	6.862	24.47	3.44	4.053	17.74	1.693	1.802	7.5
260	6496380	6.578	7.445	26.56	3.736	4.505	19.36	1.823	1.949	8.065
280	6998290	7.126	8.068	28.81	4.026	4.796	20.99	1.972	2.102	8.755
300	7500650	7.63	8.639	30.85	4.322	5.109	22.55	2.116	2.25	9.4
320	8000110	8.132	9.2	32.91	4.597	5.436	23.86	2.263	2.41	10.08
340	8499520	8.656	9.774	34.74	4.898	5.796	25.48	2.402	2.562	10.73
360	8998140	9.142	10.36	36.97	5.182	6.177	26.98	2.545	2.716	11.4
380	9497400	9.672	10.95	39.09	5.467	6.461	28.69	2.688	2.865	12.03
400	9995670	10.19	11.52	41.09	5.762	6.817	30.23	2.826	3.015	12.62
420	10494700	10.69	12.11	43.25	6.055	7.173	31.76	2.972	3.167	13.3
440	10993800	11.21	12.7	45.36	6.354	7.514	33.31	3.116	3.321	13.99
460	11494100	11.73	13.27	47.29	6.637	7.855	34.76	3.257	3.472	14.62
480	11995100	12.23	13.84	49.42	6.926	8.189	36.35	3.398	3.632	15.26
500	12495700	12.8	14.45	51.73	7.214	8.584	38.07	3.538	3.774	15.87
520	12996400	13.28	15.03	53.74	7.512	8.931	39.44	3.679	3.925	16.54
540	13497300	13.8	15.62	55.85	7.799	9.249	40.91	3.824	4.089	17.25
560	13996200	14.26	16.14	57.64	8.102	9.639	42.53	3.966	4.23	17.83
580	14495400	14.86	16.91	60.13	8.368	9.925	43.83	4.103	4.377	18.39

Таблица 4 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Debug. Число Ребер / Число вершин ~1000

Число вершин, тысяч	Число ребер	LBFS 4	LBFS 3	MNS 3
		ед.инт.	инт.	случ.	ед.инт.	инт.	случ.	ед.инт.	инт.	случ.
0.5	124750	0.721	0.718	0.891	0.463	0.47	0.576	0.102	0.043	0.054
1	499500	1.313	1.299	1.606	1.008	1.014	1.26	0.198	0.084	0.105
1.5	1124300	2.163	2.153	2.674	1.478	1.429	1.785	0.333	0.139	0.172
2	1512800	2.727	2.668	3.287	1.926	1.93	2.406	0.456	0.188	0.233
2.5	2352000	3.529	3.425	4.137	2.49	2.361	3.042	0.588	0.238	0.313
3	2508400	4.253	4.205	5.271	3.059	3.081	3.827	0.699	0.280	0.407
3.5	3410000	5.004	4.961	6.052	3.521	3.515	4.376	0.845	0.330	0.445
4	3506500	5.759	5.627	7.029	4.067	4.093	5.051	0.916	0.374	0.552
4.5	4431000	6.519	6.38	7.941	4.586	4.617	5.722	1.066	0.421	0.570
5	4499600	7.147	7.044	8.771	5.094	5.003	6.279	1.146	0.472	0.663
5.5	5443200	7.868	7.797	9.708	5.597	5.55	6.944	1.316	0.530	0.679
6	5489300	8.599	8.552	10.68	6.106	6.048	7.506	1.418	0.579	0.781
6.5	6443100	9.302	9.293	11.57	6.631	6.602	8.143	1.552	0.614	0.858
7	6482800	10.1	10.06	12.49	7.147	7.193	8.865	1.692	0.680	0.862
7.5	7439000	10.8	10.77	13.37	7.659	7.707	9.566	1.775	0.749	0.952
8	7469000	11.54	11.48	14.25	8.136	8.166	10.17	1.933	0.780	0.982
8.5	8437300	12.26	12.18	15.11	8.654	8.712	10.81	2.048	0.836	1.042
9	8472800	13.03	12.92	16.02	9.118	9.21	11.47	2.153	0.879	1.107
9.5	9442700	13.71	13.66	16.94	9.642	9.723	12.14	2.276	0.934	1.169
10	9477600	14.4	14.37	17.8	10.2	10.24	12.76	2.38	0.980	1.254
10.5	10448000	15.15	15.09	18.74	10.72	10.78	13.39	2.533	1.032	1.313
11	10471000	15.87	15.83	19.61	11.27	11.29	14.1	2.664	1.024	1.368
11.5	11449000	16.61	16.56	20.53	11.75	11.81	14.69	2.778	1.107	1.407
12	11477000	17.32	17.25	21.41	12.23	12.31	15.34	2.88	1.164	1.467
12.5	12451000	18.11	18.02	22.36	12.72	12.87	16.03	2.999	1.209	1.536
13	12479000	18.79	18.74	23.37	13.23	13.41	16.68	3.117	1.26	1.612
13.5	13458000	19.54	19.48	24.19	13.81	13.93	17.28	3.255	1.291	1.631
14	13476000	20.2	20.12	24.98	14.36	14.58	17.93	3.365	1.366	1.703
14.5	14458000	21.05	20.91	26.01	14.8	14.92	18.52	3.48	1.409	1.786

Таблица 5 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Release. Число Ребер / Число вершин ~1000

Число вершин, тысяч	Число ребер	LBFS 4	LBFS 3	MNS 3
		ед.инт.	инт.	случ.	ед.инт.	инт.	случ.	ед.инт.	инт.	случ.
0.5	124750	0.201	0.238	0.312	0.126	0.151	0.198	0.053	0.024	0.030
1	499500	0.362	0.421	0.551	0.277	0.334	0.439	0.105	0.050	0.061
1.5	1124300	0.605	0.713	0.935	0.389	0.466	0.607	0.176	0.084	0.101
2	1512800	0.739	0.854	1.164	0.510	0.608	0.793	0.24	0.114	0.135
2.5	2352000	0.943	1.074	1.478	0.649	0.743	1.033	0.310	0.145	0.188
3	2508400	1.177	1.375	1.854	0.842	1.016	1.338	0.358	0.165	0.222
3.5	3410000	1.379	1.597	2.139	0.960	1.142	1.532	0.423	0.196	0.258
4	3506500	1.566	1.826	2.438	1.096	1.316	1.742	0.476	0.221	0.295
4.5	4431000	1.786	2.079	2.76	1.258	1.514	1.994	0.549	0.257	0.339
5	4499600	1.934	2.261	3.061	1.356	1.634	2.149	0.601	0.288	0.381
5.5	5443200	2.18	2.537	3.387	1.518	1.823	2.385	0.698	0.326	0.401
6	5489300	2.402	2.801	3.711	1.633	1.974	2.61	0.746	0.353	0.446
6.5	6443100	2.606	3.051	4.019	1.804	2.162	2.831	0.804	0.382	0.473
7	6482800	2.825	3.33	4.37	1.946	2.348	3.073	0.880	0.409	0.507
7.5	7439000	3.026	3.563	4.673	2.103	2.53	3.328	0.942	0.442	0.542
8	7469000	3.216	3.794	4.965	2.218	2.687	3.515	1.01	0.474	0.590
8.5	8437300	3.424	4.003	5.215	2.383	2.868	3.762	1.081	0.506	0.618
9	8472800	3.617	4.256	5.551	2.527	3.046	3.978	1.148	0.536	0.662
9.5	9442700	3.837	4.52	5.927	2.678	3.209	4.225	1.213	0.566	0.691
10	9477600	4.059	4.776	6.228	2.801	3.382	4.449	1.271	0.595	0.720
10.5	10448000	4.245	5.003	6.551	2.956	3.559	4.686	1.348	0.625	0.759
11	10471000	4.439	5.249	6.867	3.084	3.728	4.907	1.418	0.658	0.827
11.5	11449000	4.668	5.506	7.185	3.24	3.896	5.152	1.486	0.687	0.845
12	11477000	4.85	5.719	7.498	3.376	4.067	5.4	1.544	0.716	0.867
12.5	12451000	5.089	5.991	7.853	3.54	4.288	5.633	1.602	0.745	0.917
13	12479000	5.265	6.246	8.211	3.664	4.429	5.826	1.666	0.776	0.944
13.5	13458000	5.479	6.489	8.554	3.82	4.61	6.064	1.751	0.810	1.005
14	13476000	5.655	6.666	8.746	3.974	4.836	6.34	1.801	0.838	1.012
14.5	14458000	5.919	7.002	9.229	4.084	4.93	6.485	1.856	0.864	1.058

	Время счета серии задач: Число Ребер / Число вершин ~25.
	Debug	Release
единичный интервальный
интервальный
случайный

Рис.21

	Время счета серии задач: Число Ребер / Число вершин ~1000. Debug Release единичный интервальный интервальный случайный

Рис.22

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

По результатам таблиц 2-5 и графиков (Рис.21, Рис.22) видна линейная зависимость времени счета от суммы количеств вершин и ребер графа, и можно сделать следующие выводы:

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

Наиболее быстрым является алгоритм MNS3, затем LBFS3 и LBFS4. Алгоритм LBFS3 быстрее LBFS4 примерно на треть, хотя в названии фигурируют 3 и 4 прохода, реально выполняются 4 и 6 переборов всех вершин и соседей - это и дает выигрыш в скорости примерно на треть. Алгоритм MNS3 быстрее LBFS3 на разных графах от 2 до 10 раз, хотя эти программы дают полностью одинаковый результат. Это проявляется преимущество алгоритма быстрой сортировки по сравнению с упорядочиванием через множества алгоритма LBFS. Таким образом, развитие алгоритма распознавания единичных интервальных графов (MNS3) до уровня распознавания интервальных и единичных интервальных графов (LBFS4) требует увеличения трудозатрат примерно на порядок (от 3 до 15 раз на разных графах).

Режим без оптимизации Debug примерно в 2 раза медленнее, чем с оптимизацией Release. Однако на случайных графах с небольшим числом ребер (отношение числа ребер к числу вершин 25) скорость счета двух режимов различается на <20%. Видимо, перебор запутанной сложной структуры случайного графа является тяжелым для современных процессоров.

Графы с отношением числа ребер к числу вершин 25 считаются в примерно два раза дольше, чем с отношением числа ребер к числу вершин 1000. Таким образом, число вершин оказывает условно большее влияние на скорость счета, чем число ребер графа.

Замер скорости счета на современном процессоре Intel i5-2400 3.1GHz показал, что задача со случайным графом с числом вершин 580 тысяч и числом ребер 14.5 миллиона сосчиталась за 12.8, 9.6, 1.2 секунд для LBFS4, LBFS3, MNS3 в режиме Release. То же в режиме Debug 15.4, 11.3, 1.7 секунд. Это показывает высокую скорость счета реализованных алгоритмов: обработка графов с числом вершин и ребер десятки миллионов не превышает десятков секунд.

Временные засечки времени работы алгоритмов распознавания (таблицы 2-5) показали хорошую масштабируемость реализованных программ: при увеличении числа вершин и ребер время счета увеличивается практически линейно. Таким образом практически показано, что временные затраты алгоритмов составляют O(|V|+|E|) (время счета прямо пропорционально числу вершин и ребер).

Заключение

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

Проведены тестовые эксперименты на графах на корректность алгоритмов и на время работы алгоритмов. Экспериментально показана линейная скорость работы реализованных алгоритмов от суммы количеств вершин и ребер.

Список литературы

1) Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.

2) Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl. Math. 138, 371-379 (2004)

3) D.J. Rose, R.E. Tarjan, G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5 (1976), pp. 266-283.

4) F. S. Roberts. On the compatibility between a graph and a simple order. Journal of Combinatorial Theory, Series B, 11(1):28-38, 1971.

5) D.G. Corneil, S. Olariu, L. Stewart, The LBFS structure and recognition of interval graphs, SIAM Journal on Discrete Mathematics, 23 (2009), pp. 1905-1953.

6) Peng Li, Yaokun Wu. A Four-Sweep LBFS Recognition Algorithm for Interval Graphs. Discrete Mathematics & Theoretical Computer Science, Vol 16, No 3 (2014).

7) D. G. Corneil and R. Krueger. A unified view of graph searching. SIAM Journal on Discrete Mathematics, 22(4):1259-1276, 2008.

8) Татт У. Теория графов. -- М.: Мир, 1988. -- 424 с.

9) Wikipedia - The Free Encyclopedia [Электронный ресурс] -- Режим доступа : https://en.wikipedia.org/ wiki/ Interval_graph

10) C.G. Lekkerkerker, J.C. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, 51 (1962), pp. 45-64.

11) F.S. Roberts, Indifference graphs, F. Harary (Ed.), Proof Techniques in Graph Theory, Academic Press, New York, (1969), pp. 139-146.

12) G. Ramalingam, C.P. Rangan, A uniform approach to domination problems on interval graphs, Information Processing Letters, 27 (1988), pp. 271-274.

13) P.J. Looges, S. Olariu, Optimal greedy algorithms for indifference graphs, Computers & Mathematics with Applications, 25 (1993), pp. 15-25.

14) Wikipedia - The Free Encyclopedia [Электронный ресурс] -- Режим доступа : https://en.wikipedia.org/wiki/Breadth-first_search

15) Wikipedia - The Free Encyclopedia [Электронный ресурс] -- Режим доступа : https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search

16) Erdos P., Renyi A. On random graphs I // Publ. Math. Debrecen. -- 1959. -- V. 6. -- P. 290-297.

Размещено на Allbest.ru