Новиков Ф.А. Дискретная математика для программистов (860615), страница 68
Текст из файла (страница 68)
Однако читателю следует иметь в виду, что при решении сложных практических задач,например, из вычислительной геометрии, интуитивных представлений может оказатьсянедостаточно.10.8.2. Эйлерова характеристикаДля графов, уложенных на некоторой поверхности, справедливо определённоесоотношение между числом вершин, рёбер и граней графов, которые укладываются на этой поверхности.362Глава 10.
Циклы, независимость и раскраска(формула Эйлера) Для связного планарного графа справедливо следующее соотношение:ТЕОРЕМАp-q+f =2.ЗАМЕЧАНИЕЧисло в правой части этого соотношения называется эйлеровой характеристикой поверхности.Индукция по q. База: q = 0 =>• р = 1 & / = 1. Пусть теоремаверна для всех графов с q рёбрами: р — q + / = 2. Добавим еще одно ребро.Если добавляемое ребро соединяет существующие вершины, то легко видеть,что q' = q+l,p' =р, / ' = / + 1 ир'-q' + f =p-q-l+ f+l=p-q+ f = 2.
Еслидобавляемое ребро соединяет существующую вершину с повой, то р' — р + 1,q' = q+l, /' = f n p , - q , + f'=p+l-q-l+ r = p-q + f = 2.•ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕ 1Если G — связный планарный граф (р > 3), то q ^ Зр —6.Каждая грань ограничена по крайней мере тремя ребрами, каждое ребро ограничивает не более двух граней, отсюда 3 / ^ 2q. ИмеемДОКАЗАТЕЛЬСТВО2 = P~q + fСЛЕДСТВИЕ 2ГрафыО3p-3q+ 2q^6q^3p-6.•и Кз^ не планарны.ДОКАЗАТЕЛЬСТВО[Kb не планарен] Имеем р = 5, q = 10. Еслипланарен, то по предыдущемуследствию q = р(р - 1 ) / 2 = 1 0 ^ З р - 6 = 3- 5 - 6 = 9 — противоречие.[К3,з не планарен ] Имеем р = 6, q = 9. В этом графе нет треугольников, зиачит,если этот граф планарен, то в его плоской укладке каждая грань ограничена пеменее чем четырьмя ребрами и, следовательно, 4 / ^ 2q или 2 / ^ q.
По формулеЭйлера 6 - 9 + / = 2, откуда / = 5. Имеем 2 / = 2 - 5 = 1 0 ^ д = 9 — противоречие.•ЗАМЕЧАНИЕОперация подразбиения ребра х = (u,v) состоит в замене его двумя рёбрами (u,w) и(w,v), где w — новая вершина. Два графа называются гомеоморфными, если они могутбыть получены из одного графа подразбиением рёбер. Граф планарен тогда и толькотогда, когда он не содержит подграфов, гомеоморфиыхили Кз,з- Доказательстводостаточности этого утверждения (теоремы Куратовского) выходит за рамки данногокурса.36310.8.
ПланарностьСЛЕДСТВИЕ 3не больше 5.ДОКАЗАТЕЛЬСТВОВ любом планарном графе существует вершина, степень которойОТпротивиого. Пусть Vv е V (d(v) > 6). Тогдаv€Vно q < Зр - 6. Имеем: Зр < Зр - 6 — противоречие.•ОТСТУПЛЕНИЕДля случая многогранников формулу Эйлера вывел Декарт. Действительно, каркас многогранника — это плоский граф, и обратно, связному плоскому графу соответствует многогранник.10.8.3.
Теорема о пяти краскахТЕОРЕМАВсякий планарный граф можно раскрасить пятью красками.ДОКАЗАТЕЛЬСТВОДостаточно рассматривать связные графы, потому чтоИндукция по р. База: если р ^ 5, то х < р < 5. Пусть теорема верна для всех связных планарных графов с р вершинами. Рассмотрим граф G с р + 1 вершинами.По третьему следствию к формуле Эйлера Зг; е V (d(v) ^ 5). По индукционному предположению x(G - v) ^ 5. Нужно раскрасить вершину v. Если d(v) < 5,то в 5-раскраске графа G — v существует цвет, свободный для вершины v. Если d(v) = 5 и для Г+(г>) использованы не все пять цветов, то в 5-раскраскеграфа G — v существует цвет, свободный для вершины v.
Остался случай, когда d(v) = 5 и все пять цветов использованы (вершина Vi покрашена в цвет г,рис. 10.9). Пусть G13 — правильный подграф графа G — v, порожденный всемивершинами, покрашенными в цвета 1 или 3 в 5-раскраске графа G — v. Если v\ иг>з принадлежат разным компонентам связности графа G13, то в той компоненте, в которой находится вершина v\, произведем перекраску 1 « 3. При этомполучится 5-раскраска графа G - v, но цвет 1 будет свободен для вершины v.В противном случае существует простая цепь, соединяющая vi и г>з и состоящая из вершин, покрашенных в цвета 1 и 3.
Тогда вершины v2 и v4 принадлежатразным компонентам связности подграфа G24 (так как граф G — планарный).Перекрасим вершины 2 н 4 в той компоненте связности графа G24, которойпринадлежит v2, и получим 5-раскраску графа G — v, в которой цвет 2 свободендля вершины v.•364Глава 10. Циклы, независимость и раскраскаРис. 10.9. К доказательству теоремы о пяти краскахКомментарииИз вопросов, рассмотренных в этой главе, в литературе наибольшее вниманиеуделено задаче коммивояжёра. Анализ различных подходов к её решению см.,например, в [21]. Алгоритм 10.1 описан в [8], в других источниках (например,в [5]) можно найти другие варианты решения этой задачи.Обсуждение переборных задач в этой главе носит в основном ознакомительный характер. Для получения более точной и детальной информации следуетобратиться к специальной литературе, прежде всего к фундаментальной книге [19].
Алгоритм построения максимальных независимых множеств заимствованиз [21]. Здесь этот алгоритм использован в качестве примера для иллюстрацииспособов и особенностей решения переборных задач.Центральный результат этой главы — теорема о пяти красках — изложен покниге [28]. Алгоритмы раскрашивания изложены по книге [21], в которой можно пайти их более детальное и подробное обсуждение. Различные применениязадачи о раскраске графов в программировании и смежные вопросы освещеныв [20].Упражнения10.1. Доказать, что кодерево связного графа является максимальным подграфом,не содержащим коциклов.10.2.
Доказать, что эйлеров граф пе имеет мостов.10.3. Доказать, что если в связном графе G(V,E) Vw ф v е V (d(u) + d(v) ^ р),то граф G гамильтонов.10.4. Доказать, что ао ^ Pi,ai ^ Ро10.5. Написать алгоритм построения всех клик графа.10.6. Доказать или опровергнуть следующее утверждение: наименьшее доминирующее множество является ядром.10.7. Доказать, что X(G(V,B)) ^ 1 + max &(G'(V',Е')).10.8. Доказать, что если в планарном графе каждая грань есть Сп, тоqп(р - 2)п—2Указатель основных обозначенийМетаобозначенияОбозначениеСмыслDefПо определению есть 1|0|1 =Def0„с: =(а + Ь)/2Положим равным1 = 1,2 х 2 = 4Равно: ==ПримерЧисловые множестваОбозначениеNZQRПримерыНазваниеНатуральные числа1,2,30,1,-1,2,-2Целые числаРациональные числаf f f ' 718281828Вещественные числа 1,1.5, у/2,7г, еСовокупностиОбозначение{аь ...,ап}( a i , .
. . ,ап){А\ В, С)( a i , . . . ,ап)ПрименениеНеупорядоченное множество различных элементовУпорядоченная последовательностьоднородных элементовУпорядоченная последовательностьразнородных элементовУпорядоченная последовательностьсоставных элементовПримеры{1,2,3}(0,1,0,1)(М;+,*)(а - > 0 1 , 6 - » 10)366Указатель основных обозначенийОперации с множествамиОбозначениеа £ Аа &ААсВAUBАГ\ВА\ВААВАхВ0ПрочтениеПримерыЭлемент а принадлежит1 е {1,2,3}множеству АЭлемент а не принадлежит 4 ^ { 1 , 2 , 3 } , v ^ ^ Qмножеству АМножество А является{2,3} С {1,2,3}подмножеством множестваВОбъединение множеств А и { 1 , 2 } U { 2 , 3 } = { 1 , 2 , 3 }ВПересечение множеств А и { 1 , 2 } П { 2 , 3 } = { 2 }ВРазность множеств А и В{ 1 , 2 } \ { 2 , 3 } = {1}Симметрическая разность{1,2} Д {2,3} = {1,3}множеств А и ВПрямое произведение{1,2} х {2,3} =множеств А и В= { ( 1 , 2 ) , ( 1 , 3 ) , (2, 2), ( 2 , 3 ) }{}Пустое множествоМощность множества А|{1,2}| = 2Логические обозначенияОбозначение-пРР VQР hQP=*QVx (Р(х))Зх (Р(х))НазваниеОтрицаниеДизъюнкцияКонъюнкцияИмпликацияКвантор всеобщностиКвантор существованияПрочтениеНе РР или QРидЕсли Р, то QДля всех х выполнено Р(х)Существует х,такой, что выполнено Р(х)ОтношенияОбозначениеR оSRnR-<<НазваниеКомпозиция отношенийСтепень отношенияМатрица отношенияОтношение эквивалентностиОтношение порядкаОтношение строгого линейного порядкаОтношение нестрогого линейного порядка367Групповые операцииФункцииОбозначение/:А^ВЪ = /(а)f °9Г1Dom /Im/ПрочтениеФункция / из А в ВЬ является значением функции / для аргумента аСуперпозиция функций / и9Обратная функция к /Множество определенияфункцииf:A—*BМножество значенийфункции / : А —> ВПримечание/ с А х Ва н-> Ь(fog)(x)/ -1:= f(g(x))В ^ АVa £ D o m / (3b Е В (b = f(a)))V f e e l m / (За е А (Ъ = f (а)))Групповые операцииОбозначениепЕг=1aiтгП aiг=1m i n ( a i , .
. . , ап)m a x ( a i , . . . , ап)ПрочтениеПримечаниеСумма элементов с ц , . . . , апЕтгг=1йг= ai + . . . + a nтгПроизведение элементовп ai = а\ х • • • х апi=ia i , . . . , апМинимальный из элеменmin(a, b) ^ а к min(a, b) ^ bтов а\,... ,апМаксимальный из элеменmax(a, b) ^ a к max(a, b) ^ bтов ец,... , a nСписок литературы1. АхоА., Ульман Дж. Теория синтаксического анализа, перевода икомпиляции. Мир, 1978.2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительныхалгоритмов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
