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

Рис.21

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

)        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.

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

)        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.

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

)        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

)        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.

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

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

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

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

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

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