Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов

В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 66

DJVU-файл В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 66 Дискретная математика (2169): Лекции - 2 семестрВ.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов: Дискретная математика - DJVU, страница 66 (2169) - СтудИзба2019-04-28СтудИзба

Описание файла

DJVU-файл из архива "В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 66 - страница

Утверждение 77.4. Множество 2 является наимюсьшим верши>ьным покрытием графа 6. с Утворждепие достаточно доказать для связных графов. Пусть (а, Ь) — произвольная дуга графа 6. Если а си У, Ь ее Х, то эти вершины либо обе помечены, либо пот. В обоих случаях дуга (а, Ь) ипцндгптна вершине множества /. Пусть а ~ Х, Ь еэ У. Тогда, если вершина а не помочепа, то а си/. Если же а помечена, то и вершина Ь помечена п, следовательно, Ь ~ 2.

Итак, всякая дуга графа 6 ипцидентна некоторой вершине множества 7, т. е, Я вЂ” покрытие графа 6. Кроме того, легко видеть, что ~l! =-!Т~, где Т вЂ” мпонсество всех дуг графа С, ведущих из множоства У. Мполсеству Т в графе 6 соответствует наибольшее паросочетапие. Поэтому из теоремы 32.2 следует, что вершинное покрытие Я является навмопьшим. З Использованный здесь метод чередующихся цепей играет важную роль и при решении более общих задач.

Одну из пих мы сейчас рассмотрим. Пусть С = (Х, У, Е6) — полный двудольный взвешенный граф, !Х! =!У! = п. Требуется найти в графа 6 совершенное паросочетание, вес которого минимален. Легко видеть, что это — упоминавшаяся ранее задача о назначениях (см. гл. 1Ъ', 3 30). Совершенное паросочетание минимального веса назовем для краткости оптимальным решением. Задача о назначениях обладает двумя простыми свойствамн: 1. Поскольку для каждой вершины любое совершенное паросочетаппе содержит в точности одно ребро, ип- 358 цидентное этой вершине, то множество оптимальных решений не изменится, если веса всех ребер, ипцидентпых какой-либо вершине, увеличить (уменьшить) на одно и то же число.

2. Если веса всех ребер графа неотрицательны и вес некоторого совершенного паросочетапия равен пулю, то оно является оптимальным решением. Пусть, как обычно, и~(х, у) — вес ребра ху. Будем считать, что ю(х, у)~0 для каждого ребра хушВС. Из первого свойства следует, что случай, когда имеются ребра отрицательного веса, сводится к нашему. Кроме того, это свойство позволяет, затратив 0(п») операций, переити к взвешенному графу, у которого каждой вершине инцндентно ребро нулевого веса и веса всех ребер пеотрицательны. Для этого достаточно изменить матрицу весов графа С следующим образом: сначала вычесть из всех элементов каждой строки минимальный элемент атой строки, а затем то же самое проделать со столбцами. Будем считать, что эта операция уя«е проделана и граф С обладает требуемыми свойствами.

Пусть А<=Х, В~ У и а — некоторое число. Будем говорить, что и »рафу С применяется операция (А, В, и), если сначала из веса каждого ребра, ипцндеятного вершине из множества А, вычитается с», а затем к весу кая«доге ребра, инцидентного вершине из В, прибавляется а. Согласно свойству 1 получившийся в результате взвешенный граф имеет то»ке множество оптимальных решений, что и граф С.

Кроме того, ребра вида аЬ, где а ш А, Ь ш В, в преобразованном графе будут иметь то же веса, что и в исходном. Пусть Т=(Х, У, С) — дзудольный граф и М вЂ” паросочетапне в этом графе. Будем, как и ранее, обозначать через Т = Т(Т, М) ориентированный двудольный граф, получеппый из графа Т путем ориентаций «от У к Х» всех ребер паросочетапия М и «от Х к У» остальных ребер этого графа. Будем считать, что граф С задан матрпцей весов. Алгоритм л»д построения совершенного паросочетания минимального веса в двудольном взвешенном графе. 1. Построить граф Т =(Х, У, С), сГ= (ху: ю(х, у)= О).

2. Найти в графе Т максимальное паросочетапие ЛХ. Пусть Хн н Ун — множества вершин, не насыщенных паросочетапнем М н входящих, соответственно, в доли Хи У. 359 3. Если Хм = Ув = Ы, то конец (ЛХ вЂ” оптимальное решение задачи]. Иначе построить граф Т=Т(Т, зд), 4. Применить к графу 7' 1н пса в ширпзу (алгоритм .Фд) из множества Хи.

Если найден (х, у)-путь Р, хдн <н Хя, у ~ Уя, то аерейтн к п. 5. Иначе перейти к п. 7. 5. Преобразовать граф Т, зацепив в нем каждую дугу пути Р па обратную. Пусть Хя = (ал х ~и Х, г( (х)= = О), Ум = (йч рдн У, И+(р)= О) (путем изменения йХ вдоль увеличивающей цепи найдено новое паросочетание в графе Т =(Х, У, П), Хв<=Х, У„~ У вЂ” подмножества вершин графа Т, пе насыщенных новым паросочетапием]. 6. Если Х.

= У = Ы, то конец (множество всех таких ребер хр, что х ш Х, у я У и (у, х) — дуга графа Т, составляет совершенное паросочетание минимального веса в исходном графе 6]. Иначе перейти к п. 4. 7. Пусть Х' ~= Х и У' ~ У вЂ” подмножества вершин графа Т, получивших пометки в результате поиска в ширину (в п. 4). Среди ребер графа С, имеющих вид ху, х я Х', уев У вЂ” Г, найти ребро минимального веса. Пусть сд — вес этого ребра. 8.

Модифицировать веса дуг графа 6, применив к нему операцию (Х', У', а). 9. Модифицировать граф Т, добавив к нему все такие дуги (х, у), что х ~иХ, у ш У вЂ” У', и(х, у)= О, и удалив все такие дуги (х, у), что х~нХ вЂ” Х, у~в Г. Перейти к п. 4. Займемся теперь обоснованием алгоритма Фд.

Корректность пп. 1 — 3 не вызывает сомнений. Легко видеть такдке, что каждый из этих пунктов можно выполнить за время 0(пд). Остальные пункты алгоритма рассмотрим более подробно. Каждое выполнение п. 5 увеличивает па единицу число вершин р ш У, для которых о+(у) = 1. Следовательно, этот пункт выполняется не более п раз. Наша ближайшая цель — показать, что после выполнения пп. 4, 6 — 9 не более чем и раз подряд обязательно произойдет переход к п.

5, т. е. очередное выполнение п. 4 закончится отысканием пути Р. Рассмотрим подробнее пп. 7 — 9. После окончания п. 4 и перехода к п. 7 кансдая дуга графа Т ипцидентна по крайней мере одной вершине множества (Х вЂ” Х')0 Г. Это сразу следует из утверждения 77.4. Таким образом, каждое ребро нулевого 360 веса в графе С ияцидептио одной из вершки этого миожества. С другой стороны, поскольку Х~~И, Ум««И, то Х «ь Х, У чь У. Поэтому из правила выбора величины а з п. 7 следует, что с«) О.

После модификации графа С в п. 8 веса всех его ребер останутся веотрицательвыми (это следует пз правила выбора и). В результате последующей модификации графа Т (и. 9) ого дуги во-прежнему будут соответствовать ребрам пулевого веса в графе 6, причем дуги вида (у, х), х ж Х, у ж У, будут соответствовать паросочетакию нулевого веса в графе 6. Модификация графа Т в п. 9 обладает двумя важиыми свойствамк. Во-первых, удаленные дуги этого графа направлены от непомеченных вершин доли Х.

Поэтому все зершииы, достижимые из Хв в «старом» графе Т, достижимы из этого миожества и в «иовом» графе Т. Во-вторых, добавлеипые дуги направлены от помеченных вершил доли Х к иепомечепиым вершинам доли У. Таким образом, примеяение поиска в ширину к модифицироваииому графу Т (п.

4) приведет к тому, что дополнительно будет помечена по крайней мере одна вершина доли У. Поскольку ) У) = п, то после выполиекия пп. 4, 7 — 9 ие более чем п раз подряд помеченной окажется иекоторая вершина множества Ув, т. е. будет найден путь Р. в затем последует выполнение п. 5. Как уже было показано, и. 5 (а значит, и п.

8) выполпяется пе более п раз. Поэтому каждый из пп. 4, 7 — 9 выполняется не более и' раз. Легко видеть, что трудоемкость каждого из пп. 1 — 9 ие превосходит 0(пг). Поэтому время работы алгоритма в целом оцеиивается сверху величиной 0(п«). Как отмечалось выше, после выполнения п. 8 веса всех ребер графа 6 остаются неотрицательными, и, следовательио, множество оптимальных решений пе меияется. Условие окончания Хи = Ув = ю означает, что в «последием» графе Т имеется п дуг, паправлеииых от Х; к У, которым соответствует совершенное паросочетаиие нулевого веса в «последнем» графе С.

Согласно свойству 2 оио является оптимальным решением исходной задачи. резюмируем все выше изложенное в виде теоремы. Т е о р е м а 77.5. Алгоритм А«строит совершенное паросочетание минимального веса в двудольном взвешенном графе С (Х, У, ЕС), !Х! = (У( =и, за время 0(и'). 3 а м е ч а н и е. Известен алгоритм, решающий эту задачу за время 0(и»). В алгоритме лб» оценка 0(п«) возникает, по существу, из-за того, что приходится 0(п') раз выполшггь операцию (Х', У', а), которая сама требует времени 0(и'). Снижение оценки до 0(п') достигается за счет того, что результат этой операции удается получить за время 0(п).

Недавно опубликован алгоритм, оценка трудоемкости которого во многих случаях предпочтительнее 0(п»). Эта г и' В и В 7 В В и ~ б г С, Ч« В В 7 б и т б В зз Рис. 77.3 оценка имеет внд 0(и»» 1ои(пТ) ), где Т вЂ” паиболыпий из весов ребер графа. .«Чтзь ««33) Пример. На рис. 77.3 представлена матрица весов И' = ~ И';,б двудольного графа 6 =(Х, У, ЕС), у которой И'е = ю(хв х,), х; ~н Х, у; ~ У. Там же изображен граф Т, построенный по максимальному паросочетанию М = =- (х»уь х~у») нулевого веса в графе О.

Соответствующие этому паросочетанию дуги графа Т обведены жирными лнпнямн, а элементы матрицы И' отмечены звездочками. Перед первым выполнением п. 4 имеем Хв = (х» х4~ х»)~ ум = (У»1 У«1 УБ). ПОиск В ширину из Хм дает Х' = (хь х», х«, х»), У' = (у1). Вершины множества Х' 0 У' будем отмечать значком «+».

Поскольку пути нз Хн в Ув пег, то переходим к пп. 7 — 9. Находим с« = = И'»» = 1 и выполняем операцию ((х», хз, х«, хз), (У1), 1) т. е. вычитаем 1 из всех элементов в строках 2, 3, 4, 5 и прибавляем это число ко всем элементам первого столбца. В результате к графу Т добавится дуга (хз, у»). Модифицированная матрица )т (т. е.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее