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

     Матрица смежности – квадратная матрица, размерности, равной количеству вершин. При этом а[ i, j ] – целое число, равное количеству рёбер, связывающих i-ю, j-ю вершину. Если в графе нет петель, то диагональные элементы равны 0. Если рёбра не повторяются, то все элементы 0 или 1. Если граф неориентированный, то матрица симметрична.

     3. Матрица инцидентности:

 

     4. Явное задание графа как алгебраической системы: <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как к рассмотрению приняты только простые графы, граф проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d }; {(a,b), (b,a),(b,c),(c,b),(a,c),( c,a),(c,d),(d,c)}>.

     В таком представлении ребру соответствуют  две пары вершин (v₁,v₂) и ( v₂,v₁), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его отождествляют с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф можно записать как пару (V,E), где V – множество вершин, а E – множество рёбер.

     5. Задание графа посредством списков.

     Например, списком пар вершин, соединенных ребрами (или дугами) или списком списков для каждой вершины множества смежных с ней вершин.

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

     Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости/длины), задаваемые матрицей С=[c_ij].

     Задача  о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s x до заданной конечной вершины t x, при условии, что такой путь существует t R(s) (здесь R(s) множество, достижимое из вершины s) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и х_i- некоторая его вершина, то, двигаясь от s к х_i, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым ( ) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

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

     1) Для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами х_i X.

     2) Найти кратчайшие пути между всеми парами вершин.

     Почти все методы, позволяющие решить задачу о кратчайшем (s-t)-пути, дают также (в процессе решения) и все кратчайшие пути от s к х_i. Таким образом, они позволяют решить задачу с небольшими дополнительными вычислительными затратами.

     С другой стороны, задача №1 может быть решена либо n-кратным применением алгоритма задачи №2, причем на каждом шаге в качестве начальной вершины s берутся различные вершины, либо однократным применением специального алгоритма.

     Наиболее  распространенные методы их решения  задач – это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k – кратчайших путей в графе).

     Если  требуется найти кратчайший путь во взвешенном графе, где pебpам приписаны вещественные числа – веса, и эти веса неотрицательны, можно использовать алгоритм Дейкстpы. При наличии ребер с отрицательным весом кратчайший путь может не существовать даже для связного графа. Кратчайший путь существует, только если в графе нет циклов отрицательного сyммаpного веса – по такому циклу можно кpyтиться сколько угодно, уменьшая длину до бесконечности. Для общего случая подходит алгоритм Флойда, который позволяет либо найти кратчайшие пути, либо обнаружить циклы отрицательной длины.

     Упомянутые  алгоритмы являются классическими  и описаны в различных книгах по теории графов (напp. [1]). Существyет огромное количество дpyгих алгоритмов, более выгодных в каких-то случаях.

Алгоритм  Дейкстры

     Пусть необходимо лететь с одной пересадкой, причем сначала самолетом компании A, а затем – компании B. Сколько придется заплатить пассажиру, чтобы попасть из города i в город j?

     Известно, что все цены неотрицательны. Найти наименьшую стоимость проезда 1 i для всех i=1..n за время O(n²).

     В процессе работы алгоритма некоторые  города будут выделенными (в начале – только город 1, в конце – все).

     При этом:

1. для каждого выделенного города i хранится наименьшая стоимость пути 1 i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;
2. для каждого невыделенного города i хранится наименьшая стоимость пути 1 i, в котором в качестве промежуточных используются только выделенные города.

     Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрев первый невыделенный город на этом пути – уже до него путь длиннее. Существенно требование неотрицательности цен.

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

     При самом бесхитростном способе  хранения множества выделенных городов (в булевском векторе) добавление одного города к числу выделенных требует времени O(n).

Схема алгоритма Дейкстры

     Алгоритм  использует три массива из N (= числу вершин сети) чисел каждый:

1. S содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена);
2. B содержит расстояния – текущие кратчайшие рас- стояния от до соответствующей вершины;
3. третий массив с содержит номера вершин – k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из V_i в V_k. Матрица расстояний A[i,k] задает длины дуге A[i,k]; если такой дуги нет, то A[i,k] присваивается большое число Б, равное "машинной бесконечности".

     Описание  реализации:

1. Инициализация. В цикле от 1 до N заполнить нулями массив S; заполнить числом i массив C; перенести i-ю строку матрицы A в массив B, S[i]:=1; C[i]:=0 (i – номер стартовой вершины).
2. Общий шаг. Найти минимум среди неотмеченных (т. е. тех k, для которых S[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k]

     Затем выполняются следующие операции:

     S[j]:=1;

     если B[k] > B[j]+A[j,k], то (B[k]:=B[j]+A[j,k]; C[k]:=j)

     (Условие  означает, что путь Vi ... Vk длиннее,  чем путь V_i...V_j V_k).

     (Если  все S[k] отмечены, то длина пути  от V_i до V_k равна B[k]. Теперь надо перечислить вершины, входящие в кратчайший путь).

3. Выдача ответа. (Путь от V_i до V_k выдается в обратном порядке следующей процедурой:)

     z:=C[k];

     Выдать z;

     z:=C[z]. Если z = О, то конец,

     иначе перейти к 3.2. 

     Для выполнения алгоритма нужно N раз  просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n²).

     Отыскание кратчайшего пути имеет естественную интерпретацию в терминах матриц. Пусть A – матрица цен одной аваиакомпании, а B – матрица цен другой. Считается, что диагональные элементы матриц равны 0. Можно доказать, что эта матрица вычисляется по обычной формуле для произведения матриц, только вместо суммы надо брать минимум, а вместо умножения – сумму.

     Обычное умножение матриц тоже может оказаться  полезным, только матрицы должны быть другие. Пусть есть не все рейсы (как  в следующем разделе), а только некоторые, a[i,j] равно 1, если рейс есть, и 0, если рейса нет. Возведем матрицу a (обычным образом) в степень k и посмотрим на ее i-j-ый элемент. Он равен числу различных способов попасть из i в j за k рейсов.

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

4. Нахождение остовного дерева минимального веса

     Постановка  задачи:

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

     Всякую  прикладную постановку задачи нелишне  уточнить. Мы негласно подразумеваем, что города сравнительно со страной  малы; поэтому мы пренебрежем величиной  городов и будем изображать город (точнее: телефонную станцию, размещенную в городе) точкой. Введя подходящую систему декартовых координат, мы запишем положение i-го города, парой координат ( ). Условие, что страна плоская, означает, что — расстояние от i-го города, до j-го, задается формулой

     

     В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-м, а j-й с k-м, то i-й связан с k-м. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. Уточненную задачу можно теперь переформулировать в терминах теории графов.

     В терминах теории графов задача Прима-Краскала выглядит следующим образом:

     Дан полный граф с n вершинами, длины ребер определяются по формуле (1), где - координаты вершин. Найти остовное дерево минимальной длины.

     В таком виде задача была поставлена и решена Примом (1961). Краскал, одновременно и независимо, поставил и решил задачу не для плоского случая, где расстояния определяются по формуле (1), а для произвольных положительных . При этом для некоторых пар индексов , что означает отсутствие ребра, т.е. рассматривается любой граф, а не только полный.

     Итак, вышеприведенный вариант есть, строго говоря, задача Прима, а задача Краскала звучит так: Дан граф с n вершинами; длины ребер заданы матрицей D[i,j]. Найти остовное дерево минимальной длины.

     Обе перечисленные задачи решаются одним  алгоритмом, причем алгоритмом самой  примитивной разновидности.

     Представим  себе, что зимовщику оставлен некоторый  запас продуктов, и его задачей  является составление вкусного меню на всю зиму. Если зимовщик начнет с того, что сперва будет есть самую вкусную еду (например, шоколад), потом — вторую по вкусности (например, мясо), то он рискует оставить на последний месяц только соль и маргарин. Подобным образом, если оптимальный (для определенности, минимальный) объект строится как-то по шагам, то нельзя на первом шаге выбирать что-то самое малое, на втором шаге — оставшееся самое малое и т. д. За такую политику обычно приходится жестоко расплачиваться на последних шагах. Алгоритм, который мы привели, называется жадным.