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

Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г

–конечное подмножество прямого произведения Х*Х . При этом Х

называется множеством вершин , а Г - множеством дуг графа G .

Любое конечное множество точек (вершин), некоторые из которых попарно

соединены стрелками , (в теории графов эти стрелки называются дугами),

можно рассматривать как граф.

Если в множестве Г все пары упорядочены, то такой граф называют

ориентированным .

Дуга- ребро ориентированного графа.

Граф называется вырожденным, если у него нет рёбер.

Вершина Х называется инцидентной ребру G , если ребро соединяет эту

вершину с какой-либо другой вершиной.

Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 ?V

и множеством ребер (дуг) E1? E, - такими, что каждое ребро (дуга) из E1

инцидентно (инцидентна) только вершинам из V1 . Иначе говоря, подграф

содержит некоторые вершины исходного графа и некоторые рёбра (только те,

оба конца которых входят в подграф).

Подграфом, порождённым множеством вершин U называется подграф, множество

вершин которого – U, содержащий те и только те рёбра, оба конца которых

входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает

с множеством вершин самого графа.

Вершины называются смежными , если существует ребро , их соединяющее.

Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная

одновременно G1 и G2.

Каждый граф можно представить в пространстве множеством точек,

соответствующих вершинам, которые соединены линиями, соответствующими

ребрам (или дугам - в последнем случае направление обычно указывается

стрелочками). - такое представление называется укладкой графа.

Доказано, что в 3-мерном пространстве любой граф можно представить в виде

укладки таким образом, что линии, соответствующие ребрам (дугам) не будут

пересекаться во внутренних точках. Для 2-мерного пространства это, вообще

говоря, неверно. Допускающие представление в виде укладки в 2-мерном

пространстве графы называют плоскими (планарным).

Другими словами, планарным называется граф, который может быть изображен

на плоскости так, что его рёбра не будут пересекаться.

Гранью графа, изображенного на некоторой поверхности, называется часть

поверхности, ограниченная рёбрами графа.

Данное понятие грани, по - существу, совпадает с понятием грани

многогранника. В качестве поверхности в этом случае выступает поверхность

многогранника. Если многогранник выпуклый, его можно изобразить на

плоскости, сохранив все грани. Это можно наглядно представить следующим

образом: одну из граней многогранника растягиваем, а сам многогранник

«расплющиваем» так, чтобы он весь поместился внутри этой грани. В

результате получим плоский граф. Грань, которую мы растягивали «исчезнет»,

но ей будет соответствовать грань, состоящая из части плоскости,

ограничивающей граф.

Таким образом, можно говорить о вершинах, рёбрах и гранях

многогранника, а оперировать соответствующими понятиями для плоского графа.

Пустым называется граф без рёбер. Полным называется граф, в котором каждые

две вершины смежные.

Конечная последовательность необязательно различных рёбер E1,E2,...En

называется маршрутом длины n, если существует последовательность V1, V2,

... Vn необязательно различных вершин, таких, что Ei = (Vi-1,Vi ).

Если совпадают, то маршрут замкнутый.

Маршрут, в котором все рёбра попарно различны, называется цепью.

Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все

вершины цепи или цикла различны, то такая цепь или цикл называются

простыми.

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

Цикл, в котором все вершины, кроме первой и последней, попарно различны,

называется простым циклом.

Граф называется связным, если для любых двух вершин существует путь,

соединяющий эти вершины.

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

связных подграфах) графа G называется компонентой связности. Несвязный граф

имеет, по крайней мере, две компоненты связности.

Граф называется k - связным (k - реберно - связным), если удаление не менее

k вершин (ребер) приводит к потере свойства связности.

Маршрут, содержащий все вершины или ребра графа и обладающий определенными

свойствами, называется обходом графа.

Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их

прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в

графе G, называется расстоянием d (vi, vj) между vi и vj.

Степень вершины - число ребер, которым инцидентна вершина V, обозначается

D(V).

С помощью различных операций можно строить графы из более простых,

переходить от графа к более простому, разбивать графы на более простые и

т.д.

Среди одноместных операций наиболее употребительны: удаление и

добавление ребра или вершины, стягивание ребра (отождествление пары смежных

вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w,

v), где w - новая вершина) и др.

Известны двуместные операции: соединение, сложение, различные виды

умножений графов и др. Такие операции используются для анализа и синтеза

графов с заданными свойствами.

Два графа G1=(V1;E1), G2=(V2;E2),называются изоморфными, если существует

взаимнооднозначное соответствие между множествами вершин V1 и V2 и между

множествами рёбер Е1 и Е2, такое, чтобы сохранялось отношение

инцидентности.

Понятие изоморфизма для графов имеет наглядное толкование.

Представим рёбра графов эластичными нитями, связывающими узлы – вершины.

Тогда, изоморфизм можно представить как перемещение узлов и растяжение

нитей.

Теорема 1.

Пусть задан граф G=(V;E),где V - множество вершин, E - множество

рёбер, тогда 2[E]=?(V), т.е. удвоенное количество рёбер равно сумме

степеней вершин.

Теорема 2. (Лемма о рукопожатиях)

В конечном графе число вершин нечетной степени чётно.

Теорема 3.

Граф связен тогда и только тогда, когда множество его вершин нельзя

разбить на два непустых подмножества так, чтобы обе граничные точки каждого

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

Расстоянием между двумя вершинами связного графа называется

длина кратчайшей цепи, связывающей эти вершины (в количестве рёбер).

Свойства связных графов.

1. Связный граф остается связным после удаления ребра тогда

и только тогда, когда это ребро содержится в цикле.

2. Связный граф , имеющий К вершин , содержит по крайней мере К-1

ребро.

3. В связном графе любые две простые цепи максимальной длины имеет

по крайней мере одну общую вершину.

4. В графе с N вершинами и К компонентами связности число рёбер не

превышает 1/2(N-K)(N-K+1).

5. Пусть у графа G есть N вершин . Пусть D(G)- минимальная из

степеней вершин этого графа . Тогда D(G) > 1/2 (N-1).

Связный граф без циклов называется деревом.

Деревья особенно часто возникают на практике при изображении

различных иерархий. Например, популярные генеалогические деревья.

Пример(генеалогическое дерево): На рисунке показано библейское

генеалогическое дерево.

Эквивалентные определения дерева.

1. Связный граф называется деревом, если он не имеет циклов.

2. Содержит N-1 ребро и не имеет циклов.

3. Связный и содержит N-1 ребро.

4. Связный и удаление одного любого ребра делает его несвязным.

5. Любая пара вершин соединяется единственной цепью.

6. Не имеет циклов и добавление одного ребра между любыми двумя

вершинами приводит к появлению одного и только одного цикла.

1

Раскраска графов

Раскраской графа G = (V,E) называется отображение D: V( N . Раскраска

называется правильной, если образы любых двух смежных вершин различны: D

(U) ? D (V), если (U,V) ( I. Хроматическим числом графа называется

минимальное количество красок, необходимое для правильной раскраски графа.

Теорема 5.

Граф является планарным тогда и только тогда, когда он не содержит

подграфа, изоморфного одному из следующих (графы Понтрягина -

Куратовского).

Граф К33

Граф К5

Свойство: В любом планарном графе существует вершина, степень

которой.

Так как мы рассматриваем только простые графы, граф нам проще

определять как модель, носителем которой является множество вершин, а

отношение – бинарное отношение смежности вершин. Тогда данный граф

запишется как . В таком представлении ребру

соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру.

Чтобы задать такое представление, достаточно для каждого ребра указать

двухэлементное множество вершин – его мы и будем отождествлять с ребром.

Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и

граф мы будем записывать как пару (V,E), где V – множество вершин, а E –

множество рёбер.

5. Наконец, граф можно задать посредством списков.

Например:

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

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

вершин.

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

1

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

Развитие теории графов в основном обязано большому числу всевозможных

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

одно из первых мест в качестве формальных моделей реальных систем.

Графы нашли применение практически во всех отраслях научных знаний:

физике, биологии, химии, математике, истории, лингвистике, социальных

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

используются при исследовании коммуникационных сетей, систем информатики,

химических и генетических структур, электрических цепей и других систем

сетевой структуры.

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

приложения:

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

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

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

анализ пропускной способности коммуникационной сети

организация движения в динамической сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью

задача о распределении работ

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

оптимизация структуры ПЗУ

размещение диспетчерских пунктов городской транспортной сети

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

распределение памяти в ЭВМ

проектирование сетей телевизионного вещания

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

проектирование кратчайшей коммуникационной сети

синтез структурно-надежной сети циркуляционной связи

анализ надежности стохастических сетей связи

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

структурный синтез линейных избирательных цепей

автоматизация контроля при проектировании БИС

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

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

покрытие схемы заданным набором типовых подсхем

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

конструктивное перечисление структурных изомеров для

производных органических соединений

синтез тестов цифровых устройств

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

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

Будем рассматривать ориентированные графы G = , дугам которых

приписаны веса. Это означает, что каждой дуге ?E поставлено в

соответствие некоторое вещественное число a (u, v), называемое весом данной

дуги.

Нас будет интересовать нахождение кратчайшего пути между

фиксированными вершинами s, t ?V. Длину такого кратчайшего пути мы будем

обозначать d (s, t) и называть расстоянием от s до t (расстояние,

определенное таким образом, может быть отрицательным). Если не существует

ни одного пути из s в t, то полагаем d (s, t) = + . Если каждый контур

нашего графа имеет положительную длину, то кратчайший путь будет всегда

элементарным путем, т.е. в последовательности v1,..., vp не будет повторов.

С другой стороны, если в графе существует контур отрицательной длины,

то расстояние между некоторыми парами вершин становится неопределенным,

потому что, обходя этот контур достаточное число раз, мы можем показать

путь между этими вершинами с длиной, меньшей произвольного вещественного

числа. В таком случае, можно было бы говорить о длине кратчайшего

элементарного пути, однако задача, поставленная таким образом, вероятно

будет значительно более сложной, так как, в частности, она содержит в себе

задачу существования гамильтонова пути.

Можно дать много практических интерпретаций задачи о кратчайших

путях. Например, вершины могут соответствовать городам, а каждая дуга -

некоторому пути, длина которого представлена весом дуги. Мы ищем затем

кратчайшие пути между городами. Вес дуги также может соответствовать

стоимости (или времени) передачи информации между вершинами. В таком случае

мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну

ситуацию получаем, когда вес дуги равен вероятности p(u, v)

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

аварии каналов не зависят друг от друга, то вероятность исправности пути

передачи информации равна произведению вероятностей составляющих его дуг.

Задачу нахождения наиболее надежного пути легко можно свести к задаче о

кратчайшем пути, заменяя веса p(u, v) на a (u, v) = - lg p(u, v).

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а

не самих путей. Однако, зная расстояние, мы можем при условии положительной

длины всех контуров легко определить кратчайшие пути. Для этого достаточно

отметить, что для произвольных s, t ? V (s , t) существует вершина v, такая

что d (s, t) = d (s, v) + a (v, t).

Действительно, таким свойством обладает предпоследняя вершина

произвольного кратчайшего пути из s в t.

Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a

(u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная

таким образом последовательность t, v, u, ... не сожержит повторений и

оканчивается вершиной s.

Очевидно, что она определяет (при обращении очередности) кратчайший

путь из s в t.

Таким образом, мы получаем следующий алгоритм:

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

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных

вершин v ? V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v

?V.

Результаты: СТЕК содержит последовательность вершин, определяющую

кратчайший путь из s в t.

begin

CTEK := ? ; CTEK ? t; v:= t;

while v ? s do

begin

u := вершина, для которой D[v] = D[u] + A[u, v];

CTEK ? u;

v:= u

end

end.

Пусть -ориентированный граф, | V| = n, | E| = m. Если выбор

вершины u происходит в результате просмотра всех вершин, то сложность

нашего алгоритма - O(n2). Если мы просматриваем только список ПРЕДШ[v],

содержащий все вершины u, такие что u (?) v, то в этом случае сложность

будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем

пути в неориентированном графе легко сводится к аналогичной задаче для

некоторого ориентированного графа. С этой целью достаточно заменить каждое

ребро {u, v}двумя дугами ? u, v?и ?v, u? , каждая с таким же весом, что и

{u, v}. Однако в случае неположительных весов это приводит к возникновению

контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E>является

ориентированным графом, |V| = n, |E| = m. В целях упрощения изложения и

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

исключать ситуации, при которых «большинство» вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A[u,

v], u, v ? V (A[u, v] содержит вес a (u, v)).

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

Большинство известных алгоритмов нахождения расстояния между двумя

фиксированными вершинами 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] равно

Страницы: 1, 2, 3, 4