Выбор того или иного задания графа зависит от конкретной задачи, которую предстоит решать.
Стандартным подходом является то, что во всех рассматриваемых задачах главной частью исходной информации служит граф. Кроме этого, исходные данные могут включить номера одной или нескольких выделенных вершин. Если, например, задача состоит в отыскании цепи, соединяющей две заданные вершины графа, то помимо графа необходимо задать номера этих двух вершин.
После того как ко всем исходным данным задачи присвоены конкретные значения, они размещены в памяти ЭВМ, они называются входом задачи. Размером (или длиною) входа считается число ячеек, занятых входом.
При анализе алгоритма решения любой задачи математика в первую очередь интересует зависимость времени его работы от размера задачи, т. е. от размера входа. Однако, это время зависит не только от размера входа, но и от других параметров задачи, т. е. время работы алгоритма на входах одинаковой длины может быть не одинаковым. Поясним сказанное на простейшем примере. Пусть элементами списка S={S1,S2,…,Sm} являются натуральные числа и требуется определить, содержит ли список S число, кратное трем. Очевидный алгоритм решения этой простой задачи состоит в следующем: проверяем поочередно делимость элементов списка S на 3 до тех пор, пока не встретится число кратное трем, или же не будут проверены все элементы S. Время выполнения р таких проверок равно t = 2р (р делений и р изменений адреса). Следовательно, при неизменной длине входа т время работы алгоритма будет изменяться в пределах 2£t£ 2т в зависимости от расположения подходящего элемента s в списке S. Наихудшим будет случай, когда S не содержит чисел, кратных трем, либо когда Sm— единственное такое число. Один из основных подходов к определению понятия «трудоемкость алгоритма» ориентируется именно на такого рода наихудший случай [1].
Трудоемкость (или сложность) алгоритма решения данной задачи определяетcя как функция f, ставящая в соответствие каждому натуральному числу п время работы f(n) алгоритма в худшем случае на входах длины n. Иначе говоря, f(n) —максимальное время работы алгоритма по всем входам данной задачи длины п. Анализ эффективности алгоритмов заключается в выяснении вопроса: как быстро растет функция f(n) с ростом n? При ответе на этот вопрос обычно используют O-символику.
Говорят, что неотрицательная функция f(n) не превосходит по порядку функцию g(n), если существует такая константа с, что f(n) <с g(n) для всех n> 0; при этом пишут f(n) = O(g(n)). Выражению «трудоемкость (сложность) алгоритма есть O(g(n)) придается именно этот смысл. В частности, трудоемкость O(i) означает, что время работы соответствующего алгоритма не зависит от длины входа.
Алгоритм с трудоемкостью О(п), где n — длина входа, называют линейным. Линейный алгоритм ограниченное константой чиcло раз просматривает входную информацию и для подавляющего большинства «естественных» задач является неулучшаемым в смысле трудоемкости. Поэтому отыскание линейного алгоритма для некоторой задачи часто является своего рода «последней точкой» в ее алгоритмическом решении.
Алгоритм, сложность которого равна О(пс), где с — константа, называется полиномиальным. В большинстве случаев эта степень не превосходит трех и оценка сложности алгоритма, как правило, имеет один из следующих видов: O(n3), O(n2), O(n), O(n log n). [1]
Одним из подходов к анализу NP-трудных задач, т.е. таких, про которые известно, что для их точного решения не существует полиномиальных алгоритмов, является наложение ограничений на вход исходной задачи и переход к рассмотрению возникающих при этом подзадач. В этом случае часто возникает пограничная область, отделяющая NP-полные подзадачи от полиномиально разрешимых и включающая те подзадачи, сложность которых неизвестна. Естественной целью является максимально возможное сужение этой области. Особых интерес представляют такие ограничения, при которых пограничная область отсутствует. Например, известно, что задача «k-раскраска» решается за полиномиальное время при k£2 и NP-полна при k³3. Еще более интересны ограничения, отражающие внутреннюю структуру подаваемых на вход объектов. Так, для задачи 3-раскраска, известно, что она полиномиально разрешима в классе графов G с максимальной степенью вершин D(G)£3 и является NP-полной при D(G)³4. В действительности, в приведеных примерах утверждения о полиномиальной распознаваемости тривиальны. В магистерской диссертации исследуется нетривиальный пример такого рода. Исследуется NP-полная задача распознавания принадлежности графа G классу Ll3 графов пересечений ребер линейных 3-униформных гиперграфов. Для нее существует порог полиномиальной разрешимости, связанный с минимальной степенью вершин d(G) тестируемого графа G. А именно, существует такое натуральное число d*, что задача GÎLl3 (1) полиномиально разрешима в классе графов G с d(G) ³d* и NP-полна при d(G)£d*. В настоящее время существует довольно узкая оценка для числа d*: 6£d*£10. А также существует линейный алгоритм, решающий задачу проверки графа на алгоритм, который решает данную задачу в классе графов с d(G) ³10 [2].
Задачей, поставленной в магистерской диссертации, является по возможности уменьшение оценки d(G) за счет сужения рассматриваемых классов графов.
Применение информационных технологий в теории графов можно разделить по следующим группам.
1) Программы, служащие для набора научных статей по теории графов (например, Microsoft Word, TeX).
2) Программы для изображения графов в удобном виде (например, использование автофигур в Microsoft PowerPoint, либо стандартного набора специальных изображений в Microsoft Visio).
3) Программы для подготовки иллюстраций научных статей (например, Adobe Photoshop, Corel Draw).
4) Специальные библиотеки в языках программирования. Начиная от единиц, предоставляющий графический интерфейс пользователю, до сложных библиотек используемых в при реализации алгоритмов в коммерческих приложениях (например, JGraph и JGraphT в Java). Такого рода библиотеки содержат минимально необходимые сущности, например «граф», «ребро», «бинарное дерево», а также стандартный набор алгоритмов: «поиск в ширину», «поиск в глубину», проверка связности графа, бинарный поиск и многое другое, что позволяет прикладному алгоритмисту абстрагироваться от несущественной детализации и перейти непосредственно к реализации алгоритма.
5) Поиск информации в сети Internet.
Отметим, что одним из наиболее важных моментов применения ИТ в теории графов является поиск информации. Зачастую бывает очень трудно найти печатный вариант необходимой книги. С помощью глобальной сети Internet эта проблема решается, появляется возможность искать книги и научные статьи по необходимой тематике.
А сейчас остановимся более подробно на использовании библиотек JGraphT и JGraph.
Сайт производителя этой библиотеки: http://www.jgraph.com/jgraph.html. JGraphT – это open source Java библиотека, которая содержит огромное количество объектов из теории графов и не меньшее количество стандартных алгоритмов. JGraph поддерживает работу со следующими типами графов.
1) Ориентированные и неориентированные графы.
2) Графы с помеченными и непомеченными ребрами.
3) Простые графы, мультиграфы, псевдографы.
Несмотря на всю мощь этой библиотеки, она довольно проста в использовании. С помощью JGraphT можно хранить в памяти компьютера объекты многих сложных типов. Для создания графа программист может использовать большой набор функций. Также предусмотрена возможность экспорта созданных объектов в XML-документ и наоборот, создания объектов из специальных XML-документов.
Эта библиотека содержит в себе следующий набор пакетов.
| org.jgrapht | «Стартовая точка» пользовательского приложения. Пакет содержит в себе такой наборы сущностей, как Graph, DirectedGraph, Multigraph, Pseudograph, UndirectedGraph. |
| org.jgrapht.alg | Содержит стандартный набор алгоритмов JGraphT. |
| org.jgrapht.alg.util | Набор утилит для использования в алгоритмах. |
| org.jgrapht.demo | Демонстрационные программы для быстрого ознакомления с «мощью» архива JGraphT. |
| org.jgrapht.event | Обработчики событий. |
| org.jgrapht.ext | Средства расширения и совместимости с другими продуктами. |
| org.jgrapht.generate | Конструкторы графов с различной структурой, например, можно создать полный случайный граф, полный двудольный, «колесо», и т.д. |
| org.jgrapht.graph | Имплементация различных графов. |
| org.jgrapht.traverse | Средства обхода графов. |
| org.jgrapht.util | Набор структур данных, алгоритмов и утилит, не специфичных для теории графов, но используемых в библиотеке JGraphT. |
Основными достоинствами библиотеки JGraphT являются то, что она:
1) оптимизирована для моделей данных и алгоритмов;
2) разработана для использования в высокопроизводительных приложениях;
3) может работать с графами содержащими миллионы вершин и ребер;
4) может обеспечивать графическую визуализацию данных с помощью библиотеки JGraph.
Рассмотрим, к примеру, пакет org.jgrapht.alg. Этот пакет интересен тем, что в нем содержится реализация многих стандартных алгоритмов из теории графов. Пакет содержит в себе следующий набор классов: