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

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

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

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

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

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

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

Рассмотрим мультиграф Л, получающийся из графа Р () Рг заменой каясдой дуги, входящей одновременно в Р' и Рг„двумя экземплярами этой дуги. Очевидно, что Л пе содержит отрицателыгых контуров. Поэтому, согласно утверждению 76.3, Х содержит такой (1, /)-путь Р, что ю(Ь)~ и~(Р) и, следовательно, (Р')= (Р:)+и(Р',) (Р')+ (Р.') = (Е)~.(Р) Это ~еравенство противоречит минимальности Рг. Таким образом, пути Рг и Рг являются кратчайшими среди, соответственно, (1, (г)- и ((г, 1)-путей, все внутренние вершины которых принадлежат множеству (1, 2, ..., й — 1).

Поэтому, воспользовавшись предположением индукции, получим И ~ч = И'~,, '+ И "„' = ю (Р~) + М) = «(Р'). а Теорема 76.5. Время работы алгоритма эвг пе превосходит 0((С~з). Если граф С не содержит отрицательных контуров, то Итц — вес кратчайшего (1, ])-пути в графе С для всех 1, 7 =1., и, и =!С!. Если же такие контуры в графе итлеются, то существуют такие числа и и 1, что Итй(0. > Справедливость первого утверждения теоремы очевидна, поскольку каждая из ке более чем !С~ итераций выполняется за время 0 ~ С ~ г. Второе утверждение теоремы непосредственно следует из утверждения 76.4.

Допустим теперь, что граф С содержит отрицательные контуры. Пусть т — такой наименьший индекс, что для некоторой вершины 1 в графе С имеется отрицательный контур о', содеря ащий только ( и некоторые верзпипы множества (1, 2, ..., гп). Ясно, что контур д включает вершину и. Тогда прн любых 1, 1 = 1, и число Иг~ н~ равно весу кратчайшего (1, 7)-пути, все внутренние вершины которого принадлежат множеству (1, 2, ..., т — 1). Доказательство этого факта дословно повторяет доказательство утверждения 76.4. Контуру В соответствуют ((, т)-путь Р, и (т, ()-путь Рг, такие, что Р~ 6 Рг = о'.

Поскольку внутренние вершины путей Р~ и Рг принад- 332 лежат множеству (1, 2, ..., лг — 1), то ю(Р,)>Ига 1 й(рв))И7 ~. Следовательно, ' И, '+ И'; 'е..ю(рг)+ +и(рв)=ю(Я), т. е. Игг1 ш1п(О,И7' '+ И",",,') с'.О. <1 Рис. 76.2 Пример 2. Ниже приведены резулт,таты гьвполлония пан<дай из четырех итераций алгоритма для графа, изображенного на рис.

76,2: Найдем, например, с помощью матрицы Ре кратчайпшй (2, 1)-путьорвг = 4, Ре, = 3, Ре„= 2 Слодоиатольпо, (2, 3, 4, 1) — кратчайший (2, 1)-путь. 23 В, ь. Биевичев и ав. зсз -.-(' ' ') '-(-' -' -'') .-('- -' -'') Ив 02 — 1 '-('-'-) 0111 ре 2022 4440,, О111 рг 20221 = ззоз~ 4140, "-('"':~ 0121 рз (2023 =('3303 е41 2 0 0121, ре (4023) !~ 1~ :4 1 2 О, 4 77. Наибольшие пароеочетапия и задача о назначениях Задача построения наибольших паросочетаний в графе широко распространеяа, и для ее решения имеются аффективные алгоритмы. Эти алгоритмы основаны па методе чередующихся цепей, восходящем к Дж.

Петерсену. Пусть М вЂ” паросочетанне в графе 6. Цепь графа 6, ребра которой поочередно входят и не входят в М, называется чередующейся относительно М. Цепь длины 1 1 е, я е, 5 Рвс. 77Л по определению также чередующаяся. Ребра цепи называются темными или светлыми, если они входят или, соответственно, не входят в М. Вершины графа 6, инцидентные ребрам из М, называются насыщенными, все другие вершины — ненасыщенными. Рассмотрим, например, граф на рис. 77.1, Множество ребер М= (еп еп е1о) является в С паросочетанием; Р=(7,8, 4, 1,2,5) (2) — чередующаяся относительно М цепь; е1 = (1, 2), ею= = (4, 8) — томные ребра Р; ел = (1, 4), ее=(2, 5), ем =- = (7, 8) — светлые ребра Р; (1, 2, 3, 4, б, 8) и (5, 7, 9, 10) — лшожества насыщенных и ненасыщенных вершин соответственно.

Очегидпо, что если в графе С существует чередующаяся относительно паросочетапия М цепь, соединяющая две несовпадающие ненасыщенные вершины, то можно построить в С паросочетанне с большим числом ребер, чем в М. В самом доле, в такой цепи число темных ребер на единицу меньше числа светлых. Удалив из М 354 все темные ребра и присоединив все светлые, получим новое паросочетание, в котором число ребер на единицу больше. По отой причине чередующуюся относительно паросочотання ЛХ цепь, соединяющую две различные ненасыщеппыо вершины, будом называть увеличивающей относительно ЛХ цепью в графе С.

Итак, отсутствие увеличивающих относительно М цепей необходимо, если паросочетание М наибольшее. Это условие оказывается и достаточным. Именно, верна Теорема 77.1. Наросочетание М в графе является наибольшим тогда и только тогда, когда в етом графе нет увеличивающих относительно М з)елей. > Необходимость условия теоремы, как выше отмечалось, очевидна. Достаточность докажем от противного. Пусть ЛХ1 также является паросочетанием в 6 и ~ЛХз) ) ) ~ЛХ~. Рассмотрим граф Н, образованный ребрами, входящими в сумму ЛХ и ЛХз по модулю 2, т. е.

в (М0 М~)~ ~(ЛХ 0 М1). Так как произвольная вершина о этого графа ннцпдентпа пе более чем одному ребру каждого из паросочетапяй М и Мь то ее степень не болыпе чем 2. Если йод о = 2, то одно из инцидентных вершине о ребер входит в ЛХ, другое — в ЛХь Поэтому любая связная компонента графа Н является либо циклом, содержащим одно и то же число ребер из М н из Мн либо чередующейся относительно ЛХ цепью. Но ~М1~ ) ~ЛХ~, следовательно, среди этих компонент обязательно есть чередузощаяся относительно М цепь, нрайние ребра которой (порзое и последнее) входят в ЛХо Тогда крайние вершины этой цепи не насыщены паросочетанием ЛХ, что противоречит условию теоремы. 3 Для иллюстрации снова обратимся к графу С на рис.

77.1. Чередующаяся относительно паросочетания (1) цепь (2) соединяет ненасыщенные вершины 5 и 7. Следовательно, можно построить паросочетание М' с большим числом ребер: ЛХ' =(М~(еь е1ь)) 0 (ез, ез, е1з) = (ез, ез, ен езз) Паросочетание ЛХ' также не является наибольшим: (9, 10) — увеличивающая относительно ЛХ' цепь. Паросочетание М = М 0 (е!з) = (ез, ез, ез е!3 е~з) — папболыпее, сз1(С) = 5.

Таким образом, теорема 77.1 подсказывает следующую стратегию поиска наиболыпсго паросочетания: на- 23» 355 чзв с произвольного паросочетания М, строить последовательность М = М, Мх М», ..., в которой паросочетанпе М„+, получается из М, с помощью только что рассмотренного изменения вдоль некоторой увеличивающей цепи. Поскольку )М„+1! = !М,! + 1, то для получения напболшчего наросочетапия потребуется не более ~6~!2 итераций (т.

е. переходов от М, к М„+1). В качестве М можно взять, например, произвольное ребро графа или, что лучше, некоторое максимальное паросочетание, так что исходное паросочетание всегда имеется в нашем распоряжении. Поэтому разработка аффективного алгоритма, основанного на указанной стратегии, сводится к построению процедуры, которая быстро находит увеличивающую цепь в графе, либо выявляет ее отсутствие. Ограничимся случаем двуРис. 77.2 дольного графа, хотя такая процедура (а значит, и эффективный алгоритм отыскания наибольшего паросочетаппя) известна и в случае произвольного графа.

Итак, пусть 6=(Х, У, Е) — двудольный граф и М вЂ” паросочетапве в этом графе. Поставим в соответствие графу 6 и паросочетапию М вспомогательный ориентированный двудольпып граф 6=(Х, У, А), полагая Л =Л10Л«, где Л~ -— -((у, х): х ш Х, уж У, ху = М), Аз= ((х, у): х«н е Х, у е У, хр я ЕРМ). Иными словами, чтобы получить граФ 6, достаточно придать ориентацию «от У к Х» всем ребрам графа 6, входящим в паросочетание М, и «от Х к У» всем остальным ребрам этого графа. На рис. 77.2 изображены граф 6 с паросочетанием М (выделено жирными линияни) и граф 6. Обозначим через Хи н У„множества ненасыщенных вершин, входящих, соответственно, в Х и У.

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

Эта операция вместе с поиском пути Р составляет итерацию приводимого алгоритма. Предполагается, что граф 6 задан списками смежности. Алгоритм .Ф, построении наибольшего паросочетания в двудольном графе. 1. Построить какое-либо максимальное паросочетание М в графе 6. 2. По графу 6 и паросочетапию М построить граф 6. 3. Пусть в графе С Х =(х: х~нХ, д (х)=0), У+= =(у: ун У, д~(у)= О) (в графе 6 Х-0 Ул — множество вершин, не насыщенных текущим паросочетанием]. Выполнить в графе 6 поиск в ширину (алгорнтм Фз) из множества Х .

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

2. Утверждение 77.3. Алгоритм Фз строит наибольшее наросочетание е деудольном графе 6=(Х, У, ЕС) за гремя 0(]Е6] ш(п (]Х!, ] У])). с' То, что алгоритм корректен и построенное им паросочетание является наибольшим, следует из теоремы 77А и утвернгдения 77.2. Очевидно также, что число итераций алгоритма (т. е. выполнений п. 2 — 5) не превосходит величины шш (]Х], ]У]), поскольку па каждой итерации, кроме последней, величины ]Х ] и ]У+] уменьшаютсн па единицу. Согласно утверждению 76.2 п. 3 выполняется за время 0(]ЕС]).

Легко покааать, что зта же оценка трудо- емкости справедлива и для остальных шагов алгоритма. Таким образом, время выполнения отдельной итерации составляет 0(~ЕС~), а алгоритма в целом— 0(~ЕС~ шш (~Х~, ~ У~)). з Вместо с наибольшим паросочетанием алгоритм .Фз фактически находит и наименьшео вершинное покрытие в графе С. В результате последнего выполнения п. 3 алгоритма будет установлено отсутствие пути из Х в У+ в графе С. Следовательно, только часть вершин этого графа будет иметь метки после окончания поиска в ширину пз Х . Обозначим через Х' и У', соответственно, множества непомеченных вершин доли Х и помеченных вершин доли У. Положим Я = Х 0 У . Будем считать, что в графе С пет изолированных воршин.

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