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

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...

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



Максимальное паросочетание — это такое паросочетание 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, линейно независима.






Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой...

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...





© cyberpedia.su 2017 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав

0.006 с.