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

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

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

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

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

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

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