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

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

2015-01-11T14:30:05Z

Freemahn: /* Время работы */

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex>, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами <tex>-1</tex>). Затем перебирается вершина <tex>v </tex>, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G\langle V, E \rangle</tex> хранится в матрице смежности <tex>g[i][j]</tex> размера n на n

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

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

==Ссылки==

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

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

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

2015-01-11T14:29:31Z

Freemahn: /* Реализация */

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex>, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами <tex>-1</tex>). Затем перебирается вершина <tex>v </tex>, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G\langle V, E \rangle</tex> хранится в матрице смежности <tex>g[i][j]</tex> размера n на n

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:22:17Z

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

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex>, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами <tex>-1</tex>). Затем перебирается вершина <tex>v </tex>, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится в матрице смежности <tex>g[I][j]</tex>

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:19:50Z

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

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами <tex>-1</tex>). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится в матрице смежности <tex>g[I][j]</tex>

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:18:54Z

Freemahn: /* Теорема */

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится в матрице смежности <tex>g[I][j]</tex>

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:18:32Z

Freemahn: /* Теорема */

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится в матрице смежности <tex>g[I][j]</tex>

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:17:36Z

Freemahn: /* Источники */

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится в матрице смежности <tex>g[I][j]</tex>

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:15:20Z

Freemahn: /* Реализация */ исправлено

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится в матрице смежности <tex>g[I][j]</tex>

'''bool''' dfs(v: '''int'''):
'''if''' (used[v])
'''return''' ''false''
used[v] = ''true''
'''for''' to '''in''' g[v]
'''if''' (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' ''true''
'''return''' ''false''

function '''main'''():
fill(matching, -1)
'''for''' v '''in''' V
fill(used, ''false'')
dfs(v)
'''for''' v '''in''' V
'''if''' (matching[v] != -1)
print(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:09:57Z

Freemahn: /* Алгоритм */ поправил на \mathrm и дефис на тире

==Теорема==
{{Теорема
|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\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>

'''bool''' '''dfs'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
'''fill'''(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T14:04:23Z

Freemahn: /* Теорема */

==Теорема==
{{Теорема
|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>matching</tex> хранятся паросочетания <tex> (v, matching[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> matching[v] </tex> = -1). А <tex>used</tex> - обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>matching[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> matching</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> matching</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>

'''bool''' '''dfs'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
'''fill'''(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T13:59:50Z

Freemahn: /* Теорема */ Изменил дефис на тире

==Теорема==
{{Теорема
|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>matching</tex> хранятся паросочетания <tex> (v, matching[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> matching[v] </tex> = -1). А <tex>used</tex> - обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>matching[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> matching</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> matching</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>

'''bool''' '''dfs'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
'''fill'''(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T13:32:05Z

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

==Теорема==
{{Теорема
|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>matching</tex> хранятся паросочетания <tex> (v, matching[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> matching[v] </tex> = -1). А <tex>used</tex> - обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>matching[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> matching</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> matching</tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>

'''bool''' '''dfs'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
'''fill'''(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T13:30:34Z

Freemahn: /* Реализация */

==Теорема==
{{Теорема
|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>matching</tex> хранятся паросочетания <tex> (v, matching[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> matching[v] </tex> = -1). А <tex>used</tex> - обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>mt[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (список <tex> mt</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> mt </tex>.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше. 

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

* Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>

'''bool''' '''dfs'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
'''fill'''(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T13:29:13Z

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

==Теорема==
{{Теорема
|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>matching</tex> хранятся паросочетания <tex> (v, matching[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> matching[v] </tex> = -1). А <tex>used</tex> - обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex> первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>mt[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (список <tex> mt</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> mt </tex>.
После того, как все вершины <tex>v \in V</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'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
fill(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T13:27:21Z

Freemahn: /* Алгоритм */ изменил алгоритм

==Теорема==
{{Теорема
|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>matching</tex> хранятся паросочетания <tex> (v, matching[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> matching[v] </tex> = -1). А <tex>used</tex> - обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
Функция <tex> \mathrm{dfs} </tex> возвращает <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины v первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>mt[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.

В основной программе сначала указывается, что текущее паросочетание — пустое (список <tex> mt</tex> заполняется числами -1). Затем перебирается вершина <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.

Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> mt </tex>.
После того, как все вершины <tex>v \in V</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'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
fill(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:56:09Z

Freemahn: /* Реализация */ маленькая правка

==Теорема==
{{Теорема
|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'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
fill(used, '''false''')
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:55:29Z

Freemahn: /* Реализация */ закончил редактирование кода

==Теорема==
{{Теорема
|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'''(v: '''int'''):
'''if''' (used[v]):
'''return''' '''false'''
used[v] = '''true''';
'''for''' to '''in''' g[v]:
if (matching[to] == -1 '''or''' dfs(matching[to])):
matching[to] = v
'''return''' '''true'''
'''return''' '''false'''

'''function''' '''main'''():
'''fill'''(matching, -1)
'''for''' v '''in''' V:
fill(used, false)
'''dfs'''(v)
'''for''' v '''in''' V:
'''if''' (matching[v] != -1):
'''print'''(v, " ", matching[v])

==Время работы==
:Итак, алгоритм Куна можно представить как серию из <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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:45:23Z

Freemahn: /* Реализация */ половина изменений

==Теорема==
{{Теорема
|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''' to '''in''' g[v]:
if (matching[to] == -1 || dfs(matching[to]))
matching[to] = v
'''return''' true
'''return''' false

Как вызывать:

fill(matching, -1)
'''for''' u '''in''' N:
fill(used, 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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:22:46Z

Freemahn: /* Источники */ изменил с : на *

==Теорема==
{{Теорема
|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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:20:28Z

Freemahn: /* Алгоритм */ исправил неправильное название теоремы

==Теорема==
{{Теорема
|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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:13:00Z

Freemahn: /* Алгоритм */ Убрал лишние пробелы(х2)

==Теорема==
{{Теорема
|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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:06:38Z

Freemahn: /* Алгоритм */ Убрал лишние пробелы(х2)

==Теорема==
{{Теорема
|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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:06:03Z

Freemahn: /* Алгоритм */ убрал лишние пробелы

==Теорема==
{{Теорема
|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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

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

2015-01-11T12:05:20Z

Freemahn: /* Время работы */ Убрал лишние пробелы

==Теорема==
{{Теорема
|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 стр.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

Представление символов, таблицы кодировок

2014-01-05T13:39:00Z

Freemahn: Добавил пример на python и hex-дамп

== Представление символов в вычислительных машинах ==

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

Количество символов, которые можно задать последовательностью битов длины ''n'', задается простой формулой <tex>C(n) = 2^n</tex>. Таким образом, от нужного количества символов напрямую зависит количество используемой памяти.

== Таблицы кодировок ==

На заре компьютерной эры на каждый символ было отведено по 5 бит. Это было связано с малым количеством оперативной памяти на компьютерах тех лет. В эти 64 символа входили только управляющие символы и строчные буквы английского алфавита.

С ростом производительности компьютеров стали появляться таблицы кодировок с большим количеством символов.
Первой 7 битной кодировкой стала ASCII7. В нее уже вошли прописные буквы английского алфавита, арабские цифры, знаки препинания.
Затем на ее базе была разработана ASCII8, в которым уже стало возможным хранение 256 символов: 128 основных и еще столько же расширенных. Первая часть таблицы осталась без изменений, а вторая может иметь различные варианты (каждый имеет свой номер). Эта часть таблицы стала заполняться символами национальных алфавитов.

Но для многих языков (например, арабского, японского, китайского) 256 символов недостаточно, поэтому развитие кодировок продолжалось, что привело к появлению UNICODE.

== Наиболее известные кодировки ==
===Кодировки стандарта ASCII===
{{Определение
|definition='''ASCII''' - таблицы кодировок, в которых содержатся основные символы (английский алфавит, цифры, знаки препинания, символы национальных алфавитов(свои для каждого региона), служебные символы) и длина кода каждого символа <tex>n = 8</tex> бит.
}}

''7 бит:''
* '''ASCII7''' - первая кодировка, пригодная для работы с текстом. Помимо маленьких букв английского алфавита и служебных символов, содержит большие буквы английского языка, цифры, знаки препинания и другие символы.
''Кодировки стандарта ASCII (8 бит):''
* '''ASCII''' - первая кодировка, в которой стало возможно использовать символы национальных алфавитов.
* '''КОИ8-R''' - первая русская кодировка. Символы кириллицы расположены не в алфавитном порядке. Их разместили в верхнюю половину таблицы так, чтобы позиции кириллических символов соответствовали их фонетическим аналогам в английском алфавите. Это значит, что даже при потере старшего бита каждого символа, например, при проходе через устаревший семибитный модем, текст остается "читаемым".
* '''CP866''' - русская кодировка, использовавшаяся на компьютерах IBM в системе DOS.
* '''Windows-1251''' - русская кодировка, использовавшаяся в русскоязычных версиях операционной системы Windows в начале 90-х годов. Кириллические символы идут в алфавитном порядке. Содержит все символы, встречающиеся в типографике обычного текста (кроме знака ударения).[http://ru.wikipedia.org/wiki/CP1251]
===Кодировки стандарта UNICODE===

'''Юникод''' или '''Уникод''' ( англ. Unicode ) - это промышленный стандарт обеспечивающий цифровое представление символов всех письменностей мира, и специальных символов.

Стандарт предложен в 1991 году некоммерческой организацией «Консорциум Юникода» (англ. ''Unicode Consortium, Unicode Inc.'').Применение этого стандарта позволяет закодировать очень большое число символов из разных письменностей.
Стандарт состоит из двух основных разделов: '''универсальный набор символов''' (англ. ''UCS, universal character set'') и семейство кодировок (англ. ''UTF, Unicode transformation format''). '''Универсальный набор символов''' задаёт однозначное соответствие символов кодам — элементам кодового пространства, представляющим неотрицательные целые числа.Семейство кодировок определяет машинное представление последовательности кодов UCS.

Коды в стандарте Unicode разделены на несколько областей. Область с кодами от U+0000 до U+007F содержит символы набора ASCII с соответствующими кодами. Далее расположены области знаков различных письменностей, знаки пунктуации и технические символы. Под символы кириллицы выделены области знаков с кодами от U+0400 до U+052F, от U+2DE0 до U+2DFF, от U+A640 до U+A69F.
Часть кодов зарезервирована для использования в будущем.

Юникод имеет несколько форм представления (англ. Unicode Transformation Format, UTF): UTF-8, UTF-16 (UTF-16BE, UTF-16LE) и UTF-32 (UTF-32BE, UTF-32LE). Была разработана также форма представления UTF-7 для передачи по семибитным каналам, но из-за несовместимости с ASCII она не получила распространения и не включена в стандарт.

====Кодовое пространство====
Кодовое пространство разбито на 17 плоскостей по 216 (65536) символов. Нулевая плоскость называется базовой, в ней расположены символы наиболее употребительных письменностей. Первая плоскость используется, в основном, для исторических письменностей. Плоскости 15 и 16 выделены для частного употребления.

Для обозначения символов Unicode используется запись вида «U+xxxx» (для кодов 0…FFFF) или «U+xxxxx» (для кодов 10000…FFFFF) или «U+xxxxxx» (для кодов 100000…10FFFF), где xxx — шестнадцатеричные цифры. Например, символ «я» (U+044F) имеет код 044F16 = 110310.

* '''UTF8''' - самая распространенная на данный момент кодировка из семейства UNICODE. [http://ru.wikipedia.org/wiki/UTF-8]

{|class="wikitable"
!Unicode||UTF-8||Представленные символы
|-
|<code>0x00000000</code> — <code>0x0000007F</code>||<code>0xxxxxxx</code>||ASCII, в том числе английский алфавит, простейшие знаки препинания и арабские цифры
|-
|<code>0x00000080</code> — <code>0x000007FF</code>||<code>110xxxxx 10xxxxxx</code>||кириллица, расширенная латиница, арабский алфавит, армянский алфавит, греческий алфавит, еврейский алфавит и коптский алфавит; сирийское письмо, тана, нко; Международный фонетический алфавит; некоторые знаки препинания
|-
|<code>0x00000800</code> — <code>0x0000FFFF</code>||<code>1110xxxx 10xxxxxx 10xxxxxx</code>||все другие современные формы письменности, в том числе грузинский алфавит, индийское, китайское, корейское и японское письмо; сложные знаки препинания; математические и другие специальные символы

|-
|<code>0x00010000</code> — <code>0x001FFFFF</code>||<code>11110xxx 10xxxxxx 10xxxxxx 10xxxxxx</code>||музыкальные символы, редкие китайские иероглифы, вымершие формы письменности

|-
|||<code>111111xx</code>||служебные символы c, d, e, f
|}

Также возможны коды длиной в 5 и 6 байт, но на практике они не используются. Это связано с тем, что в стандарт Unicode не входят символы с кодом выше <code>0x10ffff</code>.

====BOM====
'''Byte Order Mark (BOM)(''метка порядка байтов'')''' - Unicode символ, используемый для индикации порядка байтов текстового файла. Его кодовый символ U+FEFF (ZERO WIDTH NON-BREAKING SPACE)''неразрывный пробел с нулевой шириной'', также именуемый . По спецификации его использование не является обязательным, однако если BOM используется, то он должен быть установлен вначале текстового файла. Помимо своего конкретного использования в качестве указателя порядка байтов, символ может также указать какой кодировкой Unicode закодирован текст.
[[Файл:Bom.png|thumb|right| 400px]]

{| class="wikitable"
|+'''Представление BOM в кодировках'''
|-
! Кодирование
! Представление (Шестнадцатеричное)
|-
| UTF-8
| <code>EF BB BF</code>
|-
| UTF-16 (BE)
| <code>FE FF</code>
|-
| UTF-16 (LE)
| <code>FF FE</code>
|-
| UTF-32 (BE)
| <code>00 00 FE FF</code>
|-
| UTF-32 (LE)
| <code>FF FE 00 00</code>
|-
|}
В кодировке UTF-8, наличие BOM не является существенным, поскольку, нет альтернативной последовательности байтов. Когда BOM используется на страницах или редакторах для контента закодированного в UTF-8, иногда он может представить пробелы или короткие последовательности символов, имеющие странный вид (такие как ï»¿). Именно поэтому, при наличии выбора, для совместимости, как правило, лучше упустить BOM в UTF-8 контенте.Однако BOM могут еще встречаться в тексте закодированном в UTF-8, как побочный продукт перекодирования или потому, что он был добавлен редактором. В этом случае BOM часто называют подписью UTF-8.

Когда символ закодирован в UTF-16, его 2 или 4 байта можно упорядочить двумя разными способами (little-endian или big-endian). Изображение справа показывает это.Byte order mark указывает, какой порядок используется, так что приложения могут немедленно расшифровать контент. UTF-16 контент должен всегда начинатся с BOM.

BOM также используется для текста обозначенного как UTF-32. Аналогично UTF-16 существует два варианта четырёхбайтной кодировки — UTF-32BE и UTF-32LE.К сожалению, этот способ не позволяет надёжно различать UTF-16LE и UTF-32LE, поскольку символ U+0000 допускается Юникодом
==Примеры==
Если записать строку 'hello мир' в файл exampleBOM, а затем сделать его hex-дамп, то можно убедиться в том, что разные символы кодируются разным количеством байт. Например, английские буквы,пробел, знаки препинания и пр. кодируются одним байтом, а русские буквы - двумя
===Код на python===
<pre>
#!/usr/bin/env python
#coding:utf-8
import codecs
f = open('exampleBOM','w')
b = u'hello мир'
f.write(codecs.BOM_UTF8)
f.write(b.encode('utf-8'))
f.close()
</pre>
===hex-дамп файла exampleBOM===
{|class = "wikitable" border = "1" style="text-align:center"
|Символ
|colspan="3" |BOM
|h||e||l||l||o
|Пробел
|colspan="2" |м
|colspan="2" |и
|colspan="2" |р
|-
|Код в UNICODE
|EF
|BB
|BF
|68||65||6C||6C||6F
|20||D0||BC||D0||B8||D1||80
|-
|Код в UTF-8
|11101111||10111011||10111111
|01101000||01100101||01101100||01101100||01101111
|00100000||11010000||10111100||11010000||10111000||11010001||10000000
|}
== Ссылки ==
* [http://ru.wikipedia.org/wiki/ASCII Wikipedia: таблица ASCII]
* [http://ru.wikipedia.org/wiki/%D0%AE%D0%BD%D0%B8%D0%BA%D0%BE%D0%B4 Wikipedia: стандарт UNICODE]
* [http://ru.wikipedia.org/wiki/Byte_order_mark Wikipedia: Byte order mark]
* [http://ru.wikipedia.org/wiki/%D0%AE%D0%BD%D0%B8%D0%BA%D0%BE%D0%B4 Wikipedia: Юникод]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]