Паросочетание максимальной мощности в произвольном графе. Алгоритм.

Максимальное паросочетание — это такое паросочетание M в графе G, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.

Алгоритм Эдмонса: Основная идея – сжатие цветков. Цветок – подграф, образованный «насыщенным» нечетным циклом. Сжатие цветка — это сжатие всего нечётного цикла в одну псевдо-вершину (соответственно, все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине). Алгоритм Эдмондса ищет в графе все цветки, сжимает их, после чего в графе не остаётся "плохих" циклов нечётной длины, и на таком графе (называемом "поверхностным" (surface) графом) уже можно искать увеличивающую цепь простым обходом в глубину/ширину. После нахождения увеличивающей цепи в поверхностном графе необходимо "развернуть" цветки, восстановив тем самым увеличивающую цепь в исходном графе.(очень сложна)

Максимальное паросочетание в 2-дольном графе и потоки в сетях. Теорема Менгера, теорема о максимальном потоке в сети.

Максимальное паросочетание — это такое паросочетание M в графе G, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.

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

Потоки в сетях:

Сетью называется граф, элементам которого поставлены в соответствие некоторые параметры.

Потоком в сети назовем функцию f, сопоставляющую каждому ребру сети целое число и обладающую следующими свойствами:

(кососимметрия), (допустимость).

Теорема Менгера: Пусть G — конечный неориентированный граф и x, y — две несмежные вершины. Наименьшее число вершин, разделяющих x и y равно наибольшему числу попарно независимых (x, y)-цепей.

Теорема Форда — Фалкерсо́на — теорема о максимальном потоке в сети: величина максимального потока в графе путей равна величине пропускной способности его минимального разреза(Разрез графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один изкоторых, в частности, может быть отдельным узлом.)

Максимальное паросочетание во взвешенном графе.

Надо уточнить.

5) Задача линейного программирования. План. Опорный план.

Задача линейного программирования: Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции.

Стандартная задача: Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤» (минимального для «≥») значения функции при выполнении условий и , где k =m, s =n.

Каноническая задача: Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции при выполнении условий и , где k = 0, s = n.

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

Опорный план: План Х называется опорным планом основной задачи линейного программирования, если система векторов Aj, входящих в разложение с положительными коэффициентами xj, линейно независима.