Например:

       вариант 1: списком пар вершин, соединенных ребрами (или дугами);

       вариант 2: списком  списков для каждой вершины множества  смежных с ней вершин. [8]

 

2. Задачи на графах.

2.1. Описание различных задач на графах.

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

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

       Далее перечислим некоторые типовые задачи теории графов и их приложения:

      - Задача о кратчайшей  цепи

• замена оборудования
• составление расписания движения транспортных средств
• размещение пунктов скорой помощи
• размещение телефонных станций

       - Задача о максимальном  потоке

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

      - Задача об упаковках  и покрытиях

• оптимизация структуры ПЗУ
• размещение диспетчерских пунктов городской транспортной сети

      - Раскраска в графах

• распределение памяти в ЭВМ
• проектирование сетей телевизионного вещания

      - Связность графов  и сетей

• проектирование кратчайшей коммуникационной сети
• синтез структурно-надежной сети циркуляционной связи
• анализ надежности стохастических сетей связи

    - Изоморфизм графов  и сетей

• структурный синтез линейных избирательных цепей
• автоматизация контроля при проектировании БИС

    - Изоморфное вхождение и пересечение графов

• локализация неисправности с помощью алгоритмов поиска МИПГ
• покрытие схемы заданным набором типовых подсхем

 

    - Автоморфизм графов

• конструктивное перечисление структурных изомеров для
• производных органических соединений
• синтез тестов цифровых устройств [8]

2.2. Нахождение кротчайших  путей в графе

Начальные понятия

       Будем рассматривать неориентированные графы G = (V, E), дугам которых приписаны веса. Это означает, что каждой дуге (u, v) ÎE поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

       Нас будет интересовать нахождение кратчайшего  пути между фиксированными вершинами s, t ÎV. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t. Если не существует ни одного пути из s в t, то полагаем d (s, t) = ╔ . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v₁,..., v_p не будет повторов.

       Можно дать много практических интерпретаций  задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги <u, v> равен вероятности p(u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p(u, v) на a (u, v) = - lg p(u, v). [5]

 

        Кратчайшие пути от фиксированной  вершины

       Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u, v], u, v Î V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v ÎV. Каждый раз, когда мы устанавливаем, что

        
D[u] + A[u, v] < D[v],

оценку D[v] улучшаем:

D[v] = D[u] + A[u, v]. 

       Процесс прерывается, когда дальнейшее улучшение  ни одного из ограничений невозможно.  

       Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v.  

       Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа.  

       Не  известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных. [4] 

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

 

 

2.3 Алгоритмы нахождения кратчайшего пути

 

     Алгоритм Дейкстры (Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием Сначала Кратчайший Путь (Shortest Path First).

Сложность алгоритма

     Сложность алгоритма Дейкстры зависит от способа  нахождения вершины v, а также способа  хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m - количество ребер в графе G.

     В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается  все множество вершин, а для  хранения величин d - массив, время работы алгоритма есть O(n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.[9]

     Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время извлечения вершины из станет logn, при том, что время модификации d[i] возрастет до logn. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O(nlogn + mlogn)

     Если  для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O(logn), а уменьшение значения в среднем за O(1), то время работы алгоритма составит O(nlogn + m).  

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

Алгоритм

     Дан граф G = (V,E) с весовой функцией . Если веса всех ребер ω в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся ребра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество ребер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов ребер , должно удовлетворять следующим свойствам.

     Для всех ребер  новый вес .

     Для всех пар вершин путь p является кратчайшим путем из вершины u в вершину v с использованием весовой функции ω тогда и только тогда, когда p - также кратчайший путь из вершины u в вершину v с весовой функцией .

 

Сложность алгоритма

     Если  в алгоритме Дейкстры неубывающая  очередь с приоритетами реализована  в виде фибоначчиевой кучи, то время  работы алгоритма Джонсона равно O(V2lgV + VE). При более простой реализации неубывающей очереди с приоритетами время работы становится равным O(VElgV), но для разреженных графов эта величина в асимптотическом пределе ведет себя лучше, чем время работы алгоритма Флойда - Уоршелла. [7]

     Алгоритм Флойда - Уоршелла - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

Алгоритм

     Пусть вершины графа  пронумерованы от 1 до n и введено обозначение для длины кратчайшего пути от i до j, который кроме самих вершин проходит только через вершины . Очевидно, что  - длина (вес) ребра , если таковое существует (в противном случае его длина может быть обозначена как )

Существует  два варианта значения :

Кратчайший  путь между не проходит через вершину k, тогда

Существует  более короткий путь между  , проходящий через k, тогда он сначала идёт от i до k, а потом от k до j. В этом случае, очевидно,  

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

Тогда рекуррентная формула для имеет вид: