Новиков Ф.А. Дискретная математика для программистов (860615), страница 65
Текст из файла (страница 65)
aci(Km<n) = max(m,n), если Кт<п — полный двудольный граф.10.4.2. Независимые множества вершин и рёберМножество вершин называется независимым (или внутренне устойчивым), еслиникакие две из них не смежны. Наибольшее число вершин в независимом множестве вершин называется вершинным числом независимости и обозначается fa.Примеры1. Ро(Кр) = 1, если Кр — полный граф .2.
/Зо(Кт,п) = тах(ш, п) , если К т у п ~ полный двудольный граф.3. j30(Kp) = р, если Кр — вполне несвязный граф.4. Po(G\ UG2) = 0o(G\) + /3o(C?2), если G\ и G2 — компоненты несвязного графа.Ясно, что множество вершин S является независимым тогда и только тогда, когдаVves{r(v)ns= 0).Множество рёбер называется независимым (или паросочетанием), если никакиедва из них не смежны. Наибольшее число рёбер в независимом множестве рёберназывается рёберным числом независимости и обозначается (3\.Примеры1.
(3i(C2n) = п, если С2п — чётный цикл.2. (3i(C2n+\) =72 — 1, если С2п+1 — нечётный цикл.3. (3i(K2n) = 72, если К2п — полный граф с чётным числом вершин.4. f3\{K 2n+ \) = п, если К 2 п +1 — полный граф с нечётным числом вершин.5. (3i(Km>n) = min(m,n), если Кт,п — полный двудольный граф.10.4. Независимые и покрывающие множества347ЗАМЕЧАНИЕ;Индексы 0 и 1 в обозначениях ао, ai, /Зо, fli выбраны из следующих мнемонических соображений.
Индекс 0 соответствует вершинам, так как вершина нульмерна, а 1 — рёбрам,так как ребро одномерно.10.4.3. Связь чисел независимости и покрытийПриведённые примеры наводят на мысль, что числа независимости и покрытиясвязаны друг с другом и с количеством вершин р.ТЕОРЕМАДля любого нетривиального связного графа«о + А» = р = (У i + (h.ДОКАЗАТЕЛЬСТВОДокажем четыре неравенства, из которых следуют два требуе-мых равенства.[ ао + /Зо ^ р ] Пусть М0 — наименьшее вершинное покрытие, то есть |Мо| = о^.Рассмотрим V \ Mq. Тогда V \ Mq — независимое множество, так как если быв множестве V \ Мо были смежные вершины, то Mq не было бы покрытием.Имеем \V \ М 0 | ^ /30, следовательно, р = |М 0 | + \V \ М 0 | ^ «о + Аь[ а 0 + /Зо ^ р ] Пусть N0 — наибольшее независимое множество вершин, то есть\N0\ = А)- Рассмотрим V \ No. Тогда V \ No — вершинное покрытие, так какнет рёбер, инцидентных только вершинам из N0, стало быть, любое ребро инцидентно вершине (или вершинам) из V \ N0.
Имеем \V \ iV0| ^ ао. следовательно,p=\No\ + \V\No\>(30 + а0.[ ai + /3i ^ р] Пусть Mi — наименьшее рёберное покрытие, то есть \М\\ = а ьМножество Mi не содержит цепей длиной больше 2. Действительно, если быв Mi была цепь длиной 3, то среднее ребро этой цепи можно было бы удалитьиз Mi и это множество все равно осталось бы покрытием.
Следовательно, Miсостоит из звёзд. (Звездой называется граф, диаметр которого не превосходитдвух, D(G) < 2, и имеется одна центральная вершина, смежная с остальными,а остальные не смежны между собой. Другими словами, звезда — это полныйдвудольный граф К\, п .) Пусть этих звёзд т. Имеем |Mi| = YlT=\ n ^ г д е n i ~число рёбер в г-й звезде. Заметим, что звезда из щ рёбер покрывает щ + l вершину.Имеем: р = YaL\+ 1 ) = т + YhLi ni = га + |Mi |. Возьмём по одному ребру изкаждой звезды и составим из них множество X.
Тогда \Х\ = га, множество X —независимое, то есть \Х\ ^ /?ь Следовательно, р = \М\\ + га = |Mi| + |X| ^ а\+(3\.[ ах + (Зх ^ р ] Пусть N\ — наибольшее независимое множество рёбер, то есть|7Vi| = Pi. Построим рёберное покрытие Y следующим образом. Множество N\покрывает 2|iVi| вершин. Добавим по одному ребру, инцидентному непокрытым р - 2|7Vi| вершинам, таких рёбер р - 2\Ni\. Тогда множество Y — рёберное покрытие, то есть \Y\ ^ a i и \Y\ = |JVi| + р - 2|7Vi| = р Имеем:P = P~\N1\ + \N1\ = |r| + |7Vi|+/?i.•348Глава 10.
Циклы, независимость и раскраскаЗАМЕЧАНИЕУсловия связности и нетривиальное™ гарантируют, что все четыре инварианта определены. Хотя это условие является достаточным, оно не является необходимым. Например, для графа КП U КП заключение теоремы остается справедливым, хотя условие невыполнено.ОТСТУПЛЕНИЕЗадача отыскания экстремальных независимых и покрывающих множеств возникает вомногих практических случаях.
Например, пусть дано множество процессов, использующих неразделяемые ресурсы. Соединим рёбрами вершины, соответствующие процессам,которым требуется один и тот же ресурс. Тогда /Зо будет определять количество возможных параллельных процессов.10.5. Построение независимых множестввершинЭтот раздел, фактически, является вводным обзором методов решения переборпых задач. Методы рассматриваются на примере задачи отыскания максимального независимого множества вершин графа. Наш обзор пе претендует па полноту,по описание основополагающих идей и терминов в нём присутствует.10.5.1. Постановка задачи отыскания наибольшегонезависимого множества вершинЗадача отыскания наибольшего независимого множества вершин (и тем самымопределения вершинного числа независимости /30) принадлежит к числу трудоёмких.Эту задачу можно поставить следующим образом. Пусть задай графНайти такое множество вершин X, X с V, чтоG(V,E).w(X)— max w(Y),v'YeEгде w(Y)=f \Y|, a £ =f {Y с V | Vu, v G У ((и, v) £ E)} (см.
2.6.4).Если бы семейство £ независимых множеств оказалось матроидом, то поставленную задачу можно было бы решить жадным алгоритмом (алгоритм 2.2). Однакосемейство £ матроидом не является. Действительно, хотя аксиомы Mi и М2(см. 2.6.1) выполнены, так как пустое множество вершин независимо и всякоеподмножество независимого множества независимо, но аксиома Мз не выполнена, как видно из следующего примера.Пример Рассмотрим полный двудольный граф К п , п + 1.
Доли этого графа образуют (максимальные) независимые множества, и их мощности различаются на 1.Однако никакая вершина из большей доли не может быть добавлена к вершинамменьшей доли с сохранением независимости.10.5. Построение независимых множеств вершин34910.5.2. Поиск с возвратамиДаже если для решения задач, подобных поставленной в предыдущем подразделе,пе удаётся найти эффективного алгоритма, остаётся возможность попробоватьнайти решение «полным перебором» всех возможных вариантов, просто в силуконечности числа возможностей. Например, наибольшее независимое множествоможно найти по следующей схеме.Вход: графG(V,E).Выход: наибольшее независимое множество X.тп: = 0 { наилучшее известное значение Д) }for У е 2V doif У е £ & |У| > тп thenт .— |У |; X : — Y { наилучшее известное значение X }end ifend forЗАМЕЧАНИЕДля выполнения этого алгоритма потребуется 0(2 Р ) шагов.ОТСТУПЛЕНИЕАлгоритм, трудоёмкость которого (число шагов) ограничена полиномом от характерногоразмера задачи, принято называть эффективным, в противоположность неэффективнымалгоритмам, трудоёмкость которых ограничена функцией, растущей быстрее, например,экспонеитой.
Таким образом, жадный алгоритм эффективен, а полный перебор — пет.При решении переборных задач большое значение имеет способ организацииперебора (в нашем случае — способ построения и последовательность перечисления множеств У). Наиболее популярным является следующий способ организации перебора, основанный на идее поиска в глубину и называемый поиском свозвратами.ЗАМЕЧАНИЕИногда употребляется термин бэктрекинг (транслитерация английского названия этогометода — backtracking).Идея поиска с возвратами состоит в следующем. Находясь в некоторой ситуации, пробуем изменить её допустимым образом в надежде найти решение. Еслиизменение не привело к успеху, то возвращаемся в исходную ситуацию (отсюданазвание «поиск с возвратами») и пробуем изменить её другим образом, и такдо тех пор, пока пе будут перебраны все возможности.Для рассматриваемой задачи отыскания наибольшего независимого множествавершин метод поиска с возвратами может быть реализован с помощью следующего рекурсивного алгоритма.350Глава 10.
Циклы, независимость и раскраскаАлгоритм 10.2 Поиск с возвратамиВход: граф G{V,E).Выход: наибольшее независимое множество X.тп: = 0 { наилучшее известное значение /Зо }X : — 0 { наибольшее известное независимое множество X }B T ( 0 , V) { вызов рекурсивной процедуры ВТ }Основная работа выполняется рекурсивной процедурой ВТ.Вход: S — текущее независимое множество вершин, Т — оставшиеся вершины графа.Выход: изменение глобальной переменной X, если текущее множество не может бытьрасширено (является максимальным),for v € Т doif S + v G £ thenif |S| > m thenX := S\m :={ наибольшее известное независимое множество }end ifBT(S + v,T \ r*(v)) { пробуем добавить v }end ifend forПО построению вершина v добавляется в множество S только присохранении независимости расширенного множества.
В алгоритме это обстоятельство указано в форме условия S + v е £. Проверить сохранение условиянезависимости нетрудно, например, с помощью следующей функции.Вход: независимое множество S и проверяемая вершина v.Выход: true, если множество S + v независимое, false — в противном случае,for и € S doif (и, v) € Е thenreturn false { множество S + v зависимое }end ifend forreturn true { множество S + v независимое }ОБОСНОВАНИЕЭтот цикл не включен в явном виде в рекурсивную процедуру ВТ, чтобы незагромождать основной текст и не затуманивать идею поиска с возвратами.
Таким образом, множество S, а следовательно, и множество X — независимые.В тот момент, когда множество S нельзя расширить, оно максимально по определению. Переменная тп глобальна, поэтому среди всех максимальных независимых множеств в конце работы алгоритма построенное множество X являетсянаибольшим независимым множеством вершин.•10.5.3. Улучшенный переборПрименение метода поиска с возвратами не гарантирует эффективности — трудоёмкость поиска с возвратами имеет тот же порядок, что и другие способыперебора (в худшем случае).10.5. Построение независимых множеств вершин351Используя конкретную информацию о задаче, в некоторых случаях можно существенно сократить трудоёмкость выполнения каждого шага перебора или уменьшить количество перебираемых возможностей в среднем (при сохранении оценки количества шагов в худшем случае).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
