# Смотрите в качестве примера на конспекты, которые отмечены как хорошие.
# В конспекте не должно быть орфографических, пунктуационных, речевых, фактических, логических и других ошибок. Используйте spell checker.
# Используйте вики-шаблоны [[Шаблон: Определение]], [[Шаблон: Теорема]], [[Шаблон: Лемма]], [[Шаблон: Утверждение]], [[Шаблон: Задача]] ([[Справка по шаблонам]]).
# Если ваш конспект написан про какое-то конкретное понятие или теорему, не надо делать отдельный пункт "Формулировка":
{|
# Не используйте тег <nowiki> <br> </nowiki>. Для перевода строки в вики надо вставлять пустую строку. Видимо, единственное место, где можно использовать его — внутри шаблонов — там переводы строки почему-то не работают.
# Ставьте категорию <nowiki>[[Категория: Дискретная математика и алгоритмы]]</nowiki> и подкатегорию с названием подтемы (например, <nowiki>[[Категория: Динамическое программирование]]</nowiki>). Список подкатегорий [[:Категория:Дискретная математика и алгоритмы | тут]].
# Оформляйте ссылки на источники [http://ru.wikipedia.org/wiki/Википедия:Ссылки_на_источники правильно]. Пример хорошего оформления {{---}} конспекты [[Алгоритм ХаффманаУкконена]] и [[Сокращенная и минимальная ДНФПравило Лаулера]].
# Не используйте сокращения.
== Картинки ==
# Картинки, где только возможно, надо делать в векторе. Для этого можно пользоваться Microsoft Visio, Inkscape, GraphwizGraphviz, Metapost и им подобными.
== Источники информации==
# Используйте ссылки на другие конспекты.
# В конспекте должны быть указаны источники или литература. Причем указывать ссылки не просто на википедию, а на конкретную статью (как [http://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C Википедия {{---}} Экспоненциальная запись], на английскую {{---}} как [http://en.wikipedia.org/wiki/Scientific_notation Wikipedia {{---}} Scientific notation]). Для книг достаточно указать автора, название, издание и номер страницы.
#* Используем какой-то определённый стиль именования переменных(я бы рекомендовал lowerCamelCase для переменных и функций и UpperCamelCase для классов)
== Алгоритм Штор-теорема Вагнера нахождения минимального разреза ==
== Необходимые определения ==<tex>G</tex> - неориентированный взвешенный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами.{{Определение |definition='''Разрезом''' называется такое разбиение множества <texb>VМинор графа</tex> на два подмножества <tex>A</tex> и <tex>B</tex>, что:* <tex>A, B \subset V</tex>;* <tex>A, B \neq \emptyset</tex>;* <tex>A \cap B = \emptyset</tex>;* <tex>A \cup B = V</texb>(англ. }} {{Определение |definition=''Graph minor'Весом разреза''' называется сумма весов ) G будем называть граф H, если H может быть образован из G удалением рёбер, проходящих через разрез, т.е. таких и вершин и стягивания рёбер, один конец которых принадлежит <tex>A</tex>, а второй конец - <tex>B</tex>.* <tex>w(A, B) =</tex> <tex dpi = "140">\sum\limits_{uv \in E, u \in A, v \in B} w(u, v)</tex>
}}
Эту задачу называют "глобальным минимальным разрезом". Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его O(n^2) раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г. В общем случае допускаются петли и кратные рёбра, все кратные рёбра можно заменить одним ребром с их суммарным весом а петли не влияют на решение. Поэтому будем считать, что кратных ребер и петель во входном графе нет. == Алгоритм == Идея алгоритма довольно проста. Будем <tex>n-1</tex> раз повторять следующий процесс[[Категория: находить минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>, а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности <tex>s</tex> и <tex>t</tex>). В конце концов, после <tex>n-1</tex> итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех <tex>n-1</tex> найденных разрезов. Действительно, на каждой <tex>i</tex>-ой стадии найденный минимальный разрез <tex>\langle A,B \rangle</tex> между вершинами <tex>s_i</tex> и <tex>t_i</tex> либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины <tex>s_i</tex> и <tex>t_i</tex> невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну. Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин <tex>s</tex> и <tex>t</tex>. Для этого вводим некоторое множество вершин <tex>A</tex>, которое изначально содержит единственную произвольную вершину <tex>s</tex>. На каждом шаге находится вершина, наиболее сильно связанная с множеством <tex>A</tex>, т.е. вершина <tex>v \not\in A</tex>, для которой следующая величина <tex dpi = "140">w(v,A) = \sum\limits_{(v,u) \in E, \atop u \in A} w(v,u)</tex> максимальна (максимальна сумма весов рёбер, один конец которых <tex>v</tex>, а другой принадлежит <tex>A</tex>).Справка]]
