Викиконспекты - Вклад участника [ru]

Алгоритм Джонсона

2012-10-15T18:38:42Z

109.205.252.183: /* Теорема о существовании потенциальной функции */

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

== Алгоритм ==

=== Описание ===

Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2\log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее алгоритма Флойда. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.

В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \omega_\varphi </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой '''потенциальной''' функции.

{{Определение
|definition=
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> - произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
}}

Такая потенциальная функция строится при помощи добавлении фиктивной вершины в <tex> G </tex>, из которой проведены ребра нулевого веса во все остальные вершины и запуском алгоритма Форда-Беллмана из нее. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.

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

=== Сохранение кратчайших путей ===
Утверждается, что если какой-то путь <tex> P </tex> был кратчайшим относительно весовой функции <tex> \omega </tex>, то он будет кратчайшим и относительно новой весовой функции <tex> \omega_\varphi </tex>.

{{Лемма
|statement=
Пусть <tex>P,\; Q </tex> {{---}} 2 пути <tex> a \rightsquigarrow b\;</tex> и <tex>\omega(P) < \omega(Q).</tex> Тогда <tex>\forall \varphi: \; \omega_\varphi(P) < \omega_\varphi(Q)</tex>
|proof=

:Рассмотрим путь <tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>

:Его вес с новой весовой функцией равен <tex>\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + ... + \omega_\varphi(u_{k-1}u_k) </tex>.

:Вставим определение функции <tex> \omega_\varphi : \omega_\varphi(P) = \varphi(u_0) + \omega(u_0u_1) - \varphi(u_1) + ... + \varphi(u_{k-1}) + \omega(u_{k-1}u_k) - \varphi(u_k) </tex>

:Заметим, что потенциалы все промежуточных вершин в пути сократятся. <tex> \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)</tex>

:По изначальному предположению: <tex>\omega(P) < \omega(Q)</tex>. С новой весовой функцией веса соответствующих путей будут:

:<tex>\omega_\varphi(P) = \varphi(a) + \omega(P) - \varphi(b)</tex>

:<tex>\omega_\varphi(Q) = \varphi(a) + \omega(Q) - \varphi(b)</tex>

:Отсюда, <tex>\omega_\varphi(P) < \omega_\varphi(Q)</tex>
}}

=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=

В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; \omega_\varphi(uv) \ge 0 </tex>

|proof=

<tex>\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> - цикл в графе <tex>G</tex>

:По лемме, его вес равен <tex> \omega(C) = \omega_\varphi(C) - \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \ge 0</tex>

<tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex> 0 </tex> для всех <tex> u </tex>.

:Обозначим <tex>\delta(u,v)</tex> как минимальное расстояние между вершинами <tex>u,\; v</tex>.

:Введем потенциальную функцию <tex> \phi </tex> следующим образом: <tex>\phi(u) = \delta(s,u)</tex>

:Рассмотрим вес произвольного ребра <tex> uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, v)</tex>.

:Поскольку <tex>\delta(s, u) + \omega(uv) </tex> {{---}} вес какого-то пути <tex> s \rightsquigarrow v </tex>, а <tex> \delta(s, v) </tex> {{---}} вес кратчайшего пути <tex> s \rightsquigarrow v</tex>, то <tex> \delta(s, u) + \omega(uv) \ge \delta(s, v) \Rightarrow \delta(s, u) + w\omega(uv) - \delta(s, v) = \omega_\varphi(uv) \ge 0 </tex>.

}}

=== Псевдокод ===

Алгоритм Джонсона

Строится граф <tex>G' = (V',\;E')</tex>, где <tex>V' = V \cup \{s\}</tex>,
для некоторой новой вершины <tex>s \not\in V</tex>, а <tex>E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V \}</tex>
'''if''' Bellman_Ford<tex>(G',\;\omega,\;s)</tex> == FALSE
'''then''' out << «Входной граф содержит цикл с отрицательным весом»
'''else''' '''for''' для каждой <tex>v \in V'</tex>
'''do''' присвоить величине <tex>\varphi(v)</tex> значение <tex>\delta(s,\;v)</tex>,
вычисленное алгоритмом Беллмана — Форда
'''for''' для каждого ребра <tex>(u,\;v) \in E'</tex>
'''do''' <tex>\omega_\varphi(u,\;v) \leftarrow \omega(u,\;v) + \varphi(u) - \varphi(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;\omega_\varphi,\;u)</tex> величин <tex>\delta_\varphi(u,\;v)</tex>
для всех вершин <tex>v \in V</tex>
'''for''' для каждой вершины <tex>v \in V</tex>
'''do''' <tex>d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex>
'''return''' <tex>d</tex>

Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.

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

== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> - время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [[Фибоначчиевы кучи| фибоначчиевой кучи]], то время работы алгоритма Джонсона есть <tex>O(V^2\log V + V E)</tex>.

== См. также ==
* [[Алгоритм Дейкстры]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Флойда]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Отношение связности, компоненты связности

2012-09-10T12:09:37Z

109.205.252.183: /* Случай неориентированного графа */

== Случай неориентированного графа ==

{{Определение
|definition=
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связными''', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow v </tex>).}}

{{Теорема
|statement=
Связность - '''отношение эквивалентности'''.
|proof=
'''Рефлексивность''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).

'''Симметричность''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа).

'''Транзитивность''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex>. Действительно, сначала пройдем от <tex>a</tex> до <tex>b</tex>, затем от <tex>b</tex> до <tex>c</tex>, что и означает существования пути <tex>a \rightsquigarrow c</tex>.
}}

{{Определение
|definition=
'''Компонентой связности''' называется класс эквивалентности относительно связности.}}

{{Определение
|definition=
Граф <tex>G=(V, E)</tex> называется '''связным''', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}

== Случай ориентированного графа ==
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
=== Слабая связность ===
<wikitex>{{Определение
|definition=
Отношение $R(v, u)$ называется отношением '''слабой связности''', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением с ребер ориентации.
}}

{{Теорема
|statement=
Слабая связность '''является отношением эквивалентности'''.
|proof=
Аналогично доказательству соответствующей теоремы для неориентированного графа.
}}
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]
<br clear="all" />
</wikitex>

=== Сильная связность ===
{{Определение
|id=sc_def
|definition=
Отношение <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности'''.
}}

{{Теорема
|statement=
Сильная связность {{---}} '''отношение эквивалентности'''.
|proof=
'''Рефлексивность''' и '''симметричность''' очевидны. Рассмотрим '''транзитивность''':
<tex>(a\rightsquigarrow b \land b\rightsquigarrow a) \land (b\rightsquigarrow c \land c\rightsquigarrow b)\Leftrightarrow (a\rightsquigarrow b \land b\rightsquigarrow c) \land (c\rightsquigarrow b \land b\rightsquigarrow a) \Leftrightarrow a\rightsquigarrow c \land c\rightsquigarrow a</tex>
}}

{{Определение
|definition=
Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компонентой сильной связности''' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]
{{Определение
|definition=
Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}}

<br clear="all" />

==Источники==
* [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru]
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]

Отношение связности, компоненты связности

2012-09-10T12:06:58Z

109.205.252.183: /* Случай неориентированного графа */

== Случай неориентированного графа ==

{{Определение
|definition=
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связными''', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow v </tex>).}}

{{Теорема
|statement=
Связность - '''отношение эквивалентности'''.
|proof=
'''Рефлексивность''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).

'''Симметричность''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа).

'''Транзитивность''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex>. Действительно, сначала пройдем от <tex>a</tex> до <tex>b</tex>, затем от <tex>b</tex> до <tex>c</tex>, что и означает существования пути <tex>a \rightsquigarrow с</tex>.
}}

{{Определение
|definition=
'''Компонентой связности''' называется класс эквивалентности относительно связности.}}

{{Определение
|definition=
Граф <tex>G=(V, E)</tex> называется '''связным''', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}

== Случай ориентированного графа ==
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
=== Слабая связность ===
<wikitex>{{Определение
|definition=
Отношение $R(v, u)$ называется отношением '''слабой связности''', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением с ребер ориентации.
}}

{{Теорема
|statement=
Слабая связность '''является отношением эквивалентности'''.
|proof=
Аналогично доказательству соответствующей теоремы для неориентированного графа.
}}
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]
<br clear="all" />
</wikitex>

=== Сильная связность ===
{{Определение
|id=sc_def
|definition=
Отношение <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности'''.
}}

{{Теорема
|statement=
Сильная связность {{---}} '''отношение эквивалентности'''.
|proof=
'''Рефлексивность''' и '''симметричность''' очевидны. Рассмотрим '''транзитивность''':
<tex>(a\rightsquigarrow b \land b\rightsquigarrow a) \land (b\rightsquigarrow c \land c\rightsquigarrow b)\Leftrightarrow (a\rightsquigarrow b \land b\rightsquigarrow c) \land (c\rightsquigarrow b \land b\rightsquigarrow a) \Leftrightarrow a\rightsquigarrow c \land c\rightsquigarrow a</tex>
}}

{{Определение
|definition=
Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компонентой сильной связности''' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]
{{Определение
|definition=
Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}}

<br clear="all" />

==Источники==
* [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru]
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]