Дискретная математика (998286), страница 50
Текст из файла (страница 50)
11.1. Связь различных задач 2. ЗНП можно сформулировать как задачу линейного программирования: р ппп т ох; при ограничениях р ',У Ваху ) 1 (1 = 1,..., р), где 1и = если Е; Е Е', в противном случае, с;>О, если о; ЕЕ,ч в противном случае. 3. Дана булева матрица Т: аттау ~1..р,1..р] оГ 0..1. Каждому столбцу приписан вес с,. Найти такое множество столбцов минимальной стоимости, чтобы любая строка содержала единицу хотя бы в одном из выбранных столбцов. 11.3.5. Связь ЗНП с другими задачами Известно, что ЗНП относится к числу трудоемких задач, и для ее решения при- меняются переборные алгоритмы с теми или иными улучшениями. На рис.
11.1 приведена схема (см. [1Ц), показывиошая связь ЗНП и некоторых других задач. На этой схеме стрелка от задачи А к задаче В означает, что решение задачи А влечет за собой решение задачи В. 280 Глава 11. Независимость и покрытия Комментарии Обсуждение переборных задач в этой главе носит в основном ознакомительный характер. Для получения более точной и детальной информации следует обратиться к специальной литературе, прежде всего к фундаментальной книге 1Ф]. Алгоритм построения максимальных независимых множеств заимствован из ]11].
3десь этот алгоритм использован прежде всего в качестве примера для иллюстрации способов и особенностей решения переборных задач. Упражнения 11.1. Доказать, что тто ) Дт, стт ) До 11.2, Написать алгоритм построения всех клик графа. 11.3. Доказать, что наименьшее доминирующее множество является независимым. ГЛАВА 12 Раскраска графов Задача раскрашивания графов, которая на первый взгляд кажется просто праздной головоломкой, имеет неожиданно широкое применение в программировании, особенно при решении фундаментальных теоретических проблем (см., напри- меР, 171).
12.1. Хроматическое число Способ явного выражения хроматического числа через другие инварианты графа неизвестен. Известны только некоторые оценки, часть из которых приведена в данном разделе. Раскраской графа называется такое приписывание цветов (натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет. Наименьшее возможное число цветов в раскраске называется ароматическим числом и обозначается Х(С). Очевидно, что сушествует гп-раскраска графа С для любого гп в диапазоне Х(С) < гп < р. Множество вершин, покрашенных в один цвет, называется одноиветляым классом. Одноцветные классы образуют независимые множества вершин, то есть никакие дае вершины в одноцветном классе не смежны. Пример ХЖе) =1~ Х(~р) =р~ ХЯ~~,~) = 2, Х(Сз,~) = 2, Х(Са„+1) = 3, Х(У) = 2, где Т вЂ” свободное дерево. ТЕОРЕМА Х(С) ~< 1+ Ь(С).
Доказатапьство Индукция по р. База: р = 1 =ь Х(С) = 18сЬ(С) = О. Пусть т'С р(С) < р => Х(С) < Ь(С)'+ 1. рассмотрим С: р(С) = р. Тогда, если е П Ъ', то Х(С вЂ” е) < Ь(С вЂ” и) + 1 < Ь(С) + 1. Но И(е) < Ь(С), значит, хотя бы 282 Глава 12. Раскраска графов один цвет в г)г(С) + 1 раскраске графа С вЂ” е свободен для е. Покрасив о в этот цвет, имеем Ь(С) + 1 раскраску С. П ТЕОРЕМА р!МС) < Х(С) < р /3о(С) + 1.
Аоказатвпьство 1. Пусть д(С) = п и У = У 13 11 У„, где Уг — одноцветные классы. Ъ;. независимое множество вершин, значит, Щ < Д>(С). Имеем: а Р = ~ ! У'~ < паул(С) ь ИН < Х. гкп 2. Пусть Я С У вЂ” наибольшее независимое множество, 1о1 = Д(С). Тогда 1г(С— Я) < ~У вЂ” Я1 = Р— Д(С). Из и-раскраски С вЂ” Я можно получить (и+ 1)- раскраску С, так как все вершины из Я можно покрасить в один новый цвет. Следовательно, Х(С) < ДС вЂ” Я)+1 <Р-(1о+1. ТЕОРЕМА Пусть д: = 1г(С), д: = д(С). Тогда 2 Ф<Х+Х<Р+1, Р<ХХ< Аоказаткл ь ство 1. Пусть д(С) = и, Уы..., ӄ— одноцветные классы, Р;: = ~Ц. Тогда Р' =Р~ з=1 следовательно пвхр; > Р/и. Но И вЂ” независимые множества в С, следовательно, К вЂ” клики в С. Значит, п Х > пшлрг > Р!».
гва Имеем хуг > п ° р/и = Р. 2. Известно, что среднее геометрическое не превосходит среднего арифметического: о+Ь вЂ” > ~/аЬЬ. 2 Следовательно, г+ т > 2~/х~ > 2 /р. 283 12.2. Планарность 3. Докажем индукцией по р, что х+ х ~ р+ 1, База: р = 1 ~ х = 14с х = 1. Пусть Х+ Х < р для всех графов с р — 1 вершинами. Рассмотрим граф а с р вершинами и вершину о е Ъ'. Тогда, очевидно, Х(а) <Х(С вЂ” о)+1~ ХФ) ~Х(а-о)+1.
если х(с) < х(с — о) +1~/х(с) < х(с — е) +1, то Х + Х = Х(а) + Х(а) < Х(а — о) + 1 + Х(а — и) + 1 < р+ 2, Следовательно, Х+ Х < р+ 1. Пусть теперь Х(а) = Х(а-о)+14 Х(а) = Х(а-о)+1 Положим д: = о(о) в графе С, тогда д = р — д — 1 — степень е в графе С. Имеем Ы > Х(С вЂ” о). Действительно, Х(С) = Х(С вЂ” о) + 1 и, если бы д < Х(С вЂ” о), то вершину о можно было бы раскрасить в любой из свободных Х(С вЂ” о) — д цветов и получить х(С вЂ” о)-раскраску графа С. Аналогично, д = р — д — 1 > Х(С вЂ” о). Таким образом, х+х=х(а)+х(а) = = Х(а — о) + 1 + Х(а — ) + 1 > о + 1+ р — о — 1 + 1 = р + 1. 4. Имеем 2 „/хх < х+ х < р+ 1.
Следовательно, ( — ) > хх. +1 2 12.2. Планарность Обсуждение плаиариости в этом разделе позволяет решить вторую историческую задачу из перечисленных в подразделе 7.1.1, а также подготавливает результаты, необходимые для доказательства теоремы о пяти красках. 12.2.1. Укладка графов Граф укладывается па некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы ребра графа при этом ие пересекались. Граф называется нланарным, если его можно уложить иа плоскости.
Плоский граф — это граф, уже уложенный на плоскости. Область, ограниченная ребрами в плоском графе, и ие содержащая внутри себя вершин и ребер, называется гранью. Число граней плоского графа С обозначается г(С). ЗАМЕЧАНИЕ Вне|инни часть плоскости также образует грань. Пример На рис. 12.1 показаны диаграммы плаиариого графа К4 и его укладки на плоскости. Этот граф имеет 4 грани. Глава 12. раскраска графов 284 рис. 12.1.
Планарный граф и вго укладка 12.2.2. Эйлерова характеристика Для графов, уложенных на некоторой поверхности, справедливо определенное соотношение между числом вершин, ребер и граней. Это соотношение называется зйлеровой харакгперистикой поверхности. ТЕОРЕМА (формула Эйлера) В связном планарном графе справедливо следующее: р — о+т=2. Доказательство Индукция по 9. База: д = 0 =ь р = 18гт = 1. Пусть теорема верна для всех графов с д ребрами: р — д+ т = 2.
Добавим еще одно ребро. Если добавляемое ребро соединяет существующие вершины, то д' = д + 1, р' р, т' = т + 1 и р — д +т~ = р — о — 1+ т+ 1 = р — е+ т = 2. Если добавляемое ребро соединяет существующую вершину с новой, то р' = р+ 1, д' = 9+ 1, т' = т и р' — д'+ т' = =р+1 — д — 1+г =р — г)+т=2 П СЛЕДСТВИЕ Если С вЂ” связный планарный граф (р > 3), то д < Зр — 6. Доказательство Каждая грань ограничена по крайней мере тремя ребрами, каждое ребро ограничивает не более двух граней, отсюда Зт < 29.
Имеем 2 = Р— д + т < Р— д+ — =ь ЗР— 39+ 2д > 6 =ь д < ЗР— 6. 29 П СЛЕДСТВИЕ Кв и Кв в непланарны. Доказательство 1. Рассмотрим Кв. Имеем р = 5, д = 10. Если Кв планарен, то по предыдущему следствию д = р(р — 1)/2 = 10 < Зр — 6 = 3 5 — 6 = 9 — противоречие. 2 Рассмотрим Квл. Имеем р = 6, д = 9.
В этом графе нет треугольников, значит, если этот граф планарен, то в его плоской укладке каждая грань ограничена не менее чем четырьмя ребрами и, следовательно, 4т < 29 или 2т < 9. По формуле Эйлера 6 — 9 + т = 2, откуда т = 5. Имеем 2т = 2 5 = 10 < у = 9— противоречие. П 12.2. Планарность ЗАМЕЧАНИЕ Граф планарен тогда н только тогда, когда он не содержит а качестве подграфов нн Кэ, нн Кэ,э.
Доказательство достаточности этого утверждения выходит эа рамки данного курса. СЛЕДСТВИЕ В любом плаиарном графе существует вершина, степень которой ие больше 5. Доказатальство От противного. Пусть Уо Е г' й(о) > 6. Тогда бр< ~ й(о) =2д=эЗр< о, ьеи но д < Зр — 6. Имеем: Зр < Зр — 6, противоречие. ОТСТУПЛЕНИЕ Эйлер вывел свою формулу, исследуя многогранники. Действительно, развертка многогранника — это плоский граф, и обратно, связному плоскому графу соответствует многогранник. Таким образом, теория графов имеет связи с самыми разными, на первый взгляд далекими, областями знания.
12.2.3. Теорема о пяти красках ТЕОРЕМА Всякий плаиариый граф можно раскрасить пятью красками. Докэзатальство Достаточно рассматривать связные графы, потому что Х(0 С') шах Х(Сг). а=1 Индукция по р. База: если р < 5, то х < р < 5. Пусть теорема верна для всех связных планарных графов с р вершинами. Рассмотрим граф С с р+ 1 вершиной. По третьему следствию к формуле Эйлера Эо Е 1г й(о) < 5. По индукционному предположению Х(С вЂ” о) < 5. Нужно раскрасить вершину о. 1. Если й(о) < 5, то в 5-раскраске С вЂ” о существует цвет, свободный для о.
2. Если й(о) = 5 и для Г+(о) использованы не все,пять цветов, то в 5-раскраске С вЂ” о существует цвет, свободный для ж 3. Остался случай, когда й(о) = 5 и все пять цветов использованы (вершина щ покрашена в цвет А рис. 12.2). Пусть Сгэ — правильный подграф С вЂ” т порожденный всеми вершинами, покрашенными в цвета 1 или 3 в 5-раскраске графа С вЂ” е. Если ог и оэ принадлежат разным компонентам связности графа Сгэ, то в той компоненте, в которой находится оп произведем перекраску 286 Глава 12.
Раскраска графов 1 ~-~ 3. При этом получится 5-раскраска С вЂ” о, но цвет 1 будет свободен для, р,! В противном случае существует простая цепь, соединяющая от и оз и состоя-' щая из вершин, покрашенных в цвета 1 и 3. В этом случае оз и о4 принадлежат разным компонентам связности подграфа Сзз (так как граф С вЂ” планарный).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
