Дискретная математика (998286), страница 48
Текст из файла (страница 48)
Таким образом, задача отыскания гамильтонова цикла или эквивалентная аадача коммивояжера являются практически востребованными, ио для них неизвестен (и, скорее всего, не существует) эффективный алгоритм решения. Комментарии Из вопросов, рассмотренных в этой главе, наибольшее внимание в литературе уделено задаче коммивояжера.
Анализ различных подходов к ее решению см., например, в !11]. Алгоритм 10.1 описан в [14), в других источниках (например в (6)) можно найти другие варианты решения этой задачи. Упражнения 10.1. Доказать, что кодерево связного графа является максимальным подграфом, не содержащим коциклов. 10.2. Доказать, что эйлеров граф не имеет мостов. 10лй доказать, что если в связном графе С()г, Е) т'и,е е Ъ' г!(и) + о(п) > р, то граф С гамильтонов. ГЛАВА 11 Независимость и покрытия В этой главе рассматриваются некоторые известные задачи теории графов н указываются связи между ними. Особое внимание уделяется обсуждению методов решения переборных задач на примере задачи отыскания максимального независимого множества вершин.
11.1. Независимые и покрывающие множества Прежде всего введем определения и рассмотрим основные свойства независимых и покрывающих множеств вершин и ребер. Эти определения и свойства используются в последующих разделах. 11.1.1. Покрывающие множества вершин и ребер Говорят, что вершина покрывает инцидентные ей ребра, а ребро покрывает ннцидентные ему вершины. Множество таких вершин, которые покрывают все ребра, называется вершинным покрытием. Наименьшее число вершин во всех вершинных покрытиях называется числом вершинного покрывшя и обозначается ао.
Пример 1. Для полного графа ао(Кр) = р — 1. 2. Для полного двудольного графа ао(К„, „') = пнп(пг, и). 3. Для вполне несвязного графа ао(Кр) = О. 4. Для несвязного графа ао(% сг Оз) = ао(Ст) + ао(Сз). Множество таких ребер, которые покрывают все вершины, называется рвбврным покрытием. Наименьшее число ребер во всех реберных покрытиях называется числом реберного покрытия и обозначается ап 270 Глава 11. Независимость и покрытия ЗАМЕЧАНИЕ Для графа с изолированными вершинами ат ве определено. Пример 1. Для четного цикла ат(Кз„) = и, для нечетного цикла ат(Кз„+т) = п + 1. 2. Для полного графа с четным числом вершин ат(Кз„) = и, для полного графа с нечетным числом вершин ат(Кг„+т) = п+ 1.
3. Для полного двудольного графа аг(К,„) = шах(тп, п). 11.1.2. Независимые множества вершин и ребер Множество вершин называется независимым, если никакие две из ннх не смежны. Наибольшее число вершин в независимом множестве вершин называется вершинным числом независимости и обозначается Дг. Пример 1. Для полного графа 4,(Кр) = 1. 2. Для полного двудолфгого графа Д(К,„) = шах(пт, и).
3. Для вполне несвязного графа До(Кр) = р. 4. Для несвязного графа До(Сг г~ Сз) = До(Ст) + )1о(Сг). Множество ребер называется независимым, если никакие два из них не смежны. Наибольшее число ребер в независимом множестве ребер называется рвбврным числом независимости и обозначается юг. ЗАМЕЧАНИЕ Независимое множество ребер называется также ларосочетанием. Пример 1. Для четного цикла Дт(Кз„) = п, для нечетного цикла (1т(Кг„+т) = и — 1.
2. Для полного графа с четным числом вершин от(Кз„) = п, для полного графа с нечетным числом вершин ~3т(Къ+к) = и — 1 3. Для полного двудольного графа )гт(К „) = ппп(т,о). 11.1.3. Связь чисел независимости и покрытий Приведенные примеры наводят на мысль, что числа независимости и покрытия связаны друг с другом н с количеством вершин р. ТЕОРЕМА Дая любого нетривиального связного игафа ао + 1то = р = ат + Рг 11.1.
Независимые и покрываюнвзе множества Доказдтвльст во Покажем, что имеют место четыре неравенства, из которых следуют два требуе- мых равенства. Пусть Мо — наименьшее вершинное покрытие, то есть !Мо! = ао, Рассмотрим Ъ''гМо. Тогда Ъ''1Мо — независимое множество, так как если бы в множестве У'гМо были смежные вершины, то Мо не было бы покрытием.
Имеем !У '1 Мо! < ~уо, следовательно, сго+гуо ~ р: р = !Мо!+ !У'г Мо! < ос+ де Пусть )то — наибольшее независимое множество вершин, то есть !)то! = 4>. Рассмотрим У'1 Жо. Тогда У |, Же — вершинное покрытие, так как нет ребер, инцндентных только вершинам из Мо, стало быть, любое ребро иицидентио вершине (или вершинам) из Ъ''1Мо. Имеем !У 1 ззо! 1 гго, следовательно, р = !йГо! + !У '1 )зо! 1 гуо+ его.
Пусть Мг — наименьшее реберное покрытие, то есть !Мг! = ггг. Множество Мг не содержит цепей длиной больше 2. Действительно, если бы в Мг была цепь длиной 3, то среднее ребро этой цепи можно было бы удалить из Мг и это множество все равно осталось бы покрытием. Следовательно, М, состоит из эвезд. (Звездой называется граф, диаметр которого ие превосходит двух, Р(С) < 2.) Пусть этих звезд пг. Имеем !М,! = 2, по где пг — число ребер в з-й звезде.
Заметим, что звезда из и; ребер покрывает и;+1 верши- иУ. Имеем: Р = 2 ',. „(пг + 1) = гп+ 2„,ыг и; = т+ !Мг !. Возьмем по одному ребру из каждой звезды и составим из них множество Х. Тогда !Х! = пз, множество Х вЂ” независимое, то есть !Х! < А. Следовательно, р = !Мг! + пг = !М,! + !Х! < ггг + 1зг. Пусть № — наибольшее независимое множество ребер, то есть !№! = гуг. Построим реберное покрытие У следующим образом. Множества № покрывает 2!№! вершин. Добавим по одному ребру, иицидеитному непокрытым р — 2!№! вершинам, таких ребер р — 2!М~ !. Тогда множество 1 — реберное покрытие, то есть !У! < сгз и !У! = !гтг!+р — 2!№! = р — !№!. Имеем: р= р — !№!+ !№! = !У!+ !р~т! > ггг+ А.
С) его + гЧо < р: ггг+ 1тг ~ ~Р: оз+А <Р: ЗАМЕЧАНИЕ Условия связности и нетривиальности гарантируют, что все четыре инварианта определе- ны. Однако зто условие является достаточным, но не является необходимым. Например для графа К гз К заключение теоремы остается справедливым, хотя условие не выпол- нено. 272 Глава 11. Неэавиоимость и покрытия Отступление Задача отыскания экстремальных независимых и покрывающих множеств возникает во многих практических случаях. Например, пусть есть множество процессов, использующих верээделяемые ресурсы. Соединим ребрами вершины, соответствующие процессам, которым требуется один и тот же ресурс. Тогда Д будет определять количество возможных параллельных процессов.
11.2. Построение независимых множеств вершин Данный раздел фактически является вводным обзором методов решения переборных задач. Методы рассматривакттся на примере задачи отыскания максимального независимого множества вершин графа. Данный обзор не претендует на полноту, но описание основополагающих идей и терминов в нем присутствует. 11.2.1. Постановка задачи отыскания наибольшего независимого множества вершин Задача отыскания наибольшего независимого множества вершин (и, тем самым, определения вершинного числа независимости )то) принадлежит к числу трудоемких. Эту задачу можно поставить следующим образом.
Пусть задан граф С()т, Е), Найти такое множество вершин Х, Х с 'к', что щ(Х) = шахе(У), уев где щ(Х): = ~Х~, а Я: = (У с Ъ' ) Ч и о б У (и о) к Е) (см. раздел 27 5). Если бы семейство Я независимых множеств оказалось матроидом, то поставленную задачу можно было бы решить жадным алгоритмом (алгоритм 2.2). Однако семейство Я матроидом не является. Действительно, хотя аксиомы М, и Мэ (см. подраздел 2.7.1) выполнены, так как пустое множество вершин независимо и всякое подмножество независимого множества независимо, но аксиома Мэ не выполнена, как видно из следующего примера. Пример Рассмотрим полный двудольный граф К„„+т.
Доли этого графа образуют (максимальные) независимые множества, и их мощности различаются на 1. Однако никакая вершина из большей доли не может быть добавлена к вершинам меньшей доли с сохранением независимости. 273 11.2. Построение независимых множеств вершин 11.2.2. Поиск с возвратами Даже если для решения задач, подобных поставленной в предыдушем разделе, не удается найти эффективного алгоритма, всегда остается возможность найти решение «полным перебором» всех возможных вариантов, просто в силу конечности числа возможностей. Например, наибольшее независимое множество можно найти по следующей схеме. Вход: граф С(У, Е). Выход: наибольшее независимое множество Х.
и»: = 0 ( наилучшее известное значение 13с ) ГогУб2 до Е У б б ьг Щ > т гйеп т;= Щ;Х: = У ( наилучшее известное значение Х ) епг) 1( епй гог ЗАМЕЧАНИЕ Для выполнения этого алгоритма потребуется О(2») шагов. ОТСТУПЛЕНИЕ Алгоритм, трудоемкость которого (число шагов) ограничена полииомом от характерного размера задачи, принято называть эффеюнпеныи„в противоположность неэффекглиенын алгоритмам, трудоемкость которых ограничена более быстро растушей функцией, например экспонентой.
Таким образом, жадный алгоритм эффективен, э полный перебор — нет. При решении переборных задач большое значение имеет способ организации перебора (в нашем случае — способ построения и последовательность перечисления множеств У). Наиболее популярным является следующий способ организации перебора, основанный на идее поиска в глубину и называемый поиском с возврашпмн. ЗАМЕЧАНИЕ Иногда употребляется термин бэкшрекинг (от английского названия этого метода— Ьас)гтгасЫпй).
Идея поиска с возвратами состоит в следующем. Находясь в некоторой ситуации, пробуем изменить ее в надежде найти решение. Если изменение не привело к успеху то возвра1цаемся в исходную ситуацию (отсюда название «поиск с возвратами») и пробуем изменить ее другим образом, и так до тех пор, пока не будут исчерпаны все возможности. для рассматриваемой задачи метод поиска с возвратами может быть реализован с помощью следующего рекурсивного алгоритма. 274 Глава 11.
Независимость и покрытия дпгоритм 11.1. Поиск с возвратами Вход: граф С(КЕ). Выход: наибольшее независимое множество Х. пз: = О ( наилучшее известное значение ~Зе ) ВТ(и, и) ( вызов рекурсивной процедуры ВТ ) Основная работа выполняется рекурсивной процедурой ВТ.
Вход: Я вЂ” текущее независимое множество вершин, Т вЂ” оставшиеся вершины графа. Выход: изменение глобальной переменной Х, если текущее множество ие может быть расширено (является максимальным). е: = Га!зе ( признак расширяемости множества ) Гог е е тг оо 1Г Я 0 (е) е б 1Ьеп е: = тгне ( множество можно расширить ) ВТ(Я0 (и),Т 1Г'(е)) ( пробуем добавить е ) епб ГЕ епд Гог 1Е е Г)1еп )Е Д > гп гпеп Х:= Я; гп:= ф( ( наибольшее независимое множество ) епб 1Г епг) )Е ОБОСНОВАНИЕ По построению вершина о добавляется в множество Я только при сохранении независимости расширенного множества. В алгоритме это обстоятельство указано в форме условия Я О (о) б Я. Проверить сохранение условия независимости нетрудно, например, с помощью следующего цикла. Г: = ггпе ( множество Я независимое ) Гоги е Я Йо )Е (и,е) Е Я 1)гоп Г: = Га)зе; еюг Еог ( множество Я 0 (и) зависимое ) епг) ')Е епб Еог Этот цикл не включен в явном виде в рекурсивную процедуру ВТ, чтобы не загромождать основной текст и не затуманивать основную идею поиска с возвратами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
