Новиков Ф.А. Дискретная математика для программистов (860615), страница 64
Текст из файла (страница 64)
Заметим, что при342Глава 10. Циклы, независимость и раскраскаэтом мы с необходимостью придём в ту вершину, с которой начали. В противномслучае вершина v имеет нечётную степень, что невозможно по условию. Такимобразом, из графа были удалены рёбра цикла, а вершины цикла были сохраненыв стеке S. Заметим, что при этом степени всех вершин остались чётными. Далее вершина v выводится в качестве первой вершины эйлерова цикла, а процесспродолжается с вершины, стоящей на вершине стека.•10.2.3. Оценка числа эйлеровых графовПусть S (р) — множество всех графов с р вершинами, а £(р) — множество эйлеровых графов с р вершинами.ЗАМЕЧАНИЕВ этом подразделе речь идёт о числе нумерованных графов, то есть о числе графов, вкоторых вершины перенумерованы.
Считается, что если перенумеровать вершины в другом порядке, то это будет другой граф. Очевидно, что нумерованных графов (любоготипа) больше, чем графов, определяемых как классы эквивалентности по отношениюизоморфизма, поэтому приводимые здесь оценки являются достаточно грубыми.ТЕОРЕМАЭйлеровых графов почти нет, то естьм М = 0 .р->оо \3{р)\Пусть £ ' ( Р ) — множество графов с р вершинами и чётными степенями. Тогда по предыдущей теореме £(р) с £'(р) и |£(р)| ^ |£'(P)I- В любомграфе число вершин нечётной степени чётно, следовательно, любой граф из £'(р)можно получить из некоторого графа S(р — 1), если добавить новую вершину исоединить её со всеми старыми вершинами нечётной степени. Следовательно,|£'(P)I ^ IS(p - 1)1- Но |S(p)| = 2°( р ' 2 \ поскольку (нумерованный) граф с р вершинами определяется подмножеством включённых в него рёбер, выбранных измножества всех возможных рёбер, а их С(р, 2).ДОКАЗАТЕЛЬСТВОЗаметим, чтоС(к 2)С(ЬС(кк'> ~ 2!(fc-2)!(fc 1)!~2!(fc — 3)!h12)2k ( k—~l2)t * -1^ 22)t~"1LДалее имеем:|£(P)| ^|£'(p)| ^\9(p-l)\=„ Mz J _ откуда lim Щ= 0.9(P)2P-1'p-*oo |9(p)|=2C<P.2)-(P-I)=ISCP)^-^-1)•10.3.
Гамильтоновы циклы34310.3. Гамильтоновы циклыНазвание «гамильтонов цикл» произошло от задачи «Кругосветное путешествие», придуманной Гамильтоном1 в XIX веке: нужно обойти все вершины графа,диаграмма которого показана на рис. 10.6 (в исходной формулировке вершины были помечены названиями столиц различных стран), по одному разу ивернуться в исходную точку. Этот граф представляет собой укладку додекаэдра.10.3.1. Гамильтоновы графыЕсли граф имеет простой цикл, содержащий все вершины графа (по одномуразу), то такой цикл называется гамилътоновым циклом, а граф называется гамилътоновым графом.Гамильтонов цикл пе обязательно содержит все рёбра графа. Ясно, что гамильтоповым может быть только связный граф.ЗАМЕЧАНИЕЛюбой граф G можно превратить в гамильтонов, добавив достаточное количество новыхвершин и инцидентных им рёбер и не добавляя рёбер, инцидентных только старым вершинам.
Для этого, например, достаточно к вершинам v\,...,vv графа G добавить вершиныmi, ... ,и р и множество рёбер {(г>г,иг)} и {(и*,i>i+i)}Простые необходимые и достаточные условия гамильтоновости графа неизвестны. Известны только некоторые достаточные условия, одно из которых приведено в следующей теореме.1Уильям Гамильтон ( 1 8 0 5 - 1 8 5 6 ) .344Глава 10. Циклы, независимость и раскраскаТЕОРЕМАЕсли 6{G) ^ р/2, то граф G является гамилътоновым.ДОКАЗАТЕЛЬСТВО О Т противного. Пусть G — пе гамильтонов. Добавим к G минимальное количество новых вершин и\,...,ип,соединяя их со всеми вершинамиG так, чтобы граф G' : = G + и\ +Ь ип был гамильтоновым.Пусть v,ui,w,...,v — гамильтонов цикл в графе Gпричёмv е G, щ е G',и\ $ G.
Такая пара вершин v и щ в гамильтоиовом цикле обязательно найдется,иначе граф G был бы гамильтоновым. Тогда w 6 G, w 0 {щ,... ,ип}, иначевершина щ была бы не нужна. Более того, вершина v не смежна с вершиной w,иначе вершина и\ была бы не нужна. Далее, если в цикле v, ui, w,..., v', w',..., vесть вершина w', смежная с вершиной w, то вершина v' не смежна с вершинойv, так как иначе можно было бы построить гамильтонов цикл v, v',..., w, w'...
vбез вершины щ, взяв последовательность вершин w,... ,v' в обратном порядке.Отсюда следует, что число вершин графа G', не смежных с v, не менее числавершин, смежных с w. Но для любой вершины w графа G d(w) ^ р/2 + п попостроению, в том числе d(v) ^ р/2 + п. Общее число вершин (смежных и несмежных с v, за исключением самой вершины v) составляет п + р — 1. Такимобразом, имеем:п + р-1 = d(v) + d(v) ^ d(w) + d(v)Следовательно, 0 ^ п + 1, что противоречит тому, что п > 0.=+•10.3.2. Задача коммивояжёраРассмотрим следующую задачу, известную как задача коммивояжёра. Имеется ргородов, расстояния между которыми известны.
Коммивояжёр должен посетитьвсе р городов по одному разу, вернувшись в тот, с которого начал. Требуетсянайти такой маршрут движения, при котором суммарное пройденное расстояниебудет минимальным.Очевидно, что задача коммивояжёра — это задача отыскания кратчайшего гамильтоиова цикла в нагруженном полном графе.Можно предложить следующую простую схему решения задачи коммивояжёра:сгенерировать все р\ возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать из них кратчайший.Очевидно, такое вычисление потребует не менее 0(р\) шагов.Как известно, р\ — быстро растущая функция.
Таким образом, решение задачикоммивояжёра описанным методом полного перебора оказывается практическинеосуществимым даже для сравнительно небольших р. Более того, известно, чтозадача коммивояжёра принадлежит к числу так называемых NP-полных задач,подробное обсуждение которых выходит за рамки этого учебника.Вкратце суть проблемы ./VP-полноты сводится к следующему.
В различных областях дискретной математики, комбинаторики, логики и т. п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющихполиномиальную сложность. Более того, если бы удалось отыскать эффектив-10.4. Независимые и покрывающие множества345ный алгоритм решения хотя бы одной из этих задач, то из этого немедленноследовало бы существование эффективных алгоритмов для всех остальных задачданного класса. На этом основано общепринятое мнение, что таких алгоритмовпе существует.ОТСТУПЛЕНИЕПолезно сопоставить задачи отыскания эйлеровых и гамильтоновых циклов, рассмотренные в этом и предыдущем разделах. Внешне формулировки этих задач очень похожи,однако они оказываются принципиально различными с точки зрения практического применения.
Уже давно Эйлером получено просто проверяемое необходимое и достаточноеусловие существования в графе эйлерова цикла. Что касается гамильтоновых графов, тодля них неизвестны простые необходимые и достаточные условия. На основе необходимого и достаточного условия существования эйлерова цикла можно построить эффективныеалгоритмы отыскания такого цикла. В то же время задача проверки существования гамильтопова цикла оказывается ./VP-полной (так же как и задача коммивояжёра).
Далее,известно, что почти нет эйлеровых графов, и эффективный алгоритм отыскания эйлеровых циклов редко оказывается применимым на практике. С другой стороны, можнопоказать, что почти все графы — гамильтоновы, то естьоо |S(p)|где 'Kip) — множество гамильтоновых графов с р вершинами, a S(р) — множество всехграфов с р вершинами. Таким образом, задача отыскания гамильтонова цикла или задача коммивояжёра являются практически востребованными, по эффективный алгоритмрешеиия для них неизвестен (и, скорее всего, пе существует).10.4. Независимые и покрывающие множестваПрежде всего введём определения и рассмотрим основные свойства независимых и покрывающих множеств вершин и рёбер. Эти определения и свойстваиспользуются в последующих разделах.10.4.1. Покрывающие множества вершин и рёберГоворят, что вершина покрывает инцидентные ей рёбра, а ребро покрывает инцидентные ему вершины.
Множество вершин, которые в совокупности покрывают все рёбра, называется вершинным покрытием. Наименьшее число вершин вовсех вершинных покрытиях называется числом вершинного покрытия и обозначается аоПримеры1. ао{Кр) — р — 1, если Кр — полный граф.2. OLo{Km,n) = min(m, п), если K m > n — полный двудольный граф.3. ао(Кр)— 0, если Кр — вполне несвязный граф.4. ао(£п UG2) = 0:0(^1) + 0:0(^2), если G\ и G 2 — компоненты несвязного графа.346Глава 10. Циклы, независимость и раскраскаМножество рёбер, которые в совокупности покрывают все вершины, называется рёберным покрытием.
Наименьшее число рёбер во всех рёберных покрытияхназывается числом рёберного покрытия и обозначается a i .ЗАМЕЧАНИЕДля графа с изолированными вершинами а\ не определено.Примеры1.СХ.\{С2П)2. ai(C2n+i)3. а\(К2п)4. ai(K2n+])= TI,если С-гп — чётный цикл.= п-1-1, если С2п+\ — нечётный цикл.= п. если К2п — полный граф с чётным числом вершин.= п + 1, если К2п+1 — полный граф с нечётным числом вершин.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
