Паросочетание в 2-дольном (не взвешенном) графе. Совершенное паросочетание, алгоритм построения, теорема Холла.

Паросочетание в 2-дольном (не взвешенном) графе. Совершенное паросочетание, алгоритм построения, теорема Холла.

Паросочетание в двудольном графе — произвольное множество рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.

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

Алгоритм построения:?

В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны количеству вершин деленных на 2.

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

Пусть дан двудольный граф, состоящий из nn синих вершин и nn красных вершин. Вершины можно разделить на nn пар (синяя-красная) так, чтобы в любой паре точки были соединены ребром тогда и только тогда, когда из любых kk синих вершин (для любого числа kk, 1⩽k⩽n1⩽k⩽n) выходят ребра в по крайней мере kk красных вершин

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

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

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

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

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

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

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

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

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

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

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

Паросочетание в 2-дольном (не взвешенном) графе. Совершенное паросочетание, алгоритм построения, теорема Холла.

Паросочетание в двудольном графе — произвольное множество рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.

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

Алгоритм построения:?

В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны количеству вершин деленных на 2.

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

Пусть дан двудольный граф, состоящий из nn синих вершин и nn красных вершин. Вершины можно разделить на nn пар (синяя-красная) так, чтобы в любой паре точки были соединены ребром тогда и только тогда, когда из любых kk синих вершин (для любого числа kk, 1⩽k⩽n1⩽k⩽n) выходят ребра в по крайней мере kk красных вершин