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

Теорема Редеи-Камиона

2012-02-29T07:27:46Z

Chuprikov Pavel:

{{Теорема
|about=
Редеи-Камиона (для пути)
|statement=
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].
|proof=
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.

 ''База индукции:'' 

Очевидно, для <tex> n = 3 </tex> утверждение верно.

 ''Индукционный переход:'' 

Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.

Пусть <tex> u </tex> – произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>.
[[Файл: Redei_kamion_3.png|250px|thumb|center]]

Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> - гамильтонов.
[[Файл: Redei_kamion_4.png|250px|thumb|center|Красным цветом выделен искомый путь]]

Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> - первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.
[[Файл: Redei_kamion_5.png|250px|thumb|center|Красным цветом выделен искомый путь]]

Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> - гамильтонов.
[[Файл: Redei_kamion_6.png|250px|thumb|center|Красным цветом выделен искомый путь]]

Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
}}

{{Теорема
|about=
Редеи-Камиона (для цикла)
|statement=
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].
|proof=
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> - количество вершин в графе.

 ''База индукции:'' 

{{Утверждение
|statement=
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.
|proof=
Пусть <tex> u </tex> - произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.
[[Файл: Redei_kamion_1.png|250px|thumb|center]]

<tex> T </tex> сильно связен, следовательно:
# <tex> V_1 \neq \emptyset </tex>, (иначе <tex> v </tex> - исток турнира)
# <tex> V_2 \neq \emptyset </tex>, (иначе <tex> v </tex> - сток турнира)
# <tex> \exists e = (w_2, w_1) \in ET </tex>, (иначе нет пути из <tex>V_2</tex> в <tex>V_1</tex>):
#* <tex> w_1 \in V_1 </tex>,
#* <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_2.png|250px|thumb|center|Красным цветом выделен цикл длины <tex> 3 </tex>]]

Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> - искомый цикл длины <tex> 3 </tex>, q.e.d.
}}

 ''Индукционный переход:'' 

{{Утверждение
|statement=
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.
|proof=
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.

Пусть <tex> v_0 : v_0 \notin S_k </tex> и верно, что <tex> \exists u, w \in S_k </tex>:
* <tex> (v_0, u) \in ET </tex>,
* <tex> (w, v_0) \in ET </tex>.

Рассмотрим два случая:
# существует такая вершина <tex> v_0 </tex>,
# не существует такой вершины <tex> v_0 </tex>.
Заметим, что при <tex>k = n - 1</tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.

 Первый случай: 

Пусть <tex> v_1 </tex> - вершина из <tex> S_k </tex> такая, что ребро <tex> e = (v_1, v_0 ) \in ET </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i ) \in ET </tex>.
[[Файл: Redei_kamion_7.png|250px|thumb|center]]

Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
[[Файл: Redei_kamion_8.png|250px|thumb|center|Красным цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]

Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.

 Второй случай: 

Пусть:
* <tex> V_1 = \{ u \in VT | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,
* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.
[[Файл: Redei_kamion_9.png|250px|thumb|center]]

Турнир сильно связен, следовательно:
* <tex> V_1 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> {v_1, \ldots, v_k} </tex>)
* <tex> V_2 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> {v_1, \ldots, v_k} </tex> и концом в <tex> V_1 </tex>)
* <tex> \exists g = (w_2, w_1) \in ET </tex>, (иначе <tex>T</tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex>V_2</tex> и концом в <tex>V_1</tex>):
** <tex> w_1 \in V_1 </tex>,
** <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_10.png|250px|thumb|center|Красным цветом выделен цикл длины <tex> k + 1 </tex>]]
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.

В любом случае утверждение верно, q.e.d.

}}
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geq 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.
}}

{{Лемма
|about=
Следствие
|statement=
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.
}}

==См. также==
* [[Гамильтоновы графы]]
* [[Турниры]]

== Литература ==
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
* Ф. Харари: ''Теория графов''

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

Теорема Редеи-Камиона

2012-02-29T07:11:25Z

Chuprikov Pavel:

{{Теорема
|about=
Редеи-Камиона (для пути)
|statement=
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].
|proof=
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.

 ''База индукции:'' 

Очевидно, для <tex> n = 3 </tex> утверждение верно.

 ''Индукционный переход:'' 

Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.

Пусть <tex> u </tex> – произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>.
[[Файл: Redei_kamion_3.png|250px|thumb|center]]

Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> - гамильтонов.
[[Файл: Redei_kamion_4.png|250px|thumb|center|Красным цветом выделен искомый путь]]

Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> - первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.
[[Файл: Redei_kamion_5.png|250px|thumb|center|Красным цветом выделен искомый путь]]

Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> - гамильтонов.
[[Файл: Redei_kamion_6.png|250px|thumb|center|Красным цветом выделен искомый путь]]

Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
}}

{{Теорема
|about=
Редеи-Камиона (для цикла)
|statement=
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].
|proof=
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> - количество вершин в графе.

 ''База индукции:'' 

{{Утверждение
|statement=
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.
|proof=
Пусть <tex> u </tex> - произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.
[[Файл: Redei_kamion_1.png|250px|thumb|center]]

<tex> T </tex> сильно связен, следовательно:
# <tex> V_1 \neq \emptyset </tex>, (иначе <tex> v </tex> - исток турнира)
# <tex> V_2 \neq \emptyset </tex>, (иначе <tex> v </tex> - сток турнира)
# <tex> \exists e = (w_2, w_1) \in ET </tex>, (иначе нет пути из <tex>V_2</tex> в <tex>V_1</tex>):
#* <tex> w_1 \in V_1 </tex>,
#* <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_2.png|250px|thumb|center|Красным цветом выделен цикл длины <tex> 3 </tex>]]

Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> - искомый цикл длины <tex> 3 </tex>, q.e.d.
}}

 ''Индукционный переход:'' 

{{Утверждение
|statement=
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.
|proof=
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.

Пусть <tex> v_0 \notin S_k </tex> такая, что <tex> \exists u, w \in S_k </tex>:
* <tex> (v_0, u) \in ET </tex>,
* <tex> (w, v_0) \in ET </tex>.

Рассмотрим два случая:
# существует такая вершина <tex> v_0 </tex>,
# не существует такой вершины <tex> v_0 </tex>.
Заметим, что при <tex>k = n - 1</tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.

 Первый случай: 

Пусть <tex> v_1 </tex> - вершина из <tex> S_k </tex> такая, что ребро <tex> e = (v_1, v_0 ) \in ET </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i ) \in ET </tex>.
[[Файл: Redei_kamion_7.png|250px|thumb|center]]

Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
[[Файл: Redei_kamion_8.png|250px|thumb|center|Красным цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]

Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.

 Второй случай: 

Пусть:
* <tex> V_1 = \{ u \in VT | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,
* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.
[[Файл: Redei_kamion_9.png|250px|thumb|center]]

Турнир сильно связен, следовательно:
* <tex> V_1 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> {v_1, \ldots, v_k} </tex>)
* <tex> V_2 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> {v_1, \ldots, v_k} </tex> и концом в <tex> V_1 </tex>)
* <tex> \exists g = (w_2, w_1) \in ET </tex>, (иначе <tex>T</tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex>V_2</tex> и концом в <tex>V_1</tex>):
** <tex> w_1 \in V_1 </tex>,
** <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_10.png|250px|thumb|center|Красным цветом выделен цикл длины <tex> k + 1 </tex>]]
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.

В любом случае утверждение верно, q.e.d.

}}
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geq 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.
}}

{{Лемма
|about=
Следствие
|statement=
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.
}}

==См. также==
* [[Гамильтоновы графы]]
* [[Турниры]]

== Литература ==
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
* Ф. Харари: ''Теория графов''

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

Обсуждение:Алгоритм Куна для поиска максимального паросочетания

2012-02-22T16:36:43Z

Chuprikov Pavel:

1) Дефисы, где следует, заменить на тире.

2) Можно убрать фразы про "разобьем на 2 доли" и т. д. Ясно, что алгоритм работает только на двудольных графах и можно сразу оперировать правой и левой долями.

3) Так как подробное описание краткое, то краткое, думаю, можно уничтожить что бы не читать два раза одно и тоже.

4) В алгоритме заменить (где это возможно) явную индексацию на теоретико-множественные операции. Ведь и так понятно как на самом деле можно реализовать ту или иную операцию. Название переменных лучше не сокращать.

5) v = 1...n1 - нехорошо. т. к. левый операнд типа вершина правый операнд - число.

6) Вместо пытаемся насытить - запускаем поиск увеличивающей цепи, нашли - делаем А, нет - делаем Б.

7) В поиске увеличивающей цепи не надо говорить: "Изначально стоим там-то" Это слышится как глас сверху: "встань в вершину v, о чудесный дфс, если это первый твой запуск". вершина v (лучше видимо u что бы не было конфликта имен) - это параметр дфса, который не должен знать о вершине каких-то внешних данных. И соответственно не должно быть special case для ребра из начальной вершины.

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

Жалобы и предложения можно писать в обсуждения, но для уведомления нужно все-таки использовать форму.

Обсуждение:Алгоритм Куна для поиска максимального паросочетания

2012-02-22T16:35:06Z

Chuprikov Pavel:

Обсуждение:Алгоритм Куна для поиска максимального паросочетания

2012-02-22T16:33:11Z

Chuprikov Pavel: Новая страница: «1) Дефисы, где следует, заменить на тире. 2) Можно убрать фразы про "разобьем на 2 доли" и т. д....»

1) Дефисы, где следует, заменить на тире.
2) Можно убрать фразы про "разобьем на 2 доли" и т. д. Ясно, что алгоритм работает только на двудольных графах и можно сразу оперировать правой и левой долями.
3) Так как подробное описание краткое, то краткое, думаю, можно уничтожить что бы не читать два раза одно и тоже.
4) В алгоритме заменить (где это возможно) явную индексацию на теоретико-множественные операции. Ведь и так понятно как на самом деле можно реализовать ту или иную операцию. Название переменных лучше не сокращать.
5) v = 1...n1 - нехорошо. т. к. левый операнд типа вершина правый операнд - число.
6) Вместо пытаемся насытить - запускаем поиск увеличивающей цепи, нашли - делаем А, нет - делаем Б.
7) В поиске увеличивающей цепи не надо говорить: "Изначально стоим там-то" Это слышится как глас сверху: "встань в вершину v, о чудесный дфс, если это первый твой запуск". вершина v (лучше видимо u что бы не было конфликта имен) - это параметр дфса, который не должен знать о вершине каких-то внешних данных. И соответственно не должно быть special case для ребра из начальной вершины.

Файл:Two ways to cycle.png

2012-01-20T16:33:15Z

Chuprikov Pavel:

Обсуждение:Теорема о существовании простого цикла в случае существования цикла

2012-01-20T16:17:33Z

Chuprikov Pavel: Новая страница: «Еще нужны рисунки...»

Еще нужны рисунки...

Эйлеровость графов

2011-12-29T22:02:19Z

Chuprikov Pavel: /* Источники */

==Эйлеров путь==
{{Определение|definition=
'''Эйлеровым путем''' в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}

==Эйлеров обход==
{{Определение|definition=
'''Эйлеров обход''' {{---}} обход графа, посещающий эйлеров путь.
}}

==Эйлеров цикл==
{{Определение|definition=
'''Эйлеров цикл''' {{---}} замкнутый эйлеров путь.
}}

==Эйлеров граф==
{{Определение|definition=
Граф называется '''эйлеровым''', если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
}}

==Критерий эйлеровости==
{{Теорема
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Все вершины имели четную степень.

2. Все компоненты связности кроме, может быть одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
}}

{|
|[[Файл:not_euler.png|200px|thumb| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
|[[Файл:not_euler2.png|200px|thumb| Две компоненты связности, одна имеет ребра.]]
|}

{{Теорема
|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Все вершины имеют четную степень.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

|proof=

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>.

База индукции: <tex>n = 0</tex> цикл существует.

Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.

Рассмотрим связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны.

Допустим, что <tex>v_1</tex> и <tex>v_2</tex> {{---}} вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Поскольку степень <tex>v_2</tex> {{---}} чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, и эйлеров цикл можно считать построенным. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> {{---}} подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. Заметим что <tex>G'</tex> может состоять из нескольких компонент связности.

Рассмотрим какую-либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.

}}

'''Следствие:'''

В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

====[[Основные определения теории графов|Ориентированный граф]]====
{{Теорема
|statement=
В ориентированном графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
|proof=
Доказательство аналогично случаю неориентированного графа.
}}

'''Следствие:'''

В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>deg^+ - deg^- = 1</tex>, а для другой <tex>deg^+ - deg^- = -1</tex>.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

==Источники==

* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977.

==См. Также==

* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
* [[Алгоритм построения Эйлерова цикла]]

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

Эйлеровость графов

2011-12-29T22:02:03Z

Chuprikov Pavel: /* Источники */

==Эйлеров путь==
{{Определение|definition=
'''Эйлеровым путем''' в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}

==Эйлеров обход==
{{Определение|definition=
'''Эйлеров обход''' {{---}} обход графа, посещающий эйлеров путь.
}}

==Эйлеров цикл==
{{Определение|definition=
'''Эйлеров цикл''' {{---}} замкнутый эйлеров путь.
}}

==Эйлеров граф==
{{Определение|definition=
Граф называется '''эйлеровым''', если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
}}

==Критерий эйлеровости==
{{Теорема
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Все вершины имели четную степень.

2. Все компоненты связности кроме, может быть одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
}}

{|
|[[Файл:not_euler.png|200px|thumb| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
|[[Файл:not_euler2.png|200px|thumb| Две компоненты связности, одна имеет ребра.]]
|}

{{Теорема
|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Все вершины имеют четную степень.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

|proof=

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>.

База индукции: <tex>n = 0</tex> цикл существует.

Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.

Рассмотрим связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны.

Допустим, что <tex>v_1</tex> и <tex>v_2</tex> {{---}} вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Поскольку степень <tex>v_2</tex> {{---}} чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, и эйлеров цикл можно считать построенным. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> {{---}} подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. Заметим что <tex>G'</tex> может состоять из нескольких компонент связности.

Рассмотрим какую-либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.

}}

'''Следствие:'''

В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

====[[Основные определения теории графов|Ориентированный граф]]====
{{Теорема
|statement=
В ориентированном графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
|proof=
Доказательство аналогично случаю неориентированного графа.
}}

'''Следствие:'''

В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>deg^+ - deg^- = 1</tex>, а для другой <tex>deg^+ - deg^- = -1</tex>.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

==Источники==

* Уилсон Р. Введение в теорию графов. {{–--}} М.: Мир, 1977.

==См. Также==

* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
* [[Алгоритм построения Эйлерова цикла]]

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

Эйлеровость графов

2011-12-29T21:58:12Z

Chuprikov Pavel: /* Критерий эйлеровости */

==Эйлеров путь==
{{Определение|definition=
'''Эйлеровым путем''' в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}

==Эйлеров обход==
{{Определение|definition=
'''Эйлеров обход''' {{---}} обход графа, посещающий эйлеров путь.
}}

==Эйлеров цикл==
{{Определение|definition=
'''Эйлеров цикл''' {{---}} замкнутый эйлеров путь.
}}

==Эйлеров граф==
{{Определение|definition=
Граф называется '''эйлеровым''', если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
}}

==Критерий эйлеровости==
{{Теорема
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Все вершины имели четную степень.

2. Все компоненты связности кроме, может быть одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
}}

{|
|[[Файл:not_euler.png|200px|thumb| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
|[[Файл:not_euler2.png|200px|thumb| Две компоненты связности, одна имеет ребра.]]
|}

{{Теорема
|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Все вершины имеют четную степень.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

|proof=

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>.

База индукции: <tex>n = 0</tex> цикл существует.

Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.

Рассмотрим связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны.

Допустим, что <tex>v_1</tex> и <tex>v_2</tex> {{---}} вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Поскольку степень <tex>v_2</tex> {{---}} чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, и эйлеров цикл можно считать построенным. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> {{---}} подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. Заметим что <tex>G'</tex> может состоять из нескольких компонент связности.

Рассмотрим какую-либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.

}}

'''Следствие:'''

В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

====[[Основные определения теории графов|Ориентированный граф]]====
{{Теорема
|statement=
В ориентированном графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
|proof=
Доказательство аналогично случаю неориентированного графа.
}}

'''Следствие:'''

В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>deg^+ - deg^- = 1</tex>, а для другой <tex>deg^+ - deg^- = -1</tex>.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

==Источники==

* Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

==См. Также==

* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
* [[Алгоритм построения Эйлерова цикла]]

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

Эйлеровость графов

2011-12-29T21:57:42Z

Chuprikov Pavel: /* Критерий эйлеровости */

==Эйлеров путь==
{{Определение|definition=
'''Эйлеровым путем''' в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}

==Эйлеров обход==
{{Определение|definition=
'''Эйлеров обход''' {{---}} обход графа, посещающий эйлеров путь.
}}

==Эйлеров цикл==
{{Определение|definition=
'''Эйлеров цикл''' {{---}} замкнутый эйлеров путь.
}}

==Эйлеров граф==
{{Определение|definition=
Граф называется '''эйлеровым''', если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
}}

==Критерий эйлеровости==
{{Теорема
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Все вершины имели четную степень.

2. Все компоненты связности кроме, может быть одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
}}

{|
|[[Файл:not_euler.png|200px|thumb| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
|[[Файл:not_euler2.png|200px|thumb| Две компоненты связности, одна имеет ребра.]]
|}

{{Теорема
|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Все вершины имеют четную степень.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

|proof=

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>.

База индукции: <tex>n = 0</tex> цикл существует.

Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.

Рассмотрим связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны.

Допустим, что <tex>v_1</tex> и <tex>v_2</tex> - вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Поскольку степень <tex>v_2</tex> {{---}} чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, и эйлеров цикл можно считать построенным. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> {{---}} подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. Заметим что <tex>G'</tex> может состоять из нескольких компонент связности.

Рассмотрим какую-либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.

}}

'''Следствие:'''

В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

====[[Основные определения теории графов|Ориентированный граф]]====
{{Теорема
|statement=
В ориентированном графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
|proof=
Доказательство аналогично случаю неориентированного графа.
}}

'''Следствие:'''

В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>deg^+ - deg^- = 1</tex>, а для другой <tex>deg^+ - deg^- = -1</tex>.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

==Источники==

* Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

==См. Также==

* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
* [[Алгоритм построения Эйлерова цикла]]

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

Эйлеровость графов

2011-12-29T21:55:38Z

Chuprikov Pavel: /* Критерий эйлеровости */

==Эйлеров путь==
{{Определение|definition=
'''Эйлеровым путем''' в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}

==Эйлеров обход==
{{Определение|definition=
'''Эйлеров обход''' {{---}} обход графа, посещающий эйлеров путь.
}}

==Эйлеров цикл==
{{Определение|definition=
'''Эйлеров цикл''' {{---}} замкнутый эйлеров путь.
}}

==Эйлеров граф==
{{Определение|definition=
Граф называется '''эйлеровым''', если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
}}

==Критерий эйлеровости==
{{Теорема
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Все вершины имели четную степень.

2. Все компоненты связности кроме, может быть одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
}}

{|
|[[Файл:not_euler.png|200px|thumb| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
|[[Файл:not_euler2.png|200px|thumb| Две компоненты связности, одна имеет ребра.]]
|}

{{Теорема
|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Все вершины имеют четную степень.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

|proof=

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>.

База индукции: <tex>n = 0</tex> цикл существует.

Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.

Рассмотрим связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны.

Допустим, что <tex>v_1</tex> и <tex>v_2</tex> - вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Поскольку степень <tex>v_2</tex> {{---}} чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, и эйлеров цикл можно считать построенным. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> {{---}} подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. Заметим что <tex>G'</tex> может состоять из нескольких компонент связности.

Рассмотрим какую {{---}} либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.

}}

'''Следствие:'''

В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

====[[Основные определения теории графов|Ориентированный граф]]====
{{Теорема
|statement=
В ориентированном графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
|proof=
Доказательство аналогично случаю неориентированного графа.
}}

'''Следствие:'''

В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>deg^+ - deg^- = 1</tex>, а для другой <tex>deg^+ - deg^- = -1</tex>.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

==Источники==

* Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

==См. Также==

* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
* [[Алгоритм построения Эйлерова цикла]]

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

Эйлеровость графов

2011-12-29T21:54:13Z

Chuprikov Pavel: /* Эйлеров цикл */

==Эйлеров путь==
{{Определение|definition=
'''Эйлеровым путем''' в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}

==Эйлеров обход==
{{Определение|definition=
'''Эйлеров обход''' {{---}} обход графа, посещающий эйлеров путь.
}}

==Эйлеров цикл==
{{Определение|definition=
'''Эйлеров цикл''' {{---}} замкнутый эйлеров путь.
}}

==Эйлеров граф==
{{Определение|definition=
Граф называется '''эйлеровым''', если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
}}

==Критерий эйлеровости==
{{Теорема
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Все вершины имели четную степень.

2. Все компоненты связности кроме, может быть одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
}}

{|
|[[Файл:not_euler.png|200px|thumb| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]
|[[Файл:not_euler2.png|200px|thumb| Две компоненты связности, одна имеет ребра.]]
|}

{{Теорема
|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Все вершины имеют четную степень.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

|proof=

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>.

База индукции: <tex>n = 0</tex> цикл существует.

Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.

Рассмотрим связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны.

Допустим, что <tex>v_1</tex> и <tex>v_2</tex> - вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Поскольку степень <tex>v_2</tex> - чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, и эйлеров цикл можно считать построенным. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> - подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. Заметим что <tex>G'</tex> может состоять из нескольких компонент связности.

Рассмотрим какую - либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.

}}

'''Следствие:'''

В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

====[[Основные определения теории графов|Ориентированный граф]]====
{{Теорема
|statement=
В ориентированном графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
|proof=
Доказательство аналогично случаю неориентированного графа.
}}

'''Следствие:'''

В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>deg^+ - deg^- = 1</tex>, а для другой <tex>deg^+ - deg^- = -1</tex>.

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

'''Доказательство:'''

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

==Источники==

* Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

==См. Также==

* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
* [[Алгоритм построения Эйлерова цикла]]

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

Алгоритм Флойда

2011-11-07T18:41:17Z

Chuprikov Pavel: /* Код (окончательный) */

'''Алгоритм Флойда (алгоритм Флойда–Уоршелла)''' {{---}} алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Этот алгоритм работает в течение времени <tex> \Theta(n^3) </tex> и использует <tex> \Theta(n^2) </tex> памяти. Разработан в 1962 году.

== Алгоритм ==
[[Файл:Floyd.png|right|thumb|Текущий (синий) путь и потенциально более короткий (красный)]]

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

Дан взвешенный ориентированный граф <tex> G(V, E) </tex>; <tex>\omega_{uv} =
\begin{cases}
\text{weight of }uv ,& \text{if } uv \in E \\
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>, в котором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>. Требуется найти матрицу кратчайших расстояний <tex> d </tex>, в которой элемент <tex> d_{ij} </tex> либо равен длине кратчайшего пути из <tex> i </tex> в <tex> j </tex>, либо равен <tex> +\infty </tex>, если вершина <tex> j </tex> не достижима из <tex> i </tex>.

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

Обозначим длину кратчайшего пути между вершинами <tex> u </tex> и <tex> v </tex>, содержащего, помимо <tex>u</tex> и <tex>v</tex>, только вершины из множества <tex> \{ 1 .. i \} </tex> как <tex>d_{uv}^{(i)}</tex>, <tex>d_{uv}^{(0)} = \omega_{uv}</tex>.

На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер {{---}} <tex> i </tex>) и для всех пар вершин <tex>u</tex> и <tex>v</tex> вычислять <tex> d_{uv}^{(i)} = min(d_{uv}^{(i-1)}, d_{ui}^{(i-1)} + d_{iv}^{(i-1)}) </tex>. То есть, если кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex>, проходит через вершину <tex>i</tex>, то кратчайшим путем из <tex> u </tex> в <tex> v </tex> является кратчайший путь из <tex> u </tex> в <tex> i </tex>, объединенный с кратчайшим путем из <tex> i </tex> в <tex> v </tex>. В противном случае, когда этот путь не содержит вершины <tex> i </tex>, кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex> является кратчайшим путем из <tex>u</tex> в <tex>v</tex>, содержащим только вершины из множества <tex> \{ 1 .. i-1 \} </tex>.

=== Код (в первом приближении) ===
# Инициализация
<tex dpi = "105"> d^{(0)} = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105" > d^{(i)}_{uv} = min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>

В итоге получаем, что матрица <tex> d^{(n)} </tex> и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества <tex> \{ 1..n \} </tex>, что есть попросту все вершины графа. Такая реализация работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^3) </tex> памяти.

=== Код (окончательный) ===
Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) == d_{uv}^{(i)} </tex>, то тогда будет выполняться и <tex> \rho(u, v) == d_{uv} </tex>.

{{Утверждение
|statement=
В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>.
|proof=

После инициализации все неравенства, очевидно, выполняются. Далее, массив <tex> d </tex> может измениться только в строчке 5.

'''Докажем второе неравенство индукцией по итерациям алгоритма.'''

Пусть также <tex>d'_{uv}</tex> - значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации.
<tex> d_{uv} \le d_{uv}^{(i)} </tex>.

Рассмотрим два случая:
* Значение <tex> d_{uv}^{(i)} </tex> стало меньше, чем <tex> d_{uv}^{(i - 1)} </tex>. Тогда <tex> d_{uv}^{(i)} = d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному предположению) <tex> \ge d'_{ui} + d'_{iv} \ge</tex> (в силу выполнения 7-ой строчки алгоритма на <tex>i</tex>-ой итерации и невозрастания элементов массива <tex> d </tex>) <tex>\ge d_{uv}</tex>.
* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.

'''Докажем первое неравенство от противного.'''

Пусть неравенство было нарушено, рассмотрим момент, когда оно было нарушено впервые. Пусть это была <tex>i</tex>-ая итерация и в этот момент изменилось значение <tex>d_{uv}</tex> и выполнилось <tex>\rho(u,v) > d_{uv}</tex>. Так как <tex>d_{uv}</tex> изменилось, то <tex>d_{uv} = d_{ui} + d_{iv} \ge</tex> (так как ранее <tex>\forall u, v \in V: \rho(u,v) \le d_{uv}</tex>) <tex>\ge \rho(u, i) + \rho(i, v) \ge</tex> (по неравенству треугольника) <tex>\ge \rho(u, v)</tex>.
Итак <tex>d_{uv} \ge \rho(u,v)</tex> {{---}} противоречие.
}}

# Инициализация
<tex dpi = "105"> d = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105"> d_{uv} = min(d_{uv}, d_{ui} + d_{iv}) </tex>

Данная реализация работает за время <tex> \Theta(n^3) </tex>, но требует уже <tex> \Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> весьма мала.

=== Пример работы ===
{|style="text-align:center;"
| <tex>i = 0</tex> || <tex>i = 1</tex> || <tex>i = 2</tex> || <tex>i = 3 </tex> || <tex>i = 4</tex>
|-
| [[Файл:Floyd_step0.png]] || [[Файл:Floyd_step1.png]] || [[Файл:Floyd_step2.png]] || [[Файл:Floyd_step3.png]] || [[Файл:Floyd_step4.png]]
|-
| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{5} & \bf{2} \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 5 & 2 \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{3} & 2 \\
\infty & \times & \bf{2} & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|}

== Вывод кратчайшего пути ==
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.

=== Модифицированный алгоритм ===

# Инициализация
d = w
t[u][v] = v если есть ребро uv
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
if (d[u][i] + d[i][v]) < d[u][v]:
d[u][v] = d[u][i] + d[i][v]
next[u][v] = next[u][i]

# Вывод кратчайшего пути
def get_shortest_path(u, v):
if d[u][v] == inf:
raise NoPath # Из u в v пути нет
c = u
while c != v:
print c
c = next[c][v]
print v

[[Файл:Floyd_path.png]]

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Алгоритм Флойда

2011-11-07T18:37:19Z

Chuprikov Pavel: /* Код (окончательный) */

'''Алгоритм Флойда (алгоритм Флойда–Уоршелла)''' {{---}} алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Этот алгоритм работает в течение времени <tex> \Theta(n^3) </tex> и использует <tex> \Theta(n^2) </tex> памяти. Разработан в 1962 году.

== Алгоритм ==
[[Файл:Floyd.png|right|thumb|Текущий (синий) путь и потенциально более короткий (красный)]]

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

Дан взвешенный ориентированный граф <tex> G(V, E) </tex>; <tex>\omega_{uv} =
\begin{cases}
\text{weight of }uv ,& \text{if } uv \in E \\
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>, в котором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>. Требуется найти матрицу кратчайших расстояний <tex> d </tex>, в которой элемент <tex> d_{ij} </tex> либо равен длине кратчайшего пути из <tex> i </tex> в <tex> j </tex>, либо равен <tex> +\infty </tex>, если вершина <tex> j </tex> не достижима из <tex> i </tex>.

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

Обозначим длину кратчайшего пути между вершинами <tex> u </tex> и <tex> v </tex>, содержащего, помимо <tex>u</tex> и <tex>v</tex>, только вершины из множества <tex> \{ 1 .. i \} </tex> как <tex>d_{uv}^{(i)}</tex>, <tex>d_{uv}^{(0)} = \omega_{uv}</tex>.

На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер {{---}} <tex> i </tex>) и для всех пар вершин <tex>u</tex> и <tex>v</tex> вычислять <tex> d_{uv}^{(i)} = min(d_{uv}^{(i-1)}, d_{ui}^{(i-1)} + d_{iv}^{(i-1)}) </tex>. То есть, если кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex>, проходит через вершину <tex>i</tex>, то кратчайшим путем из <tex> u </tex> в <tex> v </tex> является кратчайший путь из <tex> u </tex> в <tex> i </tex>, объединенный с кратчайшим путем из <tex> i </tex> в <tex> v </tex>. В противном случае, когда этот путь не содержит вершины <tex> i </tex>, кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex> является кратчайшим путем из <tex>u</tex> в <tex>v</tex>, содержащим только вершины из множества <tex> \{ 1 .. i-1 \} </tex>.

=== Код (в первом приближении) ===
# Инициализация
<tex dpi = "105"> d^{(0)} = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105" > d^{(i)}_{uv} = min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>

В итоге получаем, что матрица <tex> d^{(n)} </tex> и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества <tex> \{ 1..n \} </tex>, что есть попросту все вершины графа. Такая реализация работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^3) </tex> памяти.

=== Код (окончательный) ===
Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) == d_{uv}^{(i)} </tex>, то тогда будет выполняться и <tex> \rho(u, v) == d_{uv} </tex>.

{{Утверждение
|statement=
В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>.
|proof=

После инициализации все неравенства, очевидно, выполняются. Далее, массив <tex> d </tex> может измениться только в строчке 5.

'''Докажем второе неравенство индукцией по итерациям алгоритма.'''

Пусть также <tex>d'_{uv}</tex> - значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации.
<tex> d_{uv} \le d_{uv}^{(i)} </tex>.

Рассмотрим два случая:
* Значение <tex> d_{uv}^{(i)} </tex> стало меньше, чем <tex> d_{uv}^{(i - 1)} </tex>. Тогда <tex> d_{uv}^{(i)} = d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному предположению) <tex> \ge d'_{ui} + d'_{iv} \ge</tex> (в силу выполнения 7-ой строчки алгоритма на <tex>i</tex>-ой итерации и невозрастания элементов массива <tex> d </tex>) <tex>\ge d_{uv}</tex>.
* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.

'''Докажем первое неравнство от противного.'''

Пусть неравенство было нарушено. рассмотрим момент, когда оно было нарушено впервые. Пусть это была <tex>i</tex>-ая итерация и в этот момент изменилось значение <tex>d_{uv}</tex> и выполнилось <tex>\rho(u,v) > d_{uv}</tex>. Так как <tex>d_{uv}</tex> изменилось, то <tex>d_{uv} = d_{ui} + d_{iv} \ge</tex> (так как ранее <tex>\forall u, v \in V: \rho(u,v) \le d_{uv}</tex>) <tex>\ge \rho(u, i) + \rho(i, v) \ge</tex> (по неравенству треугольника) <tex>\ge \rho(u, v)</tex>.
Итак <tex>d_{uv} \ge \rho(u,v)</tex> {{---}} противоречие.
}}

# Инициализация
<tex dpi = "105"> d = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105"> d_{uv} = min(d_{uv}, d_{ui} + d_{iv}) </tex>

Данная реализация работает за время <tex> \Theta(n^3) </tex>, но требует уже <tex> \Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> весьма мала.

=== Пример работы ===
{|style="text-align:center;"
| <tex>i = 0</tex> || <tex>i = 1</tex> || <tex>i = 2</tex> || <tex>i = 3 </tex> || <tex>i = 4</tex>
|-
| [[Файл:Floyd_step0.png]] || [[Файл:Floyd_step1.png]] || [[Файл:Floyd_step2.png]] || [[Файл:Floyd_step3.png]] || [[Файл:Floyd_step4.png]]
|-
| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{5} & \bf{2} \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 5 & 2 \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{3} & 2 \\
\infty & \times & \bf{2} & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|}

== Вывод кратчайшего пути ==
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.

=== Модифицированный алгоритм ===

# Инициализация
d = w
t[u][v] = v если есть ребро uv
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
if (d[u][i] + d[i][v]) < d[u][v]:
d[u][v] = d[u][i] + d[i][v]
next[u][v] = next[u][i]

# Вывод кратчайшего пути
def get_shortest_path(u, v):
if d[u][v] == inf:
raise NoPath # Из u в v пути нет
c = u
while c != v:
print c
c = next[c][v]
print v

[[Файл:Floyd_path.png]]

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Алгоритм Флойда

2011-11-07T18:12:50Z

Chuprikov Pavel: /* Код (окончательный) */

'''Алгоритм Флойда (алгоритм Флойда–Уоршелла)''' {{---}} алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Этот алгоритм работает в течение времени <tex> \Theta(n^3) </tex> и использует <tex> \Theta(n^2) </tex> памяти. Разработан в 1962 году.

== Алгоритм ==
[[Файл:Floyd.png|right|thumb|Текущий (синий) путь и потенциально более короткий (красный)]]

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

Дан взвешенный ориентированный граф <tex> G(V, E) </tex>; <tex>\omega_{uv} =
\begin{cases}
\text{weight of }uv ,& \text{if } uv \in E \\
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>, в котором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>. Требуется найти матрицу кратчайших расстояний <tex> d </tex>, в которой элемент <tex> d_{ij} </tex> либо равен длине кратчайшего пути из <tex> i </tex> в <tex> j </tex>, либо равен <tex> +\infty </tex>, если вершина <tex> j </tex> не достижима из <tex> i </tex>.

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

Обозначим длину кратчайшего пути между вершинами <tex> u </tex> и <tex> v </tex>, содержащего, помимо <tex>u</tex> и <tex>v</tex>, только вершины из множества <tex> \{ 1 .. i \} </tex> как <tex>d_{uv}^{(i)}</tex>, <tex>d_{uv}^{(0)} = \omega_{uv}</tex>.

На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер {{---}} <tex> i </tex>) и для всех пар вершин <tex>u</tex> и <tex>v</tex> вычислять <tex> d_{uv}^{(i)} = min(d_{uv}^{(i-1)}, d_{ui}^{(i-1)} + d_{iv}^{(i-1)}) </tex>. То есть, если кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex>, проходит через вершину <tex>i</tex>, то кратчайшим путем из <tex> u </tex> в <tex> v </tex> является кратчайший путь из <tex> u </tex> в <tex> i </tex>, объединенный с кратчайшим путем из <tex> i </tex> в <tex> v </tex>. В противном случае, когда этот путь не содержит вершины <tex> i </tex>, кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex> является кратчайшим путем из <tex>u</tex> в <tex>v</tex>, содержащим только вершины из множества <tex> \{ 1 .. i-1 \} </tex>.

=== Код (в первом приближении) ===
# Инициализация
<tex dpi = "105"> d^{(0)} = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105" > d^{(i)}_{uv} = min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>

В итоге получаем, что матрица <tex> d^{(n)} </tex> и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества <tex> \{ 1..n \} </tex>, что есть попросту все вершины графа. Такая реализация работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^3) </tex> памяти.

=== Код (окончательный) ===
Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) == d_{uv}^{(i)} </tex>, то тогда будет выполняться и <tex> \rho(u, v) == d_{uv} </tex>.

{{Утверждение
|statement=
В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>.
|proof=

После инициализации все неравенства, очевидно, выполняются. Далее, массив <tex> d </tex> может измениться только в строчке 5. Докажем оба неравенства индукцией по итерациям алгоритма. Пусть также <tex>d'_{uv}</tex> - значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации.

# <tex> \rho(u, v) \le d_{uv} </tex>. Рассмотрим два случая:
#* Значение <tex> d_{uv} </tex> изменилось. Тогда <tex> d_{uv} = d_{ui} + d_{iv} \ge \rho(u, i) + \rho(i, v) \ge \rho(u, v) </tex> (по индукционному предположению и неравенству треугольника для <tex> \rho </tex>).
#* Значение <tex> d_{uv} </tex> не изменилось. Тогда неравенство выполняется автоматически по индукционному предположению.
# <tex> d_{uv} \le d_{uv}^{(i)} </tex>. Аналогично рассмотрим два случая:
#* Значение <tex> d_{uv}^{(i)} </tex> стало меньше, чем <tex> d_{uv}^{(i - 1)} </tex>. Тогда <tex> d_{uv}^{(i)} = d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному предположению) <tex> \ge d'_{ui} + d'_{iv} \ge</tex> (в силу выполнения 7-ой строчки алгоритма на <tex>i</tex>-ой итерации и невозрастания элементов массива <tex> d </tex>) <tex>\ge d_{uv}</tex>.
#* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.

}}

# Инициализация
<tex dpi = "105"> d = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105"> d_{uv} = min(d_{uv}, d_{ui} + d_{iv}) </tex>

Данная реализация работает за время <tex> \Theta(n^3) </tex>, но требует уже <tex> \Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> весьма мала.

=== Пример работы ===
{|style="text-align:center;"
| <tex>i = 0</tex> || <tex>i = 1</tex> || <tex>i = 2</tex> || <tex>i = 3 </tex> || <tex>i = 4</tex>
|-
| [[Файл:Floyd_step0.png]] || [[Файл:Floyd_step1.png]] || [[Файл:Floyd_step2.png]] || [[Файл:Floyd_step3.png]] || [[Файл:Floyd_step4.png]]
|-
| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{5} & \bf{2} \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 5 & 2 \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{3} & 2 \\
\infty & \times & \bf{2} & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|}

== Вывод кратчайшего пути ==
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.

=== Модифицированный алгоритм ===

# Инициализация
d = w
t[u][v] = v если есть ребро uv
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
if (d[u][i] + d[i][v]) < d[u][v]:
d[u][v] = d[u][i] + d[i][v]
next[u][v] = next[u][i]

# Вывод кратчайшего пути
def get_shortest_path(u, v):
if d[u][v] == inf:
raise NoPath # Из u в v пути нет
c = u
while c != v:
print c
c = next[c][v]
print v

[[Файл:Floyd_path.png]]

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2011-11-03T17:42:25Z

Chuprikov Pavel: /* Псевдокод */

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

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

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

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

В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \hat{\omega} </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> \hat{\omega} </tex>.

{{Лемма
|statement=
Пусть <tex>P,\; Q : a \rightsquigarrow b\;</tex> и <tex>w(P) < w(Q).</tex> Тогда <tex>\forall \varphi: \; w_\varphi(P) < w_\varphi(Q)</tex>
|proof=
:<tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>

:<tex>w_\varphi(P) = w_\varphi(u_0u_1) + w_\varphi(u_1u_2) + ... + w_\varphi(u_{k-1}u_k) = \varphi(u_0) + w(u_0u_1) - \varphi(u_1) + ... + \varphi(u_{k-1}) + w(u_{k-1}u_k) - \varphi(u_k) = \varphi(u_0) + w(P) - \varphi(u_k)</tex>

:<tex>w(P) < w(Q)</tex>

:<tex>w_\varphi(P) = \varphi(a) + w(P) - \varphi(b)</tex>

:<tex>w_\varphi(Q) = \varphi(a) + w(Q) - \varphi(b)</tex>

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

=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; w_\varphi(uv) \ge 0 </tex>
|proof=
<tex>\Leftarrow </tex>: <tex>C</tex> - цикл в графе <tex>G</tex>

:<tex>w(C) = w_\varphi(C) - \sum\limits_{uv \in C} (\varphi(u) - \varphi(v))= w_\varphi(C) \ge 0</tex>

<tex>\Rightarrow </tex>: Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.

:''Обозначение'' : <tex>\delta(i,\;j)</tex> - минимальное расстояние между вершинами <tex>i,\; j</tex> графа <tex>G</tex>.

:<tex>\phi(u) = \delta(s,\;u)</tex>

:<tex>w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>.

:<tex>\delta(s,\;u) + w(uv) = </tex> {какой-то путь <tex>s \rightsquigarrow v</tex>}.

:<tex>\delta(s,\;v) =</tex> {минимальный путь <tex>s \rightsquigarrow v</tex>}.

:Следовательно, <tex>w_\phi(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>w_\varphi(u,\;v) \leftarrow w(u,\;v) + \varphi(u) - \varphi(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;w_\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> - время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0 фибоначчиевой кучи], то время работы алгоритма Джонсона равно <tex>O(V^2\log V + V E)</tex>.

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

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

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

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

2011-11-03T17:42:02Z

Chuprikov Pavel: /* Псевдокод */

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

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

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

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

В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \hat{\omega} </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> \hat{\omega} </tex>.

{{Лемма
|statement=
Пусть <tex>P,\; Q : a \rightsquigarrow b\;</tex> и <tex>w(P) < w(Q).</tex> Тогда <tex>\forall \varphi: \; w_\varphi(P) < w_\varphi(Q)</tex>
|proof=
:<tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>

:<tex>w_\varphi(P) = w_\varphi(u_0u_1) + w_\varphi(u_1u_2) + ... + w_\varphi(u_{k-1}u_k) = \varphi(u_0) + w(u_0u_1) - \varphi(u_1) + ... + \varphi(u_{k-1}) + w(u_{k-1}u_k) - \varphi(u_k) = \varphi(u_0) + w(P) - \varphi(u_k)</tex>

:<tex>w(P) < w(Q)</tex>

:<tex>w_\varphi(P) = \varphi(a) + w(P) - \varphi(b)</tex>

:<tex>w_\varphi(Q) = \varphi(a) + w(Q) - \varphi(b)</tex>

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

=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; w_\varphi(uv) \ge 0 </tex>
|proof=
<tex>\Leftarrow </tex>: <tex>C</tex> - цикл в графе <tex>G</tex>

:<tex>w(C) = w_\varphi(C) - \sum\limits_{uv \in C} (\varphi(u) - \varphi(v))= w_\varphi(C) \ge 0</tex>

<tex>\Rightarrow </tex>: Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.

:''Обозначение'' : <tex>\delta(i,\;j)</tex> - минимальное расстояние между вершинами <tex>i,\; j</tex> графа <tex>G</tex>.

:<tex>\phi(u) = \delta(s,\;u)</tex>

:<tex>w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>.

:<tex>\delta(s,\;u) + w(uv) = </tex> {какой-то путь <tex>s \rightsquigarrow v</tex>}.

:<tex>\delta(s,\;v) =</tex> {минимальный путь <tex>s \rightsquigarrow v</tex>}.

:Следовательно, <tex>w_\phi(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>w_\varphi(u,\;v) \leftarrow w(u,\;v) + \varphi(u) - \varphi(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;w_\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''' d

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

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

== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> - время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0 фибоначчиевой кучи], то время работы алгоритма Джонсона равно <tex>O(V^2\log V + V E)</tex>.

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

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

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

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

2011-11-03T17:36:11Z

Chuprikov Pavel: /* Описание */

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

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

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

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

В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \hat{\omega} </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> \hat{\omega} </tex>.

{{Лемма
|statement=
Пусть <tex>P,\; Q : a \rightsquigarrow b\;</tex> и <tex>w(P) < w(Q).</tex> Тогда <tex>\forall \varphi: \; w_\varphi(P) < w_\varphi(Q)</tex>
|proof=
:<tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>

:<tex>w_\varphi(P) = w_\varphi(u_0u_1) + w_\varphi(u_1u_2) + ... + w_\varphi(u_{k-1}u_k) = \varphi(u_0) + w(u_0u_1) - \varphi(u_1) + ... + \varphi(u_{k-1}) + w(u_{k-1}u_k) - \varphi(u_k) = \varphi(u_0) + w(P) - \varphi(u_k)</tex>

:<tex>w(P) < w(Q)</tex>

:<tex>w_\varphi(P) = \varphi(a) + w(P) - \varphi(b)</tex>

:<tex>w_\varphi(Q) = \varphi(a) + w(Q) - \varphi(b)</tex>

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

=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; w_\varphi(uv) \ge 0 </tex>
|proof=
<tex>\Leftarrow </tex>: <tex>C</tex> - цикл в графе <tex>G</tex>

:<tex>w(C) = w_\varphi(C) - \sum\limits_{uv \in C} (\varphi(u) - \varphi(v))= w_\varphi(C) \ge 0</tex>

<tex>\Rightarrow </tex>: Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.

:''Обозначение'' : <tex>\delta(i,\;j)</tex> - минимальное расстояние между вершинами <tex>i,\; j</tex> графа <tex>G</tex>.

:<tex>\phi(u) = \delta(s,\;u)</tex>

:<tex>w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>.

:<tex>\delta(s,\;u) + w(uv) = </tex> {какой-то путь <tex>s \rightsquigarrow v</tex>}.

:<tex>\delta(s,\;v) =</tex> {минимальный путь <tex>s \rightsquigarrow v</tex>}.

:Следовательно, <tex>w_\phi(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): 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>w_\varphi(u,\;v) \leftarrow w(u,\;v) + \varphi(u) - \varphi(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;w_\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''' D

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

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

== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> - время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0 фибоначчиевой кучи], то время работы алгоритма Джонсона равно <tex>O(V^2\log V + V E)</tex>.

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

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

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

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

2011-11-03T17:32:01Z

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

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

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

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

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

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

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

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

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

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

{{Лемма
|statement=
Пусть <tex>P,\; Q : a \rightsquigarrow b\;</tex> и <tex>w(P) < w(Q).</tex> Тогда <tex>\forall \varphi: \; w_\varphi(P) < w_\varphi(Q)</tex>
|proof=
:<tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>

:<tex>w_\varphi(P) = w_\varphi(u_0u_1) + w_\varphi(u_1u_2) + ... + w_\varphi(u_{k-1}u_k) = \varphi(u_0) + w(u_0u_1) - \varphi(u_1) + ... + \varphi(u_{k-1}) + w(u_{k-1}u_k) - \varphi(u_k) = \varphi(u_0) + w(P) - \varphi(u_k)</tex>

:<tex>w(P) < w(Q)</tex>

:<tex>w_\varphi(P) = \varphi(a) + w(P) - \varphi(b)</tex>

:<tex>w_\varphi(Q) = \varphi(a) + w(Q) - \varphi(b)</tex>

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

=== Теорема о существовании потенциальной функции ===
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; w_\varphi(uv) \ge 0 </tex>
|proof=
<tex>\Leftarrow </tex>: <tex>C</tex> - цикл в графе <tex>G</tex>

:<tex>w(C) = w_\varphi(C) - \sum\limits_{uv \in C} (\varphi(u) - \varphi(v))= w_\varphi(C) \ge 0</tex>

<tex>\Rightarrow </tex>: Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.

:''Обозначение'' : <tex>\delta(i,\;j)</tex> - минимальное расстояние между вершинами <tex>i,\; j</tex> графа <tex>G</tex>.

:<tex>\phi(u) = \delta(s,\;u)</tex>

:<tex>w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>.

:<tex>\delta(s,\;u) + w(uv) = </tex> {какой-то путь <tex>s \rightsquigarrow v</tex>}.

:<tex>\delta(s,\;v) =</tex> {минимальный путь <tex>s \rightsquigarrow v</tex>}.

:Следовательно, <tex>w_\phi(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): 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>w_\varphi(u,\;v) \leftarrow w(u,\;v) + \varphi(u) - \varphi(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;w_\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''' D

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

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

== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> - время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0 фибоначчиевой кучи], то время работы алгоритма Джонсона равно <tex>O(V^2\log V + V E)</tex>.

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

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

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

Алгоритм Флойда

2011-11-03T17:02:15Z

Chuprikov Pavel: /* Код (окончательный) */

'''Алгоритм Флойда (алгоритм Флойда–Уоршелла)''' {{---}} алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Этот алгоритм работает в течение времени <tex> \Theta(n^3) </tex> и использует <tex> \Theta(n^2) </tex> памяти. Разработан в 1962 году.

== Алгоритм ==
[[Файл:Floyd.png|right|thumb|Текущий (синий) путь и потенциально более короткий (красный)]]

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

Дан взвешенный ориентированный граф <tex> G(V, E) </tex>; <tex>\omega_{uv} =
\begin{cases}
\text{weight of }uv ,& \text{if } uv \in E \\
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>, в котором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>. Требуется найти матрицу кратчайших расстояний <tex> d </tex>, в которой элемент <tex> d_{ij} </tex> либо равен длине кратчайшего пути из <tex> i </tex> в <tex> j </tex>, либо равен <tex> +\infty </tex>, если вершина <tex> j </tex> не достижима из <tex> i </tex>.

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

Обозначим длину кратчайшего пути между вершинами <tex> u </tex> и <tex> v </tex>, содержащего, помимо <tex>u</tex> и <tex>v</tex>, только вершины из множества <tex> \{ 1 .. i \} </tex> как <tex>d_{uv}^{(i)}</tex>, <tex>d_{uv}^{(0)} = \omega_{uv}</tex>.

На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер {{---}} <tex> i </tex>) и для всех пар вершин <tex>u</tex> и <tex>v</tex> вычислять <tex> d_{uv}^{(i)} = min(d_{uv}^{(i-1)}, d_{ui}^{(i-1)} + d_{iv}^{(i-1)}) </tex>. То есть, если кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex>, проходит через вершину <tex>i</tex>, то кратчайшим путем из <tex> u </tex> в <tex> v </tex> является кратчайший путь из <tex> u </tex> в <tex> i </tex>, объединенный с кратчайшим путем из <tex> i </tex> в <tex> v </tex>. В противном случае, когда этот путь не содержит вершины <tex> i </tex>, кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex> является кратчайшим путем из <tex>u</tex> в <tex>v</tex>, содержащим только вершины из множества <tex> \{ 1 .. i-1 \} </tex>.

=== Код (в первом приближении) ===
# Инициализация
<tex dpi = "105"> d^{(0)} = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105" > d^{(i)}_{uv} = min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>

В итоге получаем, что матрица <tex> d^{(n)} </tex> и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества <tex> \{ 1..n \} </tex>, что есть попросту все вершины графа. Такая реализация работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^3) </tex> памяти.

=== Код (окончательный) ===
Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) == d_{uv}^{(i)} </tex>, то тогда будет выполняться и <tex> \rho(u, v) == d_{uv} </tex>.

{{Утверждение
|statement=
В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>.
|proof=

После инициализации все неравенства, очевидно, выполняются. Далее, массив <tex> d </tex> может измениться только в строчке 5. Докажем оба неравенства по индукции по итерациям алгоритма:

# <tex> \rho(u, v) \le d_{uv} </tex>. Рассмотрим два случая:
#* Значение <tex> d_{uv} </tex> изменилось. Тогда <tex> d_{uv} = d_{ui} + d_{iv} \ge \rho(u, i) + \rho(i, v) \ge \rho(u, v) </tex> (по индукционному предположению и неравенству треугольника для <tex> \rho </tex>).
#* Значение <tex> d_{uv} </tex> не изменилось. Тогда неравенство выполняется автоматически по индукционному предположению.
# <tex> d_{uv} \le d_{uv}^{(i)} </tex>. Аналогично рассмотрим два случая:
#* Значение <tex> d_{uv}^{(i)} </tex> изменилось. Тогда <tex> d_{uv}^{(i)} \ge d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge d_{ui}^{(i)} + d_{iv}^{(i)} \ge d_{ui} + d_{uv} \ge d_{uv} </tex>, по индукционному предположению и тому факту, что <tex> d_{uv}^{(i)} </tex> не возрастает с ростом <tex> i </tex>.
#* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.

}}

# Инициализация
<tex dpi = "105"> d = w </tex>
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
<tex dpi = "105"> d_{uv} = min(d_{uv}, d_{ui} + d_{iv}) </tex>

Данная реализация работает за время <tex> \Theta(n^3) </tex>, но требует уже <tex> \Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> весьма мала.

=== Пример работы ===
{|style="text-align:center;"
| <tex>i = 0</tex> || <tex>i = 1</tex> || <tex>i = 2</tex> || <tex>i = 3 </tex> || <tex>i = 4</tex>
|-
| [[Файл:Floyd_step0.png]] || [[Файл:Floyd_step1.png]] || [[Файл:Floyd_step2.png]] || [[Файл:Floyd_step3.png]] || [[Файл:Floyd_step4.png]]
|-
| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 6 & \infty \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{5} & \bf{2} \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & 5 & 2 \\
\infty & \times & 4 & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|| <tex>\begin{pmatrix}
\times & 1 & \bf{3} & 2 \\
\infty & \times & \bf{2} & 1 \\
\infty & \infty & \times & \infty \\
\infty & \infty & 1 & \times \\
\end{pmatrix}</tex>
|}

== Вывод кратчайшего пути ==
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.

=== Модифицированный алгоритм ===

# Инициализация
d = w
t[u][v] = v если есть ребро uv
# Основная часть
for i in {1..n}:
for u in {1..n}:
for v in {1..n}:
if (d[u][i] + d[i][v]) < d[u][v]:
d[u][v] = d[u][i] + d[i][v]
next[u][v] = next[u][i]

# Вывод кратчайшего пути
def get_shortest_path(u, v):
if d[u][v] == inf:
raise NoPath # Из u в v пути нет
c = u
while c != v:
print c
c = next[c][v]
print v

[[Файл:Floyd_path.png]]

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Алгоритм Форда-Беллмана

2011-11-01T06:47:00Z

Chuprikov Pavel: /* Корректность алгоритма Форда-Беллмана */

==Алгоритм==
:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин. 
:В случае когда в графе <tex> G </tex> содержатся отрицательные циклы достижимые из <tex> s </tex> алгоритм сообщает, что кратчайших путей не существует.

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

'''Bellman_Ford(G, s)'''
'''for''' для каждой <tex>v \in V[G]</tex>
<tex> d[v] \leftarrow \mathcal {1} </tex>
<tex>d[s] \leftarrow 0 </tex>
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V[G] \mid - 1 </tex>
'''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' <tex>d[v] \leftarrow d[u] + \omega(u, v)</tex>
'''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' '''return''' <tex> \mathit false</tex>
'''return''' <tex> \mathit true </tex>

==Корректность алгоритма Форда-Беллмана==
:В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>. 
:<tex>d[v]</tex> - оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>. 
:<tex>\delta(s, v)</tex> - фактический вес кратчайшего пути из <tex>s</tex> в вершину <tex>v</tex>.

{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Тогда после завершения <tex> \mid V[G] \mid - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s</tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
|proof=:Рассмотрим произвольную вершину <tex>v</tex>, достижимую из <tex>s</tex>.

:Пусть <tex>p = \langle v_0,..., v_{k} \rangle </tex>, где <tex>v_0 = s</tex>, <tex>v_{k} = v</tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. 
:Путь <tex> p </tex> содержит не более <tex> \mid V[G] \mid - 1 </tex> ребер. Поэтому <tex>k \le \mid V[G] \mid - 1</tex>.

: Докажем следующее утверждение:
:: После <tex>n : (n \le k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
: Воспользуемся индукцией по <tex>n</tex>:
: '''База индукции.''' Перед первой итерацией утверждение очевидно выполнено: <tex>d[v_0] = d[s] = \delta(s, s) = 0</tex>
: '''Индукционный переход.''' Пусть после <tex>n : (n < k)</tex> итераций, верно что <tex>d[v_n] = \delta(s, v_n)</tex>. Так как <tex>(v_n, v_{n + 1})</tex> принадлежит кратчайшему пути от <tex>s</tex> до <tex>v</tex>, то <tex>\delta(s, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n + 1})</tex>. Во время <tex>l + 1</tex> итерации релаксируется ребро <tex>(v_n,v_{n+1})</tex>, следовательно по завершению итерации будет выполнено
::<tex>d[v_{n+1}] \le d[v_n] + \omega(v_n, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n+1}) = \delta(s, v_{n+1})</tex>.
: Ясно, что <tex>d[v_{n+1}] \ge \delta(s, v_{n+1}) </tex>, поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>.
: Индукционный переход доказан.

: Итак, выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v)</tex>. 
}}

{{Теорема
|statement=Пусть <tex>G = (V, E) </tex> - взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V[G] \ d[v] = \delta (s, v)</tex>. Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>
|proof=:Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>. 
:Тогда если вершина <tex> v </tex> достижима из <tex> s </tex>, то по лемме <tex> d[v] = \delta (s, v)</tex>. 
:Если вершина <tex> v </tex> не достижима из <tex> s </tex>, то <tex> d[v] = \delta (s, v) = \mathcal {1}</tex> из несуществования пути.

:Теперь докажем, что алгоритм вернет значение <tex> true </tex>. 
:После выполнения алгоритма верно, что для всех <tex> (u, v) \in E[G], \ d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </tex>.

:Пусть граф <tex> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>. 
:Тогда <tex>\sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </tex>. 
:Предположим, что алгоритм возвращает <tex> true </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </tex>. 
:Просуммируем эти неравенства по всему циклу: <tex>\sum\limits_{i=1}^{k} {d[v_{i}]} \leqslant \sum\limits_{i=1}^{k} {d[v_{i-1}]} + \sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} </tex>. 
:Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum \limits_{i=1}^{k} {d[v_{i - 1}]} </tex>.

:Получили, что <tex> \sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \ge 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.
}}

==Сложность==
:Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени. Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.

== Источники ==
:Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.
:[http://e-maxx.ru/algo/export_ford_bellman Алгоритм Форда-Беллмана]

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

Алгоритм Форда-Беллмана

2011-11-01T04:35:09Z

Chuprikov Pavel: /* Корректность алгоритма Форда-Беллмана */

==Алгоритм==
:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин. 
:В случае когда в графе <tex> G </tex> содержатся отрицательные циклы достижимые из <tex> s </tex> алгоритм сообщает, что кратчайших путей не существует.

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

'''Bellman_Ford(G, s)'''
'''for''' для каждой <tex>v \in V[G]</tex>
<tex> d[v] \leftarrow \mathcal {1} </tex>
<tex>d[s] \leftarrow 0 </tex>
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V[G] \mid - 1 </tex>
'''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' <tex>d[v] \leftarrow d[u] + \omega(u, v)</tex>
'''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' '''return''' <tex> \mathit false</tex>
'''return''' <tex> \mathit true </tex>

==Корректность алгоритма Форда-Беллмана==
:В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>. 
:<tex>d[v]</tex> - оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>. 
:<tex>\delta(s, v)</tex> - фактический вес кратчайшего пути из <tex>s</tex> в вершину <tex>v</tex>.

{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Тогда после завершения <tex> \mid V[G] \mid - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s</tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
|proof=:Рассмотрим произвольную вершину <tex>v</tex>, достижимую из <tex>s</tex>.

:Пусть <tex>p = \langle v_0,..., v_{k} \rangle </tex>, где <tex>v_0 = s</tex>, <tex>v_{k} = v</tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. 
:Путь <tex> p </tex> содержит не более <tex> \mid V[G] \mid - 1 </tex> ребер. Поэтому <tex>k \le \mid V[G] \mid - 1</tex>.

: Докажем следующее утверждение:
:: После <tex>n : (n \le k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
: Воспользуемся индукцией по <tex>n</tex>:
: '''База индукции.''' Перед первой итерацией утверждение очевидно выполнено: <tex>d[v_0] = d[s] = \delta(s, s) = 0</tex>
: '''Индукционный переход.''' Пусть после <tex>n : (n < k)</tex> итераций, верно что <tex>d[v_n] = \delta(s, v_n)</tex>. Так как <tex>(v_n, v_{n + 1})</tex> принадлежит кратчайшему пути от <tex>s</tex> до <tex>v</tex>, то <tex>\delta(s, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n + 1})</tex>. Во время <tex>l + 1</tex> итерации релаксируется ребро <tex>(v_n,v_{n+1})</tex>, следовательно по завершению итерации будет выполнено
::<tex>d[v_{n+1}] \le d[v_n] + \omega(v_n, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n+1}) = \delta(s, v_{n+1})</tex>.
: Ясно, что <tex>d[v_{n+1}] \ge \delta(s, v_{n+1}) </tex>, поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>.
: Индукционный переход доказан.

: Итак, выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>. 
}}

{{Теорема
|statement=Пусть <tex>G = (V, E) </tex> - взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V[G] \ d[v] = \delta (s, v)</tex>. Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>
|proof=:Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>. 
:Тогда если вершина <tex> v </tex> достижима из <tex> s </tex>, то по лемме <tex> d[v] = \delta (s, v)</tex>. 
:Если вершина <tex> v </tex> не достижима из <tex> s </tex>, то <tex> d[v] = \delta (s, v) = \mathcal {1}</tex> из несуществования пути.

:Теперь докажем, что алгоритм вернет значение <tex> true </tex>. 
:После выполнения алгоритма верно, что для всех <tex> (u, v) \in E[G], \ d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </tex>.

:Пусть граф <tex> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>. 
:Тогда <tex>\sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </tex>. 
:Предположим, что алгоритм возвращает <tex> true </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </tex>. 
:Просуммируем эти неравенства по всему циклу: <tex>\sum\limits_{i=1}^{k} {d[v_{i}]} \leqslant \sum\limits_{i=1}^{k} {d[v_{i-1}]} + \sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} </tex>. 
:Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum \limits_{i=1}^{k} {d[v_{i - 1}]} </tex>.

:Получили, что <tex> \sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \ge 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.
}}

==Сложность==
:Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V[G] \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени. Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.

== Источники ==
:Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.
:[http://e-maxx.ru/algo/export_ford_bellman Алгоритм Форда-Беллмана]

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

Обход в ширину

2011-11-01T03:29:34Z

Chuprikov Pavel: /* Реализация */

{{В разработке}}
'''Обход в ширину''' ('''Поиск в ширину, BFS''', '''Breadth-first search''') — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

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

=== Общая идея ===

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

Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

Также можно для каждой вершины <tex> t \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> посещена и <tex> \infty </tex> в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве <tex> X </tex> является избыточной, и его можно не хранить.

=== Анализ времени работы ===

Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

=== Корректность ===

{{Утверждение
|statement=
В алгоритме поиска в ширину очередь всегда содержит сначала некоторое количество вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1(возможно, нулевое).
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.

Переход: пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex>(возможно, 0) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием k + 1, что соответствует нашему инварианту.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит оптимальные расстояния до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых найдено неоптимальное расстояние от <tex> s </tex> ту, длина кратчайшего пути до которой минимальна. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в оптимальном пути до <tex> v </tex> — вершина <tex> w </tex>. Расстояние до вершин <tex> v </tex> и <tex> w </tex> найдено корректно, путь через <tex> w </tex> оптимальный, а через <tex> v </tex> — нет, поэтому <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно найденные расстояния до всех вершин оптимальны.
}}

=== Реализация ===

В приведенном ниже псевдокоде <tex> G = (V, E) </tex> - входной граф, <tex> s </tex> - выделенная вершина, Q - очередь. Множество <tex> X </tex> не хранится, вместо него использются расстояния в дереве обхода в ширину; расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>.

'''BFS'''(<tex>G</tex>, <tex>s</tex>)
1 d[s] <tex> \leftarrow </tex> 0
2 Q <tex> \leftarrow \emptyset </tex>
3 Q.push(s)
4 '''while''' Q <tex> \ne \emptyset </tex>
5 '''do''' u <tex> \leftarrow </tex> Q.pop
6 '''for''' v: uv <tex> \in </tex> E
7 '''do''' '''if''' d[v] = <tex> \infty </tex>
8 '''then''' d[v] <tex> \leftarrow </tex> d[u] + 1
9 Q.push(v)

== Литература ==

*Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

== Ссылки ==

[http://e-maxx.ru/algo/bfs Поиск в ширину на e-maxx.ru]

[http://ru.wikipedia.org/wiki/Поиск_в_ширину Поиск в ширину в Википедии]

[http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

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

Обход в ширину

2011-11-01T03:27:10Z

Chuprikov Pavel: /* Корректность */

{{В разработке}}
'''Обход в ширину''' ('''Поиск в ширину, BFS''', '''Breadth-first search''') — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

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

=== Общая идея ===

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

Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

Также можно для каждой вершины <tex> t \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> посещена и <tex> \infty </tex> в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве <tex> X </tex> является избыточной, и его можно не хранить.

=== Анализ времени работы ===

Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

=== Корректность ===

{{Утверждение
|statement=
В алгоритме поиска в ширину очередь всегда содержит сначала некоторое количество вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1(возможно, нулевое).
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.

Переход: пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex>(возможно, 0) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием k + 1, что соответствует нашему инварианту.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит оптимальные расстояния до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых найдено неоптимальное расстояние от <tex> s </tex> ту, длина кратчайшего пути до которой минимальна. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в оптимальном пути до <tex> v </tex> — вершина <tex> w </tex>. Расстояние до вершин <tex> v </tex> и <tex> w </tex> найдено корректно, путь через <tex> w </tex> оптимальный, а через <tex> v </tex> — нет, поэтому <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно найденные расстояния до всех вершин оптимальны.
}}

=== Реализация ===

В приведенном ниже псевдокоде <tex> G = (V, E) </tex> - входной граф, <tex> s </tex> - выделенная вершина, Q - очередь. Множество <tex> X </tex> не хранится, вместо него использются расстояния в дереве обхода в ширину; расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>.

'''BFS'''(<tex>G</tex>, <tex>s</tex>)
1 d[s] <tex> \leftarrow </tex> 0
2 Q <tex> \leftarrow \varnothing </tex>
3 Q.push(s)
4 '''while''' Q <tex> \ne \varnothing </tex>
5 '''do''' u <tex> \leftarrow </tex> Q.pop
6 '''for''' v: uv <tex> \in </tex> E
7 '''do''' '''if''' d[v] = <tex> \infty </tex>
8 '''then''' d[v] <tex> \leftarrow </tex> d[u] + 1
9 Q.push(v)

== Литература ==

*Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

== Ссылки ==

[http://e-maxx.ru/algo/bfs Поиск в ширину на e-maxx.ru]

[http://ru.wikipedia.org/wiki/Поиск_в_ширину Поиск в ширину в Википедии]

[http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

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

Теорема о существовании простого цикла в случае существования цикла

2011-10-27T18:18:18Z

Chuprikov Pavel:

{{Теорема
|statement=
Если между двумя [[Основные определения теории графов|вершинами неориентированного графа]] существуют два различных рёберно-простых [[Основные определения теории графов|пути]], то в этом графе существует простой цикл.
|proof=
Возьмём два существующих пути между нужными нам вершинами: <tex>V_0E_1V_1E_2V_2 ... E_nV_n</tex>, <tex>v_0e_1v_1e_2v_2 ... e_mv_m</tex>, <tex>V_0 = v_0</tex>, <tex>V_n = v_m</tex>. Удалим из путей одинаковые префиксы и суффиксы, оставив из тех только последние и первые вершины, соответственно. Оставшиеся пути: <tex>V_aE_{a+1} ... E_bV_b</tex>, <tex>v_ae_{a+1} ... e_cv_c</tex>, <tex>V_a = v_a</tex>, <tex>V_b = v_c</tex>, <tex>E_{a+1} \neq e_{a+1}</tex>, <tex>E_b \neq e_c</tex>.

Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <tex>V_0E_1V_1 ... E_kV_k</tex>, <tex>V_0 = V_k</tex>.

* Алгоритм:
1. Для вершины <tex>V_i</tex> найдём момент её последнего вхождения в цикл - <tex>V_j</tex>.
2. Удалим отрезок цикла от <tex>E_{i+1}</tex> до <tex>V_j</tex>, включительно.
Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <tex>V_i</tex> будет содержаться ровно один раз.
Начнём процесс с вершины <tex>V_1</tex> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
}}

[[Файл: prime_c.png|thumb|500px|center|Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла (2, 5)-5-(5, 6)-6-(6, 4)-4-(4, 2)-2]]

== Замечания ==
* Наличие двух различных рёберно-простых путей между какими-либо вершинами графа равносильно наличию цикла в этом графе.
* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для вершинно-простых путей (усиление условия).
* Так как вершинно-простой цикл всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого цикла (ослабление результата).
* Утверждение
''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''

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

== См. также ==
* [[Основные определения теории графов]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]

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

Основные определения теории графов

2011-10-27T18:08:42Z

Chuprikov Pavel: /* Неориентированные графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер. '''Ребром''' (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей. Мультиграф с петлями принято называть '''псевдографом'''.

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>, вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>

Заметим, что '''инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.

{{Определение
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.
}}
Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|Красным выделено кратное ребро (6, 2) Зеленым обозначена петля (6, 6)]]
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф б) Псевдограф]]
|}

Так же для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.

Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.

{{Определение
|definition =
'''Путём'''(маршрутом) в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
}}
{{Определение
|definition =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex> {{---}} множество рёбер. '''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
[[Файл: Неорграф.png|thumb|300px|center|Неориентированный граф ]]
Иное определение:

{{Определение
|definition =
'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.
}}

Две вершины называются '''смежными''' если между ними есть ребро.

'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

{{Определение
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
}}

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

==См. также==
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Литература==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Основные определения теории графов

2011-10-27T18:07:43Z

Chuprikov Pavel: /* Ориентированные графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер. '''Ребром''' (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей. Мультиграф с петлями принято называть '''псевдографом'''.

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>, вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>

Заметим, что '''инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.

{{Определение
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.
}}
Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|Красным выделено кратное ребро (6, 2) Зеленым обозначена петля (6, 6)]]
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф б) Псевдограф]]
|}

Так же для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.

Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.

{{Определение
|definition =
'''Путём'''(маршрутом) в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
}}
{{Определение
|definition =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex> - множество рёбер. '''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
[[Файл: Неорграф.png|thumb|300px|center|Неориентированный граф ]]
Иное определение:

{{Определение
|definition =
'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
}}

Две вершины называются '''смежными''' если между ними есть ребро.

'''Степеню''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

{{Определение
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
}}

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

==См. также==
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Литература==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Основные определения теории графов

2011-10-27T18:05:24Z

Chuprikov Pavel: /* Ориентированные графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер. '''Ребром''' (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей. Мультиграф с петлями принято называть '''псевдографом'''.

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>, вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>

Заметим, что '''инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.

{{Определение
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
}}
Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|Красным выделено кратное ребро (6, 2) Зеленым обозначена петля (6, 6)]]
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф б) Псевдограф]]
|}

Так же для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.

Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.

{{Определение
|definition =
'''Путём'''(маршрутом) в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
}}
{{Определение
|definition =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> - это две последовательности ребер в циклическом пути.
}}

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex> - множество рёбер. '''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
[[Файл: Неорграф.png|thumb|300px|center|Неориентированный граф ]]
Иное определение:

{{Определение
|definition =
'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
}}

Две вершины называются '''смежными''' если между ними есть ребро.

'''Степеню''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

{{Определение
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
}}

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

==См. также==
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Литература==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Основные определения теории графов

2011-10-27T17:59:07Z

Chuprikov Pavel: /* Ориентированные графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер. '''Ребром''' (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей. Мультиграф с петлями принято называть '''псевдографом'''.

Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>, вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>

Заметим, что '''инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.

{{Определение
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
}}
Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|Красным выделено кратное ребро (6, 2) Зеленым обозначена петля (6, 6)]]
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф б) Псевдограф]]
|}

Так же для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.

Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.

{{Определение
|definition =
'''Путём'''(маршрутом) в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>.
}}
{{Определение
|definition =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> - это две последовательности ребер в циклическом пути.
}}

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex> - множество рёбер. '''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
[[Файл: Неорграф.png|thumb|300px|center|Неориентированный граф ]]
Иное определение:

{{Определение
|definition =
'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
}}

Две вершины называются '''смежными''' если между ними есть ребро.

'''Степеню''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

{{Определение
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
}}

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

==См. также==
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Литература==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Основные определения теории графов

2011-10-26T19:11:19Z

Chuprikov Pavel:

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер.
}}

Заметим, что по такому определению любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.

'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества. Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли (см. определение ниже), но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|Красным выделено ребро (6, 2) Зеленым обозначена петля (6, 6)]]
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф б) Псевдограф]]
|}
{{Определение
|definition =
'''Ребром''' ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей. Мультиграф с петлями принято называть '''псевдографом'''.

Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> v </tex> - предок <tex> u </tex>. Также вершины <tex> u </tex> и <tex> v </tex> называют смежными. Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют тривиальным.

Так же для ориентированных графов определяют '''полустепень входа вершины'''.

<tex>deg^-v_i = |\{e~|beg~e = v\}|</tex>. 
<tex>deg^+v_i = |\{e~|end~e = v\}|</tex>. 

Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.

{{Определение
|definition =
'''Путём''' в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i = (v_{i-1}, v_i)</tex>.
}}
{{Определение
|definition =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> - это две последовательности ребер в циклическом пути.
}}

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv ~ vu \{uu~|~u \in V\})</tex> - множество рёбер.
}}
[[Файл: Неорграф.png|thumb|300px|right|Неориентированный граф ]]
Иное определение:

'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.

'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.

Две вершины называются '''смежными''' если между ними есть ребро.

'''Степеню''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.

В определении циклического пути
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

==Замечание==
В разной литературе используются разные термины для определения одного и того же

'''Ребро(edge) - Дуга(arc) - Линия(line)'''

'''Вершина(vertex) - Узел(node) - Точка(point)'''

'''Путь - Маршрут'''

etc..

==См. также==
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Литература==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Основные определения теории графов

2011-10-26T19:01:17Z

Chuprikov Pavel: /* Ориентированные графы */

==Ориентированные графы==

{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер.
}}

Заметим, что по такому определению любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.

'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества. Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли (см. определение ниже), но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').

[[Файл: directed_graph.png|thumb|300px|center|Ориентированный граф Красным выделено ребро (6, 2) Зеленым обозначена петля (6, 6)]]

{{Определение
|definition =
'''Ребром''' ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей. Мультиграф с петлями принято называть '''псевдографом'''.
[[Файл: Multigraph.png|thumb|300px|right|а) Мультиграф б) Псевдограф]]

Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> v </tex> - предок <tex> u </tex>. Также вершины <tex> u </tex> и <tex> v </tex> называют смежными. Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют тривиальным.

Так же для ориентированных графов определяют '''полустепень входа вершины'''.

<tex>deg^-v_i = |\{e~|beg~e = v\}|</tex>. 
<tex>deg^+v_i = |\{e~|end~e = v\}|</tex>. 

Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.

{{Определение
|definition =
'''Путём''' в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i = (v_{i-1}, v_i)</tex>.
}}
{{Определение
|definition =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> - это две последовательности ребер в циклическом пути.
}}

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv ~ vu \{uu~|~u \in V\})</tex> - множество рёбер.
}}
[[Файл: Неорграф.png|thumb|300px|right|Неориентированный граф ]]
Иное определение:

'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.

'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.

Две вершины называются '''смежными''' если между ними есть ребро.

'''Степеню''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.

В определении циклического пути
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

==Замечание==
В разной литературе используются разные термины для определения одного и того же

'''Ребро(edge) - Дуга(arc) - Линия(line)'''

'''Вершина(vertex) - Узел(node) - Точка(point)'''

'''Путь - Маршрут'''

etc..

==См. также==
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Литература==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

Основные определения теории графов

2011-10-26T18:34:19Z

Chuprikov Pavel: /* Ориентированные графы */

==Ориентированные графы==
{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер.
}}
[[Файл: directed_graph.png|thumb|300px|right|Ориентированный граф Красным выделено ребро (6, 2) Зеленым обозначена петля (6, 6)]]

Заметим, что по такому определению любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.

'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества. Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли (см. определение ниже), но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').

{{Определение
|definition =
'''Ребром''' ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
[[Файл: Multigraph.png|thumb|300px|right|а) Мультиграф б) Псевдограф]]

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется петлей. Мультиграф с петлями принято называть '''псевдографом'''.

Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> v </tex> - предок <tex> u </tex>. Также вершины <tex> u </tex> и <tex> v </tex> называют смежными. Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют тривиальным.

Так же для ориентированных графов определяют '''полустепень входа вершины'''.

<tex>deg^-v_i = |\{e~|beg~e = v\}|</tex>. 
<tex>deg^+v_i = |\{e~|end~e = v\}|</tex>. 

Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.

{{Определение
|definition =
'''Путём''' в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i = (v_{i-1}, v_i)</tex>.
}}
{{Определение
|definition =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> - это две последовательности ребер в циклическом пути.
}}

==Неориентированные графы==
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv ~ vu \{uu~|~u \in V\})</tex> - множество рёбер.
}}
[[Файл: Неорграф.png|thumb|300px|right|Неориентированный граф ]]
Иное определение:

'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.

'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.

Две вершины называются '''смежными''' если между ними есть ребро.

'''Степеню''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.

В определении циклического пути
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

==Замечание==
В разной литературе используются разные термины для определения одного и того же

'''Ребро(edge) - Дуга(arc) - Линия(line)'''

'''Вершина(vertex) - Узел(node) - Точка(point)'''

'''Путь - Маршрут'''

etc..

==См. также==
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]

==Литература==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

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

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

2011-10-26T18:06:58Z

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

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

{{Определение
|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 b</tex>.
}}

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

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

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

{{Теорема
|statement=
Слабая связность '''является отношением эквивалентности'''.
|proof=
Аналогично доказательству соответствующей теоремы для неориентированного графа.
}}
[[Файл:Слаб.jpg|frame|слева|Слабосвязный граф. Компоненты слабой связности выделены красным.]]
 
</wikitex>

=== Сильная связность ===
{{Определение
|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> — ориентированный граф. '''Компонентой сильной связности''' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
{{Определение
|definition=
Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}}

[[Файл:Сил.jpg|слева|frame|Сильносвязный граф. Компоненты сильной связности выделены красным.]]
 

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

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

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

2011-10-22T17:37:34Z

Chuprikov Pavel: /* Слабая связность */

== Случай неориентированного графа ==
{{Определение
|definition=
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связными''', если в графе <tex>G</tex> существует путь из <tex>u</tex> в <tex>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 b</tex>.
}}

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

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

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

{{Теорема
|statement=
Слабая связность '''является отношением эквивалентности'''.
|proof=
Аналогично доказательству соответствующей теоремы для неориентированного графа.
}}
</wikitex>

=== Сильная связность ===
{{Определение
|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> — ориентированный граф. '''Компонентой сильной связности''' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
{{Определение
|definition=
Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}}

==Источники==
* [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 ivtb.ru]
* Ф. Харари, "Теория графов", изд."МОСКВА", 2009 год.