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

Так, на рис. 5 последовательности дуг

а₆, а₅, а₉, а₈, а₄. (1)

а₁, а₆, а₅, а₉. (2)

а₁, а₆, а₅, а₉, а₁₀, а₆, а₄. (3)

являются путями.

Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а₆ в нем используется дважды.

Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет.

Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер а₁, а₂,..., а_q, в которой каждое ребро а_q за исключением первого и последнего ребер, связано с ребрами а_i-1 и а_i+1 своими концевыми вершинами. Последовательности дуг:

а₂, а₄, а₈, а₁₀, (4)

а₂, а₇, а₈, а₄, а₃, (5)

а₁₀ , а₇ , а₄ , а₈ , а₇ , а₂. (6)

в графе, изображенном на рис. 5, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х₂, х₅, х₄, х₃, х₅, х₆.

Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным.

Связный граф без циклов называется деревом. Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярные генеалогические деревья. Пример – генеалогическое дерево. Эквивалентные определения дерева.1. Связный граф называется деревом, если он не имеет циклов. 2. Содержит N-1 ребро и не имеет циклов. 3. Связный и содержит N-1 ребро. 4. Связный и удаление одного любого ребра делает его несвязным.5. Любая пара вершин соединяется единственной цепью. 6. Не имеет циклов и добавление одного ребра между любыми двумя вершинами приводит к появлению одного и только одного цикла.

2. Способы задания графа

1. Геометрический: 2. Матрицей смежности:

A	В	C	D
A	0	1	1	0
B	1	0	1	0
C	1	1	0	1
D	0	0	1	0

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

А	В	С	D
A	1	1	0	0
B	0	1	1	0
C	1	0	1	0
D	0	0	1	1

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 (вершина уже рассмотрена);