Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2017-06-11 | 720 |
5.00
из
|
Заказать работу |
|
|
Максимальное паросочетание — это такое паросочетание 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-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!