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

Централизованный алгоритм для WCP

2018-03-16T10:18:27Z

217.118.78.112:

[[Категория: Параллельное программирование]]
'''Централизованный алгоритм для WCP''' – алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется слабый конъюнктивный предикат.

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

Суть алгоритма:
* Есть один процесс-координатор, который ответственный за поиск согласованного среза;
* Остальные процессы обычные, их задача проверять свои локальные предикаты;
* Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время;
* Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса;
* Срез-кандидат согласован тогда и только тогда, когда все соответствующие вектора попарно несравнимы;
* Координатор хранит вектора среза-кандидата и флажок для каждой его компоненты: красный – этот элемент не может быть частью согласованного среза, зеленый – может;
* Начальное состояние – все по нулям, красные;
* Обрабатываем приходящие сообщения только от красных процессов, сообщения от зеленых ставим в очередь:
** Сравниваем пришедший вектор попарно с другими процессами, если новый вектор больше, то делаем меньший процесс красным;
** После обработки сообщения делаем процесс зеленым.
* Если все зеленое, то мы нашли согласованный срез.

Теорема Холла

2012-12-22T21:35:03Z

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

==Определения==

Пусть <tex>G(V,E)</tex> - двудольный граф. <tex>L</tex> - множество вершин первой доли. <tex>R</tex> - множество вершин правой доли.
{{Определение
|id=def1.
|nеat=1
|definition='''Полным(совершенным)''' паросочетанием называется паросочетание, в которое входят все вершины.
}}
{{Определение
|id=def2.
|nеat=1
|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' <tex>X</tex> определим формулой: <tex>N(X)= \{ y \in V: (x,y) \in E \}</tex>
}}

==Теорема==
{{Теорема
|id=th1.
|author=Холл
|statement=Полное паросочетание существует тогда и только тогда, когда для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>.
|proof=
* Очевидно, что если существует полное паросочетание, то для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>. У любого подмножества вершин есть по крайней мере столько же "соседей"("соседи по парасочетанию").
Пусть граф <tex>G'</tex> изначально имеет левую долю <tex>L'</tex>, которая содержит одну любую вершину из <tex>L</tex>, и правую <tex>R' = R</tex>.
*В обратную сторону докажем по индукции(будем добавлять какую-нибудь вершину <tex>x</tex> из <tex>L</tex> в <tex>G'</tex> и доказывать, что в <tex>G'</tex> есть паросочетание, насыщающее все вершины из <tex>L'</tex>). Таким образом, в конце получим что <tex>G'</tex> совпадает с <tex>G</tex>. Из этого будет следовать существование в <tex>G</tex> полного паросочетания.
#База: Одна вершина соединена хотя бы с одной вершиной из <tex>R'</tex>. Следовательно база верна.
#Переход: Пусть после <tex>k</tex> добавлений в <tex>G'</tex> можно построить паросочетание <tex>P</tex>, насыщающее все вершины из <tex>L'</tex>. Докажем что после добавления вершины <tex>x</tex> в <tex>G'</tex> будет существовать паросочетание, насыщающее все вершины <tex>L'</tex>.Добавим <tex>x</tex> в <tex>G'</tex>. Рассмотрим множество вершин <tex>H</tex> — все вершины, достижимые из <tex>x</tex>, если можно ходить из <tex>R'</tex> в <tex>L'</tex> только по ребрам из <tex>P</tex>, а из <tex>L'</tex> в <tex>R'</tex> по любым ребрам из <tex>G'</tex>. Тогда в <tex>H</tex> найдется вершина <tex>y</tex> из <tex>R'</tex>, не принадлежащая <tex>P</tex>, иначе, если рассмотреть вершины <tex>H_L</tex>(вершины из <tex>H</tex> принадлежащие <tex>L'</tex>), то для них не будет выполнено условие: <tex>|H_L| > |N(H_L)|</tex>. Тогда существует путь из <tex>x</tex> в <tex>y</tex>, который будет удлиняющим для паросочетания <tex>P</tex>(т.к из <tex>R'</tex> в <tex>L'</tex> мы проходили по ребрам паросочетания <tex>P</tex>). Увеличив паросочетание <tex>P</tex> вдоль этого пути, получаем искомое паросочетание. Следовательно предположение индукции верно.
}}

==Примечания==
Иногда теорему называют теоремой о свадьбах.

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

==Ссылки==
*[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A5%D0%BE%D0%BB%D0%BB%D0%B0 Теорема Холла — Википедия]

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

Теорема Холла

2012-12-22T21:33:07Z

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

==Определения==

Пусть <tex>G(V,E)</tex> - двудольный граф. <tex>L</tex> - множество вершин первой доли. <tex>R</tex> - множество вершин правой доли.
{{Определение
|id=def1.
|nеat=1
|definition='''Полным(совершенным)''' паросочетанием называется паросочетание, в которое входят все вершины.
}}
{{Определение
|id=def2.
|nеat=1
|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' <tex>X</tex> определим формулой: <tex>N(X)= \{ y \in V: (x,y) \in E \}</tex>
}}

==Теорема==
{{Теорема
|id=th1.
|author=Холл
|statement=Полное паросочетание существует тогда и только тогда, когда для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>.
|proof=
* Очевидно, что если существует полное паросочетание, то для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>. У любого подмножества вершин есть по крайней мере столько же "соседей"("соседи по парасочетанию").
Пусть граф <tex>G'</tex> изначально имеет левую долю <tex>L'</tex>, которая содержит одну любую вершину из <tex>L</tex>, и правую <tex>R' = R</tex>.
*В обратную сторону докажем по индукции(будем добавлять какую-нибудь вершину <tex>x</tex> из <tex>L</tex> в <tex>G'</tex> и доказывать, что в <tex>G'</tex> есть паросочетание, насыщающее все вершины из <tex>L'</tex>). Таким образом, в конце получим что <tex>G'</tex> совпадает с <tex>G</tex>. Из этого будет следовать существование в <tex>G</tex> полного паросочетания.
#База: Одна вершина соединена хотя бы с одной вершиной из <tex>R'</tex>. Следовательно база верна.
#Переход: Пусть после <tex>k</tex> добавлений в <tex>G'</tex> можно построить паросочетание <tex>P</tex>, насыщающее все вершины из <tex>L'</tex>. Докажем что после добавления вершины <tex>x</tex> в <tex>G'</tex> будет существовать паросочетание, насыщающее все вершины <tex>L'</tex>.Добавим <tex>x</tex> в <tex>G'</tex>. Рассмотрим множество вершин <tex>H</tex> — все вершины, достижимые из <tex>x</tex>, если можно ходить из <tex>R'</tex> в <tex>L'</tex> только по ребрам из <tex>P</tex>, а из <tex>L'</tex> в <tex>R'</tex> по любым ребрам из <tex>G'</tex>. Тогда в <tex>H</tex> найдется вершина <tex>y</tex> из <tex>R'</tex>, не принадлежащая <tex>P</tex>, иначе, если рассмотреть вершины <tex>H_L</tex>(вершины из <tex>H</tex> принадлежащие <tex>L'</tex>), то для них не будет выполнено условие: <tex>|H_L| > |N(H_L)|</tex>. Тогда существует путь из <tex>x</tex> в <tex>y</tex>, который будет удлиняющим для паросочетания <tex>P</tex>(т.к из <tex>R'</tex> в <tex>L'</tex> мы проходили по ребрам паросочетания <tex>P</tex>). Увеличив паросочетание <tex>P</tex> вдоль этого пути получаем искомое паросочетание. Следовательно предположение индукции верно.
}}

==Примечания==
Иногда теорему называют теоремой о свадьбах.

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

==Ссылки==
*[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A5%D0%BE%D0%BB%D0%BB%D0%B0 Теорема Холла — Википедия]

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

Теорема Холла

2012-12-22T21:24:58Z

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

==Определения==

Пусть <tex>G(V,E)</tex> - двудольный граф. <tex>L</tex> - множество вершин первой доли. <tex>R</tex> - множество вершин правой доли.
{{Определение
|id=def1.
|nеat=1
|definition='''Полным(совершенным)''' паросочетанием называется паросочетание, в которое входят все вершины.
}}
{{Определение
|id=def2.
|nеat=1
|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' <tex>X</tex> определим формулой: <tex>N(X)= \{ y \in V: (x,y) \in E \}</tex>
}}

==Теорема==
{{Теорема
|id=th1.
|author=Холл
|statement=Полное паросочетание существует тогда и только тогда, когда для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>.
|proof=
* Очевидно, что если существует полное паросочетание, то для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>. У любого подмножества вершин есть по крайней мере столько же "соседей"("соседи по парасочетанию").
Пусть граф <tex>G'</tex> изначально имеет левую долю <tex>L'</tex>, которая содержит одну любую вершину из <tex>L</tex>, и правую <tex>R' = R</tex>.
*В обратную сторону докажем по индукции(будем добавлять какую-нибудь вершину <tex>x</tex> из <tex>L</tex> в <tex>G'</tex> и доказывать, что в <tex>G'</tex> есть паросочетание, насыщающее все вершины из <tex>L'</tex>). Таким образом, в конце получим что <tex>G'</tex> совпадает с <tex>G</tex>. Из этого будет следовать существование в <tex>G</tex> полного паросочетания.
#База: Одна вершина соединена хотя бы с одной вершиной из <tex>R'</tex>. Следовательно база верна.
#Переход: Пусть после <tex>k</tex> добавлений в <tex>G'</tex> можно построить паросочетание <tex>P</tex>, насыщающее все вершины из <tex>L'</tex>. Докажем что после добавления вершины <tex>x</tex> в <tex>G'</tex> будет существовать паросочетание, насыщающее все вершины <tex>L'</tex>.Добавим <tex>x</tex> в <tex>G'</tex>. Рассмотрим множество вершин <tex>H</tex> — все вершины, достижимые из <tex>x</tex>, если можно ходить из <tex>R'</tex> в <tex>L'</tex> только по ребрам из <tex>P</tex>, а из <tex>L'</tex> в <tex>R'</tex> по любым ребрам из <tex>G'</tex>. Тогда в <tex>H</tex> найдется вершина <tex>y</tex> из <tex>R'</tex>, не принадлежащая <tex>P</tex>, иначе, если рассмотреть вершины <tex>H_L</tex>(вершины из <tex>H</tex> принадлежащие <tex>L'</tex>), то для них не будет выполнено условие: <tex>|H_L| > |N(H_L)|</tex>. Тогда существует путь из <tex>x</tex> в <tex>y</tex>, который будет удлиняющим для паросочетания <tex>P</tex>(т.к из <tex>R'</tex> в <tex>L'</tex> мы проходили по ребрам паросочетания <tex>P</tex>). Увеличив паросочетание P вдоль этого пути получаем искомое паросочетание. Следовательно предположение индукции верно.
}}

==Примечания==
Иногда теорему называют теоремой о свадьбах.

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

==Ссылки==
*[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A5%D0%BE%D0%BB%D0%BB%D0%B0 Теорема Холла — Википедия]

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