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

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

2012-03-04T12:28:07Z

178.178.19.19:

==Определения==
{{Определение
|definition=
'''Простой (вершинно-простой) путь''' {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}
[[Файл:Prostoy put(1).png|thumb|300px|left|Ориентированный граф Красным выделен вершинно-простой путь Зеленым реберно-простой путь]]

{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}

==Теорема о существовании простого пути в случае существования пути==
{{Теорема
|statement=
Если между двумя [[Основные определения теории графов|вершинами графа]] существует [[Основные определения теории графов|путь]], то между ними существует простой путь.
|proof=

=== Доказательство построением ===

Возьмём любой из существующих путей между нужными нам вершинами: <tex>v_0e_1v_1e_2v_2 ... e_nv_n</tex>.

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

=== Альтернативное ===
Выберем из всех путей между данными вершинами путь наименьшей длины.

Предположение:
Пусть он не простой.
Тогда в нём содержатся две одинаковые вершины <tex>v_i = v_j</tex>, <tex>i < j</tex>. Удалим из исходного пути отрезок от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно. Конечная последовательность также будет путём от <tex>v_0</tex> до <tex>v_n</tex> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь {{---}} простой.
}}

== Замечания ==
* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого пути.
* Теорема может быть сформулирована как для [[Основные определения теории графов|ориентированного]], так и для неориентированного графа.

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

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

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

2012-03-04T11:27:27Z

178.178.19.19:

1) :Просматриваем все вершины <tex>v</tex> первой доли графа <tex>u \in V_1</tex>. Что это?

2) Вынести доказательство корректности в теорему. Нормально доказать.

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

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

2012-03-04T11:26:31Z

178.178.19.19:

1) :Просматриваем все вершины <tex>v</tex> первой доли графа <tex>u \in V_1</tex>. Что это?
2) Вынести доказательство корректности в теорему. Нормально доказать.

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

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

2012-03-04T11:02:42Z

178.178.19.19: /* Алгоритм */

==Теорема==
{{Теорема
|statement=
Если из вершины <tex>x</tex> не существует дополняющей цепи относительно паросочетания <tex>M</tex> и паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи, тогда из <tex>x</tex> не существует дополняющей цепи в <tex>M'</tex>.
|proof=
[[Файл:Kuhn2.png|thumb|right|300x300px|Рисунок 1.]]
[[Файл:Kuhn1.png|thumb|right|300x300px|Рисунок 2. Пунктиром обозначен путь между двумя вершинами. Ребро красного цвета лежит в паросочетании, а черного - нет.]]
: Доказательство от противного. 
: Допустим в паросочетание внесли изменения вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex> и из вершины <tex>x</tex> появилась дополняющая цепь.
: Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из <tex>x</tex> существовала и в исходном паросочетании. 
: Пусть <tex>p</tex> {{---}} ближайшая к <tex>x</tex> вершина, которая принадлежит и новой дополняющей цепи и цепи <tex>(y \rightsquigarrow z)</tex>.
: Тогда <tex>MP</tex> - последнее ребро на отрезке <tex>(y \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>NP</tex> - последнее ребро на отрезке <tex>(z \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>QP</tex> - последнее ребро лежащее на отрезке <tex>(x \rightsquigarrow p)</tex> новой дополняющей цепи(см. Рисунок 1). 
: Допустим <tex>MP</tex> принадлежит паросочетанию <tex>M'</tex>, тогда <tex>NP</tex> ему не принадлежит. 
:: (Случай, когда <tex>NP</tex> принадлежит паросочетанию <tex>M'</tex> полностью симметричен.) 
: Поскольку паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex>, в паросочетание <tex>M</tex> входило ребро <tex>NP</tex>, а ребро <tex>MP</tex> нет.
: Кроме того, ребро <tex>QP</tex> не лежит ни в исходном паросочетании <tex>M</tex>, ни в паросочетании <tex>M'</tex>, в противном случае оказалось бы, что вершина <tex>p</tex> инцидентна нескольким ребрам из паросочетания, что противоречит определению паросочетания. 
:Тогда заметим, что цепь <tex>(x \rightsquigarrow z)</tex>, полученная объединением цепей <tex>(x \rightsquigarrow p)</tex> и <tex>(p \rightsquigarrow z)</tex>, по определению будет дополняющей в паросочетании <tex>M</tex>, что приводит к противоречию, поскольку в паросочетании <tex>M</tex> из вершины <tex>x</tex> не существует дополняющей цепи.
}}

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

:Задан двудольный граф <tex>G(V, E)</tex>, где <tex>V_1</tex> и <tex>V_2</tex> {{---}} его левая и правая доли соответственно.
:Просматриваем все вершины <tex>v</tex> первой доли графа <tex>u \in V_1</tex>:
:*Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем;
:*Иначе запускаем поиск увеличивающей цепи, начинающейся с этой вершины.

:Рассмотрим поиск увеличивающей цепи обходом в глубину.
:* Запускаем обход от вершины <tex>v</tex>.
:* Просматриваем все рёбра из этой вершины, пусть текущее ребро — <tex>(v, to)</tex>.
:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то включаем ребро <tex>(v, to)</tex> в паросочетание и прекращаем поиск из вершины <tex>v</tex>.
:* Иначе, если вершина <tex>to</tex> уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то просто перейдем в нашем обходе в вершину <tex>p</tex>.
:** Пробуем найти часть увеличивающей цепи из вершины <tex>p</tex>.
:** Если получилось, то удаляем из паросочетания ребро <tex>(p, to)</tex>, а вместо него добавляем <tex>(v, to)</tex>

: Этот обход, запущенный из вершины <tex>v</tex>, либо найдет увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина уже не сможет стать насыщенной).

: После того, как все вершины <tex>u \in V_1</tex> будут просмотрены, текущее паросочетание будет максимальным.
: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]] и теоремы, описанной выше. 

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

: Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>
: Функция <tex>dfs(v)</tex> {{---}} обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>.
: В массиве <tex>matching</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, matching[i])</tex>.

bool dfs(int v)
{
if (used[v])
return false;

used[v] = true;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (matching[to] == -1 || dfs(matching[to]))
{
matching[to] = v;
return true;
}
}
return false;
}

int main()
{
... чтение графа ...
matching.assign (k, -1);
for (int u = 0; u < n; u++)
{
used.assign(n, false);
dfs(u);
}

for (int i = 0; i < k; i++)
if (matching[i] != -1)
... вывод ...

}

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <tex>n_1</tex> запусков обхода в глубину на всём графе.
:Следовательно, всего этот алгоритм исполняется за время <tex>O(nm)</tex>, где <tex>m</tex> {{---}} количество ребер, что в худшем случае есть <tex>O(n^3)</tex>.

:Более точная оценка:
:В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1m)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2)</tex>, где <tex>n_2</tex> — число вершин второй доли.

==Ссылки==

* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]

==Источники==
:[http://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания] 
: Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]