В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 43
Текст из файла (страница 43)
Полученный асевлограф снова обозначаем через 6' [а силу утверждения 4.30 в 6' всс вершины вошла имеют четные степени). Если в 6' отсутствуют ребра, то перетокин к шагу 4 В противном случае зыдеяяем из 6' цикл рсы [см. утверждшше 4.29 о существовании такого цикла) и переходим к шагу 3. Шаг 3. Присваиваем 1: !+1 и переходим к шагу 2. Шаг 4.
Па построению рь .... Рг — циклы, удовлетворяющие .Условию (4.26). Если! 1, то р1 — искомый эйлороз цикл, и нз этом рабата алгоритма заканчивается. В противном случае нз. ходим цикл р, таней, что У(р,)ПУ(р;)чьИ, где 2к!к[ (н силу утверждения 4.31 цикл гс, найдется). Переходим к шагу 5. Шаг 5. Присваиваем 1г ! — 1, рш =В+на Ш: =щы ! й ..., 1, и переходиы к шагу 4. Применим алгоритм 4.5 к задаче выделения эйлерова цикла в самом общем случае, когда 6 = (У, Х) — свизный псевдогра(ь где ХтьИ, степени веРшпн котоРого четны. Удалим из 6 петли В результате получим связный мультиграф 6', степени вершин которого четны. Рассмотрим нетривиальный случай, когда в С' имеется хотя бы одни ребро.
Тогда, примепия к 6' алгоритм 4Д находим эйлеров цикл в 6'. добавляя очевидным образом в этот иикл удаленные петля, получаем эйлеров цикл в 6. Рассмотрим теперь залачу о вылелеинн эйлеровой цели в связном псевдогрзфе 6 = (1т, Х), где ХФИ, пмыошем ровно две вершины с, ю нечетной степени. Добавляя к 6 ребро (а, м) получаем псевдограф С' с четпымн степенями вершин.
Выделке иэ 6' эйлеров цикл н удалив из него ребро (о. ю), поправи эйлерону цепь, соединяющую о, ю. Пример 4.25 [решение задачи о кенигсбергских мостах). Вис' пользуемся теоремой 4.1. Заметим, что для мультиграфа 6. Ши' бражениого на рп*. 422, имеем 6(А) 5, б(В) 3, 5(С)» 5(О) 3, т. е. необходимое н достаточное условие сущестзовзгп"' эц эйлерова цикла не выполняется, а следовательно, мультпграф 6 не обладает эйлеровым циклом. 4.2.9.
Гвмальтоновы цепв м циклы Пусть 6 — псеадаграф. Цепь (цикл] в 6 называется галнльтснааой (ганильгоиоамм), если она (он] проходит через каждую вершнну псевдографа 6 ровно одна раз. С понятном гамнльтомавых циклов тесно связана так назыпаемая задача коммнвояжсра: в нагруженном графе 6 определить гамильтонов цикл мннпмальной длины (ннымн словамн, коммерсант должен совершить поездку по городам н вернуться обратно, побывав в каждом городе ровно одпн раз, я прп этом стонмость такой Тзбзака Гз поездки должна быть чинимальной).
На 'первый взгляд, понятие гамнльтоновэ пнкла скодао с понятием зйлсрова цикла. А межлу тем графы, приведенные п табл. 4.9, гдс столбцы соответствуют случаям существования (столбец 1) н кссьшествованкя (сголбеп 2) гачкльтонавых павлов, а строки — случаям сушестэовання (строка 1) н несушегтвовапня (строка 2] зйлсровых циклов, показывают не.
завнснмость этих понятий. Гамнльтоновы пенн н циклы относятся к числу спецнальньш маршрутов в ~рафах. Очевидно, что Свойство маршрутов аг «проходить через каждую вершину не более одного раза» является латянсним, а следовательно, все гамнльтоповы цепи н циклы псевдографа 6 можно получпть, применяя к 6 мешд латин. ской коапознцнн.
Пусть С является л-вершинным псевдографом. Используя тот очевндный факт, что длнна любой гамнльтоновой аепн равна л — 1, а длина любого гамнльтонова цикла равна л. получаем, что все гвмнльтановы цспп будут перечьслены а непустых элементах матрицы й. ш-п[С), за исключением элементов аа главной диагонали, а все гамнльтоновы циклы — в каждом лнагональном элементе матрацы Едю(6). Однако, как отмечалссь выше, метод латинской композиция в данном случае практнчсскн применим лишь прн достаточно малых л, н поэтому представляет мнтерсс разработка более экономичных методов. Заметим, что (как а в случае сэйлеравымн цеппмннпикланн) было бы нолсзна иметь сравннтельно простые необходимые н достаточные условна существования гамнльтоновых цепей н циклов.
Однако этот вопрос нвляегся весьма сложным и здесь не обсуждается. Вопросы существования и нахождения гаьпшьтоновых цепей и циклов в псевдогрзфах очевшгным образом свалятся к авшю. гичным вопросам дпв графюв, н поэтому в дальнейшем будем говорить щшько а графах. Рассмотрим простой нласс графов, в которых заведомо суще. ешуют гамнльтоновы цепи н циклы. Граф С называется лолльш, если какщая его вершина смежна со всеми остальными вершинамн.
Очевидно, что в полном графе всегда существуют гамнльто. вав цикл, а также гамильтонавы цепи, «оепипяющие две произ. вольные вершины этого графа. Таяны обрезом, простейшим до. счэыщным условием существования гзмнльтоновык цепей и пик. лов в графе является его полнота. Приведем также простейшие необходимме условия. Очевидным яеабходимми угловием суще. ствоеання гамнльтоновых цепей и циклов в графе С являетс» свяэносп С.
Более тонким необходимым условием сушествова. ння гамзльтонова цннла в графе С яиаяешя Утверждение 4.32. Если ероф С обладает «алильтопоееш Мпллолг, то е нем огсугсшуют гочки сочленения Пуси в С имеется точна сочленения о. Йокажем, по О ве мшкет обладать гамильтоновым цекзом. Прелположим против. все, т. е.
что С обладает гамильтоиовым циклом и = ошз ... о„еь где л л(С). Поскольку ог — точка сочленения, то в результат» удаления ог из О получаем граф С' с компонентами свят ности Оь. Сэ, где р,пй. Пусть компоненты свяэкости пронуие. рованы таким образам, что озшО~ (Уь Х,). Замвшм, что но определению гамнльтонова цикла выполняегсе о, чсоь отчьеь ошулл (оз, оз)ауг. а сшдовательно, езауь Апалогиао позу. чаем, что оь ., о шуь а это противоречит тому, что р~2. Приведем некогерые наиболее прошые методы выделения гв. мнльтонавых цепей и циклов в графе С = (У.
Х), где У (оь о ). Покшлуй, самым простым является мегод перебора всевш. можнык перестановок вц, ой, „, ог мяожества У Для кажзгй из ннх проверяем, является ли окой, э, маршрутом в С. Ешш является, то оь еь . ог — гамилгаокова цепь в С. в противмщ случае переходим к следующей перестшювке. Тогда по окончэквв перебора будут выделены все тамнльтоновы пепи в графе С.
Ана. логична для выделения гамильтоновых циклов перебираем всевоз мощные пеРестановки оь огп ..., ог нножесгвв У, ллв квжшй из коюрмх проверяе», является ли ошц ... оц, о, паршрушп в С. Есаи «зляегся, то огог, оц, о~ — гамильтонов цикл в С в противном случае переходим к слелующей перестановке. Тогщ цо окончани» перебора будут выделены все гамильтоновы шпштг в графе С.
Очевидно, что при выделении всех гамильтоиовых пмгей двм придешя перебрать л1 перестановок, а при выделении эсад гвмильтопавых циклов — (л — 1)1 перестановок При этом р эог Заквчи и упражнения !. Испол!луп алгоритм Тэрри, определить замкнутый маршрут в каждом из графов, изображеяяых па рис. 4.34 и 4бб, щю. халящнй ровно два раза (по одному разу в каждом направлении через кажлсе ребро графа. Докззамь чта в сиаьна связном орграфе с симметричной матрипсй смежности существует контур, проковяший по одному разу через каждую лугу орграфх 3. Найти минимальный путь нз иг в иг в орграфах, заданных ма~ридами смсжнастиг 0000310 вача)о) зточлао 00310130 З 00 1010 0010100 ЗЗ,О)лаа Оаалава 2 о! оа оз 0101140 лооолоо гоя)оао 0003100 )оаа)то ОООО!00 10!1031 34 ол:ьа! оооо)по зао)о)о 034 1000 а100130 Г з! 4.
Определить мюгнмвльный путь нз ш в иг в нагруженных срграфзх с заданными матрицами дляв душ 04220 11 11 2 41 а 2 1 1 22 за ! З 1 4 'Е ! 30 4 З 1 З 23 1 1 3 3 1 1 2 1 а З 22 2 2 О 212 1 124 Я 1 1 2 13 1 1 2 2 в 2142 3) 6, Определить путь из иг в и, минимальной длины в лшждом нагруженном арграфе (см. задачу 4) среди путей из аг в иг, со. держащих не более й дуг, гдш а) й 21 б) й 31 в) й 4. шб случае полного графа ни одна из перестановок не акажстсп от бРошенной, т. е.
званый метод язляетгя эффекпюныи для гра«)юв, блнзюш к полным. Отметим, что описанный метод не учить!вше яиформацнн об исследуемом графе б и явлнется кзк бы ориентированным на самый «худши1Ь случай, когда б — полный граф. Рассмотрим мсигд, аиппогичный предыдущему, но испальчукнцнй информацию о С. Охтавнм всевозможные последователь. кости вершин оч, ог„..., а, где иц оиУ. иг, шб(иг,)1(иц), и шб(иь,)ч(ичг,... ио,), б(иь) 3(аь, .
аг,) 33. тшдз в каждом случае, когда г л, последовательность ой о), аг есп гамнльтанава пень в графе б. Оаашлтствеино в каждом случае, когда г = л, ог, шб(о) ), последовательность иг,иг, . иг ой сеть гамильтонов цякл з графе б. При этом будут выделены все гамильтопавы цепи н циклы в графе б. Как и в предылупгем методе при выделешгн гампльтонавьш циило» можно прерпшгэгать, что й- !. 6. Определить, имеются ли в нагруженном орграфе П с за. данной матрицей длин дуг С((3) простые контуры отрицатель. ной длины? Найти пути минимальной ллннм из о, ео все остальные вершины среди путей, содержащнк не более шести дуг. Рассмотрщь случай 6 6 60 2 — 1 З с(п) "--,--".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
