Гамильтонов цикл

Гамильтоновы циклы, теорема Дирака — Гамильтоновы циклы

Гамильтонов цикл

Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно.

В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются «планарными». Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день.

Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления.

Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии.

Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке.

Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики.

Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.

Просмотреть программу курса

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла.

Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность.

В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой — нет.

Попробуйте курс за Бесплатно

Так, друзья, ну мы с вами обсуждали эйлеровы циклы в графах, это действительно очень важный сюжет, конечно, ну давайте поговорим теперь про ещё один столь же важный сюжет, касающийся гамильтоновых циклов так называемых, это ещё одна очень красивая тема, которая касается обхода в графах.

Ну давайте я напишу это слово, гамильтоновы циклы, собственно ими мы собираемся заниматься, определение очень простое, вот если вы помните, что эйлеров цикл — это простой цикл, который проходит по всем рёбрам, графа, то гамильтонов цикл — это простой цикл, который проходит по всем вершинам графа.

Ну давайте вот дан какой-то граф G с множеством вершин V и множеством рёбер E, тогда мы говорим, что этот граф содержит гамильтонов цикл, если существует простой цикл, который проходит по всем вершинам этого графа. Ну естественно, имеет рёбрами рёбра этого графа. G содержит гамильтонов цикл, [ПИШЕТ НА ДОСКЕ] если в нём есть простой цикл, проходящий по всем вершинам.

В нём есть простой цикл, проходящий по всем вершинам. [ПИШЕТ НА ДОСКЕ] Ну тут ситуация следующая.

Если с эйлеровыми циклами всё было очень просто и можно было написать совершенно понятный и эффективный критерий эйлеровости графа, то есть можно было сказать, что граф является эйлеровым тогда и только тогда, когда степень каждой его вершины является чётным числом, был совершенно понятный, легко проверяемый критерий, то в случае с гамильтоновостью, как ни странно, всё оказывается намного, намного сложнее. Хотя вопрос о гамильтоновости графа так же, если угодно, если не более животрепещущ, нежели вопрос об его эйлеровости. Действительно очень сложная алгоритмическая задача — отыскание гамильтонова цикла в графе, даже если известно, что этот граф гамильтонов. Очень трудная задача, и в общем случае она решается более-менее только перебором. Вот. И человечество, конечно, уже столетие фактически интересуется вопросом о том, как бы можно было всё-таки охарактеризовать графы, являющиеся гамильтоновыми. Можно ли придумать какие-то если не критерии, то хотя бы признаки, достаточные признаки гамильтоновости. И вот я сегодня хочу рассказать два очень важных, очень красивых признака, которые в некотором смысле друг друга дополняют. Один признак совершенно классический, и очень многие, конечно, его знают, а другой признак, который работает в некотором смысле в дополнительных по отношению к первому ситуациях, его вот как-то не очень принято знать. Хотя это очень досадно, он действительно работает, и я постараюсь с максимальным, конечно, пафосом, катарсисом, рассказать о том, как это всё устроено, как действительно получается этим пользоваться. Ну давайте я начну с теоремы, которая называется Признак Дирака, и это тот самый классический признак, который, как я подозреваю, очень многие слушатели могли бы знать и до этих лекций. Но если не знают, то тем более я счастлив, что доношу до вас и в этом месте какую-то принципиально новую информацию. Значит, Признак Дирака говорит следующее: если каждая вершина графа, каждая вершина графа имеет степень, [ПИШЕТ НА ДОСКЕ] не меньшую, чем половина от общего числа вершин этого графа, не меньшую… Ну, давайте я общее число вершин графа обозначу n, тогда можно будет просто написать «не меньшую n/2», где, повторяю, n — это просто количество вершин в нашем графе. Дан какой-то граф, у него n вершин, и мы предполагаем, что каждая вершина этого графа имеет степень, не меньшую, чем n/2, чем половина от общего числа вершин этого графа. И вот если каждая вершина графа имеет степень, не меньшую n/2, то граф является гамильтоновым, содержит гамильтонов цикл. Граф гамильтонов. Ну въедливый слушатель может, конечно, меня спросить, а где же условия связности, ведь понятно, что если граф не является связным, то ни эйлеровым, ни гамильтоновым он, конечно, не будет в каком-либо содержательном смысле этого слова. Простого цикла, который проходит то ли по всем рёбрам, то ли по всем вершинам этого графа, он, конечно, содержать не будет. То есть вроде как нужно было где-то здесь написать, что этот граф обязан быть связным. Ну, замечание состоит в том, что это-то как раз следует из условия. То есть граф, у которого степень каждой вершины не меньше половины от общего числа вершин этого графа, он автоматически является связным. Давайте я это замечание сразу сделаю, и въедливые слушатели будут, я надеюсь, удовлетворены. Итак, замечание состоит в том, что если для графа выполнено условие теоремы, выполнено условие теоремы, то этот граф автоматически связен. То этот граф связен. Граф связен. Ну действительно, давайте как-то попробуем это осознать вместе, почему этот граф связен. Почему в случае таких больших степеней вершин связности нам не избежать. Давайте рассмотрим произвольные две вершины этого графа. Совершенно любые. Ну какие-то там v и w, скажем. Рассмотрим произвольные две вершины нашего графа. Конечно, они могут быть соединены ребром. Ну если они соединены ребром, значит, конечно, они уже соединены, то есть от одной до другой по какой-то простой цепочке мы прошли. Поэтому давайте такую тривиальную ситуацию не рассматривать, когда они соединены ребром, и предположим, что между этими вершинами ребра нет. Ну давайте я это всё запишу. Рассмотрим две вершины графа любые совершенно, любые две вершины графа, и предположим, что между ними нету ребра. А мы хотим доказать, что всё равно какой-то цепочкой они между собою связаны. Тогда, естественно, получится, что наш граф является связным. Итак, рассмотрим любые две вершины графа и предположим, что между ними ребра нет. Нет ребра. Давайте в этом случае посмотрим, кто же всё-таки является соседями вершины v в нашем графе и кто является соседями вершины w. Мы с вами знаем, товарищи, что и у вершины v, и у вершины w по крайней мере n/2 соседей. Ну просто таковы условия нашей теоремы — у каждой вершины не меньше, чем n/2 соседей. Смотрите, вот здесь вот, то есть среди вершин нашего графа, которые не совпадают ни с вершиной v, ни с вершиной w, конечно же, n − 2 вершины всего. Потому что в графе по определению, по условию n вершин. Вот у нас две вершины выделены, а вот в этом облачке, в этой сарделечке, n − 2 оставшихся вершины нашего графа. И вот мы знаем, что вершина v соединена как минимум с n/2 вершинами отсюда, потому что таковы условия теоремы. И одновременно мы знаем, что w соединена как минимум с n/2 вершинами опять же из этого облачка. Но при этом вершины v и w по нашему предположению не соединены, то есть действительно все соседки нашей вершины v, так же точно, как все соседки нашей же вершины w, находятся вот в этом облачке. Облачко имеет размер n − 2, размер подсарделечки, состоящей из соседок, для каждой из наших вершин это как минимум n/2, ну понятно, там по принципу Дирихле или просто, ну я не знаю, очевидно, что два множества, каждое из которых имеет мощность, не меньшую, чем n/2, и при этом содержится в множестве мощности n − 2, два таких множества непременно пересекутся. Ну давайте это зафиксируем. Ясно, что множество соседей вершины v пересекается с множеством соседей вершины w. Пересекается с множеством соседей, ну или соседок там, не знаю, вершин, да? С множеством соседей вершины w. Ну раз эти два множества персекаются, давайте я перерисую картиночку ещё раз, вот у меня есть v, вот у меня есть w, есть какие-то соседи у v, есть какие-то соседи, соседки у w, есть общие элементы в этих двух множествах. Значит, есть какая-то вершина, которая одновременно является соседкой вершины v и соседкой вершины w. То есть это означает, что либо между v и w проходит ребро, и тогда очевидно, что между v и w есть какая-то простая цепь, ну вот просто это ребро и является такой простой цепью, либо, если этого ребра нет, то заведомо есть вот такая галочка, которая опять же соединяет вершины v и w, делая в этом месте, по крайней мере по отношению к этим двум вершинам, граф связным. То есть между вершинами v и w, как мы выяснили, обязательно есть простая цепь. Либо она представляет собой ребро, либо, если этого ребра нет, тогда есть общая соседка. То есть вообще у нас получается, что в этом случае, то, что называется, диаметр графа точно не превосходит 2, потому что между любыми двумя вершинами есть простая цепь длины не более двух. Мы можем очень быстро перебежать из одной вершинки в другую. Ну быстро или не быстро, в любом случае это, конечно, означает, что граф связен и наше замечание полностью доказано.

Источник: https://ru.coursera.org/lecture/teoriya-grafov/gamil-tonovy-tsikly-tieoriema-diraka-bMLVS

Гамильтонов цикл и гамильтонов граф. — Графы и архитектура

Гамильтонов цикл

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира.Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным.Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…, vp графа G добавить вершины u1, …, up и множество ребер {(vi, ui)} {(ui, vi+1)}.Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) — по входящим.Рассмотрим несколько достаточных условий существования гамильтоновых циклов в графе.Во-первых, всякий полный граф является гамильтоновым. Действительно, он содержит такой простой цикл, которому принадлежат все вершины данного графа. Во-вторых, если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие ребра, то он также является гамильтоновым.Простой (гамильтонов) цикл выделен сплошной линией (1, 2), (2, 3), (3, 4), (4, 5), (5, 1). Заметим, что если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.Если гамильтонов граф объединить с еще одной вершиной ребром так, что образуется висячая вершина, то такой граф гамильтоновым не является, поскольку не содержит простого цикла, проходящего через все вершины графа.Не является гамильтоновым и граф, представляющий собой простой цикл с «перекладиной», на которой расположены одна или несколько вершин.Теорема (Дирак, 1952) 1. Если в простом графе с n > 3 вершинами p(v) > n/2 для любой вершины v, то граф G является гамильтоновым. Замечание. Существует несколько доказательств этой широко известной теоремы, здесь мы приводим доказательство Д. Дж. Ньюмана.Доказательство. Добавим к нашему графу k новых вершин, соединяя каждую из них с каждой вершиной из G. Будем предполагать, что k — наименьшее число вершин, необходимых для того, чтобы полученный граф Gстал гамильтоновым. Затем, считая, что k > 0, придем к противоречию.Пусть v>p>w>…>v гамильтонов цикл в графе G, где v, w— вершины из G, а p— одна из новых вершин. Тогда w не является смежной с v, так как в противном случае мы могли бы не использовать вершину p, что противоречит минимальности k. Более того, вершина, скажем, w, смежная вершине w, не может непосредственно следовать за вершиной v, смежной вершине v, потому что тогда мы могли бы заменить v>p>w>…>v> w>v на v>v>…>w>w>…>v, перевернув часть цикла, заключенную между w и v. Отсюда следует, что число вершин графа G, не являющихся смежными с w, не меньше числа вершин, смежных с v (то есть равно, по меньшей мере, n/2 + k); с другой стороны, очевидно, что число вершин графа G, смежных с w, тоже равно, по меньшей мере, n/2 + k. А так как ни одна вершина графа Gне может быть одновременно смежной и не смежной вершине w, то общее число вершин графа G, равное n + k, не меньше, чем n + 2k. Это и есть искомое противоречие.Теорема (Оре) 2. Если число вершин графа G(V, E) n > 3 и для любых двух несмежных вершин u и v выполняется неравенство:d(u) + d(v) > n и (u, v)E, то граф G — гамильтонов.Граф G имеет гамильтонов цикл если выполняется одно из следующих условий: Условие Бонди: из d(vi) > i и d() > k => d(vi) + d() > n (k ? i)Условие Хватала: из d() > k > n/2 => d(vn-k) > n k.Далее, известно, что почти все графы гамильтоновы, то естьгде H(p) — множество гамильтоновых графов с p вершинами, а G(p) — множество всех графов с p вершинами. Задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего не существует) эффективный алгоритм решения.

Источник: https://www.sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/vvedenie-v-teoriu/gamiltonov-cikl-i-gamiltonov-graf

Гамильтонов цикл

Гамильтонов цикл

Определение. Граф называетсягамильтоновым, если в нем имеетсяцикл, содержащий каждую вершину этогографа.

Уильям РоуэнГамильтон выпустил головоломку, сутькоторой состояла в построении пути,который через каждую вершину проходитпо одному разу. Задача похожа на задачуо нахождении эйлеровой линии, однакодо сих пор не найдены необходимые идостаточные условия существования вграфе гамильтоновых линий.

Похожана данную и задачао коммивояжере, котораятоже состоит в построении цикла,проходящего по всем городам по одномуразу, но при этом требуется минимизироватьтранспортные расходы. Алгоритма решенияданной задачи тоже не существует.

Некоторые головоломкитипа как перевезти волка, козу и капустутоже сводятся к поиску гамильтоновойлинии на некотором графе, изображающемвсе возможные перевозки.

Известна такжезадача о нахождении пути коня на шахматнойдоске, при котором он побывает на каждомполе по одному разу (вариант – и вернетсяна исходное поле последним ходом),которая тоже является частным случаемзадачи о нахождении гамильтоновойлинии.

Например,на рисунках 18 и 22 – изображены гамильтоновыграфы, а на рисунках 21 и 23 графы, неявляющиеся гамильтоновыми.

Турниры

Определение. Граф называетсяполугамильтоновым, если существуетмаршрут, содержащий каждую его вершинуровно один раз.

Определение. Турнир (полныйориентированный граф) – орграф, в которомлюбые его две вершины соединены ровноодной дугой.

Этот класс графов получил свое названиев связи со спортивными турнирами безничьих, проводимых по круговой системе.Результаты встреч можно описать орграфом,вершины которого соответствуют участникамсоревнований, а дуга (v,w) есть в графе, еслиучастник, соответствующий вершинеv,выиграл у участника, соответствующеговершинеw.

На рисунке 24 изображен не сильносвязныйтурнир, а на рисунке 25 – сильносвязный.

Теорема.Любой турнир полугамильтонов.

Доказательство(метод математическойиндукции по количеству вершин). Еслитурнир имеет меньше четырех вершин, тоутверждение, очевидно, верно. Проведеминдукцию по числу вершин.

Предположим,что любой турнир с n вершинамиполугамильтонов. Пусть Т — турнир с n+1вершинами, и пусть турнир Т’ с n вершинамиполучен из Т удалением некоторой вершиныо вместе со всеми инцидентными ей дугами.

Тогда но предположению индукции Т’обладает полугамильтоновым маршрутом

Рассмотрим три случая.

(1) Если {v, v1) — дуга вT,то искомой простой орцепью является

(2) Если (v,v1)не является дугой в Т (это означает, чтодугой является (v1,v)) и если существует такоеi, что (v,vi)-дуга вT, то, выбирая первоеiс таким свойством (см.рис. 26), получим, что искомым маршрутомявляется

(3) Если в Т не существует дуги вида(v,vi), то искомыммаршрутом является

Теорема.Любой сильно связный турниргамильтонов.

Доказательство(метод математическойиндукции по длине цикла). Докажем белеесильный результат ,состоящий в том, чтосильно связный турнир Т с n вершинамисодержит циклы длины 3, 4, … n.

Докажем, что существует цикл длины три.Пусть Т – сильно связный турнир.

Тогдадля любой вершины v из Т все множестводуг ей инцидентных можно разделить надва не пересекающихся подмножества W –множество дуг для которых вершина vявляется концом и Z – множество дуг длякоторых вершина v является началом.

Таккак Т сильно связен, то оба этих множестване пусты, следовательно найдутся вершиныw принадлежащая W и z принадлежащая Z,тогда имеем цикл v, w , z, v длины три.

Предположим, что существуют циклы длиныменьшей или равной k–v1, v2, …,. Докажем, чтосуществует цикл длины к. Возможны дваслучая:

1. Существует вершина v, у которой естьинцидентные дуги, направленные к циклуи направленные из цикла. Тогда находимпервую дугу, направленную к циклу, пустьэто будет дуга (v, vi). Тогда искомый циклимеет вид: v1, v2, …vi-1,v, vi,…,.

2. Для любой вершины графа все дугинаправлены либо к циклу, либо из цикла.

Тогда все множество вершин, не входящихв цикл можно разделить на дванепересекающихся подмножества W –множество вершин у которых все дугинаправлены к циклу и Z – множество вершину которых все дуги направлены из цикла.

Так как Т сильно связен, то оба этихмножества не пусты, следовательнонайдутся вершины w’ принадлежащая W иz’ принадлежащая Z, тогда имеем цикл v1,w',z',v3, …,.длиныk+1 (см. рис. 27).

Деревья

Определение.Лесом называют графбез циклов.

Определение.Деревомназываютпроизвольный связный граф без циклов.

Таким образом, лесом называетсянесвязныйграф, представляющийобъединениедеревьев.Нарисунке 28, представленном ниже, изображенлес с четырьмя компонентами связности,каждая из которых представляет собойдерево.

Удобно считать, что граф, состоящий изодной изолированной вершины, тожеявляется деревом.

Определение.Вершина дерева, степенькоторой равна единице, называетсявисячей вершиной илилистом.

Свойства деревьев

  1. Граф является деревом тогда и только тогда, когда каждая пара вершин в нем соединена одной и только одной простой цепью.

  2. Удаление всякое ребра в дереве приводит к увеличению числа компонент связности.

  3. Дерево с pвершинами всегда имеет (p-1) ребер.

  4. Если G- лес, р — вершин и к компонент связности, тоGимеет р-к ребер.

  5. В каждом дереве существует по крайней мере две висячие вершины.

Доказательство свойств деревьевпредлагается читателю в качествеупражнений.

Определение.Для произвольногосвязного неориентированного графаG(V,E) каждое дерево Т(V1,T1), гдеV1=V и Е1E,называют стягивающим деревом (каркасом,остовом). Ребра такого дерева называютветвями, а остальные ребра графа -хордами.

На рисунке 29 приведен пример графа иего каркасов.

На рисунке 30 представлены граф и егокаркасы, построенные методами поискав глубину и в ширину. В круглых скобкахуказана очередность просмотра вершинграфа при соответствующем поиске.

Планарные графы

Во многих случаях не имеет значения,как изобразить граф, т.к. изоморфныеграфы несут одну и ту же информацию. Новстречаются ситуации, когда важновыяснить, возможно ли нарисовать графна плоскости так, чтобы его изображениеудовлетворяло определенным требованиям.

Например, в радиоэлектронике приизготовлении микросхем печатным способомэлектрические цепи наносятся на плоскуюповерхность изоляционного материала.Так как проводники не изолированы, тоони не должны пересекаться.

Аналогичнаязадача возникает при прокладкежелезнодорожных и других путей, где нежелательны переезды.

Определение. Плоскимназываетсяграф, изображенный на плоскости так,что никакие два ребра геометрически непересекаются нигде, кроме инцидентныхим обоим вершин.

Определение.Граф, изоморфныйплоскому, называетсяпланарным.

Граф К4(рис. 31) – планарен, емусоответствуют плоские графы, изображенныена рисунках 32 и 33.

Определение. Область, ограниченнаяребрами в плоском графе, и не содержащаявнутри себя вершин и ребер, называетсягранью.

Ниже на рисунке 34 изображен граф счетырьмя гранями.

Заметим, что грань 4 не ограничена, такуюгрань называют внешней, все остальныеграни называютвнутренними.

Теорема (Формула Эйлера). Пусть G -связный планарный граф. Тогда справедливоследующее p-q+r=2, где p — количество вершин,q — количество ребер, r — количество граней.

Доказательство(методом математическойиндукции по количеству ребер). При q=0теорема верна. Очевидно, что если q=0, тоp=1 и r=1, тогда p-q+r=2.

Пусть теорема верна для всех графов сq ребрами: p-q+r=2. Добавим еще одно ребро.Если добавляемое ребро соединяетсуществующие вершины, то q1=q+1, p1=p, r1=r+1 иp1-q1+r1=p-(q+1)+r+1= p-q+r=2. Если добавляемое ребросоединяет существующую вершину с новой,то q1=q+1, p1=p+1, r1=r и p1-q1+r1=p+1-(q+1)+r= p-q+r=2.

Теорема. ЕслиG- связныйпланарный граф с р вершинами и q ребрамииp>3, тоq3p-6.

Доказательство. Так как каждая граньограничена по крайней мере тремя ребрами,каждое ребро ограничивает не более двухграней, то 3r2q.Из формылы Эйлера следует ,что 2=p-q+r,тогда 2p-q+2/3q,следовательно 3p-3q+2q6,тогдаq3p-6

Теорема. Граф К5 не являетсяпланарным.

Доказательство. Предположимпротивное, граф планарен. Тогда p=5,q=4*5/2=10, по формуле Эйлераr=7. Тогда не выполняетсяусловие предыдущей теоремыq3p-6,а значит, наше предположение не вернограф не является планарным.

Теорема. Граф К3, 3 не являетсяпланарным.

Доказательство. Предположимпротивное, граф является планарным.Тогда p=6,q=9, по формулеЭйлераr=5. В данном графенет треугольников, следовательно, еслион планарен, то в его плоской укладкекаждая грань ограничена по крайней мере4 ребрами. Таким образом, 4r2q,2rq.Но полученное условие для нашего графане выполняется, а значит, наше предположениене верно граф не является планарным.

Теорема. В планарном графе существуетвершина степени не больше пяти.

Доказательство. Предположимпротивное, степень любой вершины графане менее шести. Тогда сумма степенейвсех вершин не менее 6*р, следовательнопо лемме о рукопожатиях 2q6p,отсюдаpq/3.Так какq3p-6,получимqq-6.Таким образом получили противоречие,значит, наше предположение не верно, впланарном графе обязательно должнабыть вершина степень которой меньшешести.

Определение.Элементарнымстягиваниемназывается следующаяпроцедура: берем ребро е (вместе синцидентными ему вершинамиu,v) и “стягиваем ” его, тоесть удаляем е и отождествляем вершиныuиv;полученная при этом вершина инцидентнатем ребрам (отличным от е), которымпервоначально были инцидентны вершиныuиv.

Ниже на рисунке 35 представлены дваграфа: до и после процедуры элементарногостягивания ребра е.

Определение.ГрафGназывается стягиваемым к графуH,если Н можно получить изGс помощью некоторой последовательностиэлементарных стягиваний.

Теорема Куратовского. Граф являетсяпланарным тогда и только тогда, когдав нем нет подграфов, стягиваемых к графамК5или К3,3.

Раскрашиваниеграфов

Определение.Произвольная функцияf:V{1,2,…,k}, где kпринадлежит множеству натуральныхчисел, называется вершинной k-раскраскойграфа G(V,E).

Определение. Раскраска называетсяправильной, если f(u)f(v),для любых смежных вершин u и v.

Определение. Граф, для которогосуществует правильная k-раскраска,называется k-раскрашиваемым.

Определение. Минимальное число k,при котором граф G является k-раскрашиваемым,называется хроматическим числом графаи обозначается(G).

Для графа на рисунке 36 (G)=3.Меньшим количеством цветов граф правильнораскрасить нельзя из-за наличия подграфовК3. Рядом с вершинами графа — указаныномера цветов.

Раскраскапланарных графов

Проблема раскраски планарных графовявляется одной из самых знаменитыхпроблем теории графов. Первоначальновопрос формулируется следующим образом:достаточно ли четырех красок для такойраскраски произвольной географическойкарты, при которой соседние страныокрашены в различные цвета? В 1879 г.британский математик А.

Кэли выдвинулгипотезу четырех красок: «Всякий планарный граф вершинно 4-раскрашиваем.»Гипотеза четырех красок привлекалавнимание многих исследователей. Уже в1880 г. появилось первое доказательствоА.Кемпе. Ошибка в этом доказательствебыла обнаружена Р. Хитвудом в 1890 г.

Одновременно он показал, что если вформулировке гипотезы слова “четыре”заменить на “пять”, то полученнаятеорема легко доказывается.

Теорема.о пяти красках. Всякийпланарный граф 5-раскрашиваем.

Доказательство(метод математическойиндукции по количеству вершин). Дляпланарных графов, у которых меньше шестивершин теорема очевидна.

Предположим, что G планарный граф с nвершинами, и что все планарные графы с n-1 вершинами 5-раскрашиваемы. Можносчитать, что G плоский граф, и что онсодержит вершину v, степень которой небольше пяти.

Удаление вершины v и всехинцидентных ей ребер приводит нас кграфу с n-1 вершиной, который, попредположению индукции 5-раскрашиваем,раскрасим его.

Тогда в исходном графеG останется окрасить только одну вершинуv.

Если степень вершины v меньше пяти, тоее можно окрасить в любой цвет, неучаствующий в окраске смежных с нейвершин.

Пусть степень вершины v равна пяти. Еслисреди смежных вершин есть две вершиныодинакового цвета, то ее можно окраситьв цвет, не использованный для окраскиэтих вершин.

Итак, остался последний случай: всемвершинам, смежным с v присвоены различныецвета. Обозначим вершины, смежные с vчерез v1,v2,…,v5. Пусть они окрашены в цветаc1,c2,…,c5. Определим H(i,j) какподграф графа G, вершинами которогоявляются все вершины цвета ci или cj, аребрами — все ребра, соединяющие вершинуцвета ci с вершиной цвета cj. Рассмотримдва случая.

1). v1 и v3 не принадлежат одной компонентесвязности графа H(1,3). В этом случае можнопоменять цвета всех вершин той компонентыH(1,3), которая содержит v1 (цвет с1 на цветс3, а цвет с3 на цвет с1). В результате v1приобретет цвет c3, что позволит окраситьv в цвет c1.

2). v1 и v3 принадлежат одной компонентесвязности графа H(1,3). В этом случаесуществует цикл C вида v->v1->..->v3->v,часть которого, заключенная между v1 иv3 целиком лежит в H(1,3).

Так как v2 находитсявнутри цикла C, а v4 — вне его, то несуществует простой цепи из v2 в v4, целикомлежащей в H(2,4). Поэтому v2 и v4 принадлежатразным компонентам связности графаH(2,4).

В этом случае можно поменять цветавсех вершин той компоненты H(2,4), котораясодержит v2 (цвет с2 на цвет с4, а цвет с4на цвет с2). В результате v2 приобрететцвет c4, что позволит окрасить v в цветc2.

Таким образом, все вершины исходногографа можно окрасить в 5 цветов, что итребовалось доказать.

Задачипо теории графов

Источник: https://studfile.net/preview/1620095/page:13/

Реализация алгоритма на языке С++

Рисунок 1. Реализация алгоритма на языке С++. Автор24 — интернет-биржа студенческих работ

Реализация алгоритма на языке PYTHON

Рисунок 2. Реализация алгоритма на языке PYTHON. Автор24 — интернет-биржа студенческих работ

Функция Hamilton сначала заносит вершину curr последней в список Path. Причём, если размер списка стал равен n, что означает включение всех вершин в состав пути Path, то выполняется проверка соединения ребром первой и последней вершины (только при поиске гамильтонова цикла, для пути это не требуется) и если такое ребро есть, то возвращается значение True (цикл обнаружен).

Если же такого ребра нет, то выполняется удаление из Path последней вершины и возврат значения возвращает False (цикл не обнаружен). В случае, когда размер списка менее n, делается отметка, что вершина curr посещалась, и процесс перебора продолжается далее.

Поочерёдно выполняется обход всех оставшихся вершин next и в случае соединения ребром вершины next с вершиной curr, если при этом вершина next ещё не посещалась, то делается рекурсивный запуск алгоритма из вершины next с целью найти путь в эту вершину.

И если рекурсия из вершины next закончится возвратом True, то есть удачным построением цикла, то алгоритм так же делает возврат True. В этом случае из переменной Path нет никаких удалений, и в списке Path находится весь гамильтонов цикл.

Если не выбран ни один из выше указанных вариантов, то выполняется возврат вершины curr, то есть делается пометка, что она не посещалась, её удаляют из окончания списка Path и алгоритм возвращается к обработке последней вершины в списке Path. Следует отметить, что алгоритмическая сложность этого метода будет не меньше, чем n!, и это означает непригодность данного алгоритма для графов большого объёма.

Задача работы коммивояжёра

Задачей, аналогичной и близкой по смыслу процедуре определения гамильтонова цикла, считается задача работы коммивояжёра. Условие задачи следующее. Странствующий торговец, именуемый коммивояжёром, должен объехать n городов и возвратиться к дому.

Коммивояжёр не намерен приезжать в каждый город более чем один раз и желает, чтобы маршрут его перемещений был оптимальным, то есть самым коротким из возможных. Это означает поиск внутри неориентированного взвешенного графа маршрута (пути), который обладает наименьшим весом (стоимостью).

Проблему коммивояжёра возможно решить по аналогии с задачей гамильтонова цикла (пути), но в этом случае необходимо сделать перебор всех возможных маршрутов. При зацикливании пути необходимо определить его суммарный вес и выполнить сравнение найденного маршрута с весом предыдущего самого лучшего известного маршрута.

Оптимально эту операцию выполнять не при окончании замыкания, а единовременно с прибавлением очередной вершины прибавлять вес рассматриваемого ребра, как выстроенного компонента маршрута.

Источник: https://spravochnick.ru/informatika/gamiltonov_cikl/

Booksm
Добавить комментарий