Содержание к диссертации
Введение
Глава I. Свойства структуры максимальных клик максимально негамильтоновых графов 21
1. Собственные вершины максимальных клик и сведение к упрощенным МНГ графам 22
2. Построение МНГ-системы 26
3. Оценка порядков и числа упрощенных МНГ графов 34
Выводы 46
Глава II. Правила вывода максимально негамильтоновых графов 48
1. Свойства некоторых элементов МНГ графов 51
2. Правила вывода, использующие основание графа 62
3. Правила вывода, использующие промежуточные клики 72
4. Правила вывода, использующие опорные и соединительные клики ... 93
5. Цепочки правил вывода 109
Выводы 115
Заключение 118
- Построение МНГ-системы
- Оценка порядков и числа упрощенных МНГ графов
- Правила вывода, использующие основание графа
- Правила вывода, использующие опорные и соединительные клики
Построение МНГ-системы
Изучение графов из определенного класса как правило ведется при помощи описания свойств некоторого набора числовых характеристик графа - например при изучении графов с гамильтоновыми циклами используются степенные последовательности (списки степеней вершин графа — см. теоремы 2-4). Выбор набора числовых характеристик в большинстве случаев закономерен и обуславливается спецификой задачи. Во многих случаях в качестве такого набора используются различные инварианты графа. В случае упрощенных МНГ графов станем использовать в качестве такого набора количество вершин в пересечениях максимальных клик. Пусть Кх, ..., Кг - такая совокупность различных максимальных клик графа G, что каждое ребро графа принадлежит хотя бы одной из этих клик (также в этом случае будем говорить, что объединение указанных клик дает весь граф). В частности, в качестве Кх, ..., Кг можно взять совокупность всех максимальных клик графа G. Обозначим R = {1,2,...,г}. Пусть / подмножество R. Определим подмножество М, множества вершин графа G следующим образом: Очевидно, что множества Mt и Mj не пересекаются при различных / и J, объединение \JMJ исчерпывает все множество вершин графа G и М0 = 0. Далее нам понадобится следующая лемма. Лемма 3. Пусть I — произвольное подмножество в R. Тогда любая вершина а из множества Mf смежна со всеми вершинами максимальных клик К,, і є І, отличными от а, и только с ними. Доказательство. Пусть для некоторого ієі вершина Ъ лежит в максимальной клике Кг Тогда, поскольку по определению множества М7 вершина а обязана, в частности, лежать в клике Кп то вершины а и Ъ смежны. Пусть теперь вершина Ь смежна с вершиной а. Найдется максимальная клика Kt, содержащая ребро {а, Ь) (возможна такая найдется не одна - возьмем любую из них). В частности, клика Ki будет содержать вершину а, из-за чего і el. Действительно, если / не принадлежит /, то а принадлежит множеству множестве Mj. Обозначим nI = \Mj\, где I- произвольное подмножество в R. Для МНГ графов множества Мп IczR содержат относительно небольшое число элементов, а именно справедлива следующая теорема. Теорема 15. Пусть G - МНГ граф. Тогда, если 7, 72 ... 7, с=7? -цепочка вложенных различных подмножеств R, причем 7, 2, то
Доказательство. Пусть \JM, ={«,,...,ат} и 7, = ( ,...,/,}. Поскольку /=i множества М, и Mj не пересекаются при I J, то следовательно, для доказательства теоремы достаточно показать, что т s. Во множестве 7, найдется пара различных номеров р и q, поскольку по условию теоремы 7, 2. Пусть, далее hp -вершина из максимальной клики Кр и hq - вершина из максимальной клики Kq, причем hp несмежна с hq (такие вершины найдутся, поскольку клика Кр не совпадает с кликой Ка). Из несмежности вершин hn и /z следуют два вывода: 1) ни одна из вершин hp и hq не лежит во множестве {ар..., ат}, поскольку по предыдущей лемме каждая из а. смежна со всеми вершинами клик Кр и Kq; 2) в G вершины hp и hq соединены гамильтоновой цепью (простой цепью, проходящей по всем остальным вершинам графа), поскольку G - МНГ граф. Гамильтонова цепь из hp в hq не содержит отрезков щ ар то есть не может иметь вид поскольку иначе в графе G найдется гамильтонов цикл что противоречит негамильтоновости графа G. Таким образом, гамильтонова цепь, соединяющая hp и hq, обязана иметь вид причем цепи t., i = 2,m содержат хотя бы по одной вершине. Без ограничения общности считаем, что jt =/, 1 = \,т. Тогда гамильтонова цепь из h„ в ha примет вид Обозначим для i = 2,m через bt последнюю вершину в цепи Tt. Пусть, дополнительно, Ьх - последняя вершина в цепи 7Х, если эта цепь не пуста и Ъх совпадает с hp, если цепь Тх пуста. В этих обозначениях гамильтонова цепь выглядит следующим образом: причем цепи S;, i = \,m + l могут быть пустыми. По лемме 3 получаем: {blt...,bm}c:K u...KjKl. Предположим, что найдется такое ie\,m, что bt принадлежит клике Kq. Тогда в G существует гамильтонов цикл: что противоречит негамильтоновости графа G. Следовательно, никакая из вершин bx, ..., bm не лежит в клике К . Теперь предположим, что m s. Тогда, поскольку все вершины Ьх, ..., Ът лежат в кликах Kt, ..., К{ и никакая из этих вершин не лежит в клике Кд, которая является одной из клик K!t, ..., К , то найдется пара вершин Ь, и bj, лежащая в одной клике. Следовательно, bt и Ъ. соединены ребром в графе G. Кроме того, a,eMj и ауєМу, где /,Jе{/,,...,/,}. Поскольку 1Х а 12 с:... с /,, то либо /сУ, либо Ус/. Также выполняется одно из двух неравенств: i j или / /. Проведем доказательство для случая, когда i j и J с /; в остальных трех случаях доказательство проводится аналогично. По лемме 3 получаем, что если некоторая вершина с, отличная от at, смежна с cij, то она смежна и с вершиной аг Следовательно, и первая вершина в цепи Тм Ьм и первая вершина в цепи JJ+l bJ+l смежны с al. Но тогда можно указать гамильтонов цикл в графе G: hp Т{ Ъх ах 12 ...s, 6,. bj J]x ам bH JJ_\ ...7 ] a, sj4X bJ+x aJ+x SJ+2 —Sm+l hqajhp, что противоречит с определением МНГ графа. Таким образом, неравенство m s приводит к противоречию. Теорема 15 доказана. Приведем в виде следствия один частный случай. Следствие 1. Если G - МНГ граф, то для любого I с: R, такого, что / 2, выполнено неравенство
Оценка порядков и числа упрощенных МНГ графов
Пусть G - упрощенный МНГ граф, в котором найдется г максимальных клик, объединение которых дает весь граф G. Напомним, что порядок графа G равен tij. Рассмотрим линейную функцию от переменных хп I czR, Пусть максимум этой линейной функции, ограниченной на множестве всех решений МНГ-системы, равен С(г). Тогда порядок графа G не превышает С(г). Обозначим через Р(г) максимум порядков упрощенных МНГ графов, имеющих ровно г максимальных клик. Ясно, что при любом натуральном значении г 1 верно неравенство Р(г) С(г) Далее вычислим точное значение величины C(r). Доказательство. При фиксированном г множество неизвестных МНГ-системы - это множество {Xji I czR, / 0 }. Количество неизвестных равно 2Г -1. Для краткости обозначений неравенства (4) перечислим в другом порядке. Обозначим для ке2,г через Dk множество упорядоченных наборов из к попарно различных чисел /15/2,...,/А, принадлежащ.../, сR, /( = / + 1, / = 1,/, 1 / г-1 и множеством [jDk существует соответствие, задаваемое следующим образом: цепочке /, 1... QI, соответствует набор i„...,/,+, из Dl+l, { ,,/2} = /,, ix i2, {ij} = Ij_x\Ij_2, j = 3,/ + 1. Легко убедиться, что такое соответствие взаимно однозначно: для набора /,,..., 4, удовлетворяющего указанным условиям, положим /, = { ",, /2}, /2 = /, u{z 3}, I3 = I2 J{i4}, ..., Ік_х = 1к_2u{ik}. Теперь неравенства (4) можно записать в таком виде: Отметим, что. неизвестные, участвующие в неравенствах (5), и неизвестные, участвующие в неравенствах (3), образуют непересекающиеся множества. Поэтому МНГ-систему можно разделить на две независимые СЛН: всех решений СЛН (6); линейная функция Xj имеет максимум С2 (г) на /сЯ,/; 2 множестве решений системы (7). В этом случае функция г(х7, I с R, I = 0) равна своему максимальному значению С(г) на некотором решении х п I с R, 7 0 МНГ-системы тогда и только тогда, когда: Легко видеть, что сумма всех неизвестных СЛН (6) принимает свое максимальное значение на решении x {i)=\, i-\,r. То есть максимум существует, причем Сх(г) = г. f г \ С2(г) = 2 нежесткости (его можно найти, например, в монографиях [10, 20]). Для того, чтобы воспользоваться этим условием, необходимо рассмотреть двойственную задачу к задаче о нахождении максимума линейной функции т(хг, I czR,I Ф0) на решениях системы (7) (называемой «прямой» задачей). Двойственная задача определяется следующим образом: Воспользуемся теоремой о дополняющей нежесткости ([10]).
Согласно этой теореме функция Е xi принимает свое максимальное значение на некотором решении х), IczR, 2 системы (7) и функция двойственной задаче тогда и только тогда, когда: если при каких-то кє2,г, (/,,...,4)єDk выполнено . / , Фк-\, то Д г„д) =0, и, если для какого то множества их множеству R, таких, что /, /2. Между множеством всех различных цепочек множеств /, .../, сR, /( = / + 1, / = 1,/, 1 / г-1 и множеством [jDk существует соответствие, задаваемое следующим образом: цепочке /, 1... QI, соответствует набор i„...,/,+, из Dl+l, { ,,/2} = /,, ix i2, {ij} = Ij_x\Ij_2, j = 3,/ + 1. Легко убедиться, что такое соответствие взаимно однозначно: для набора /,,..., 4, удовлетворяющего указанным условиям, положим /, = { ",, /2}, /2 = /, u{z 3}, I3 = I2 J{i4}, ..., Ік_х = 1к_2u{ik}. Теперь неравенства (4) можно записать в таком виде: Отметим, что. неизвестные, участвующие в неравенствах (5), и неизвестные, участвующие в неравенствах (3), образуют непересекающиеся множества. Поэтому МНГ-систему можно разделить на две независимые СЛН: всех решений СЛН (6); линейная функция Xj имеет максимум С2 (г) на /сЯ,/; 2 множестве решений системы (7). В этом случае функция г(х7, I с R, I = 0) равна своему максимальному значению С(г) на некотором решении х п I с R, 7 0 МНГ-системы тогда и только тогда, когда: Легко видеть, что сумма всех неизвестных СЛН (6) принимает свое максимальное значение на решении x {i)=\, i-\,r. То есть максимум существует, причем Сх(г) = г. f г \ С2(г) = 2 нежесткости (его можно найти, например, в монографиях [10, 20]). Для того, чтобы воспользоваться этим условием, необходимо рассмотреть двойственную задачу к задаче о нахождении максимума линейной функции т(хг, I czR,I Ф0) на решениях системы (7) (называемой «прямой» задачей). Двойственная задача определяется следующим образом: Воспользуемся теоремой о дополняющей нежесткости ([10]). Согласно этой теореме функция Е xi принимает свое максимальное значение на некотором решении х), IczR, 2 системы (7) и функция двойственной задаче тогда и только тогда, когда: если при каких-то кє2,г, (/,,...,4)єDk выполнено . / , Фк-\, то Д г„д) =0, и, если для какого то множества / с Л, / 2 выполнено J] М/,,..,/ ) 1» то д:) = 0. Укажем значения х), Ic:R, / 2 и j ( /(.)5 ( ..,,і,)єД, / = 2,г и проверим, выполняется ли для них условие дополняющей нежесткости. Положим: для всех множеств /с/?, таких, что 2 / JCJ=0;
Правила вывода, использующие основание графа
В этом параграфе приведены правила вывода, использующие свойства основания графа. Правило 2 (Складывание графов). Пусть даны два графа G и F. Объединим графы G и F. Добавим в полученный граф вершину а и ребра таким образом, чтобы множество вершин графа {O)KJTG JTF оказалось основанием графа (то есть соединим каждую из вершин этого множества ребром с каждой вершиной графа). Утверждение 1. Пусть Кх, ..., Ks - все максимальные клики графа G и Ц, ..., Lt - все максимальные клики графа F. Применим к графам G и F правило 2. Тогда список всех максимальных клик полученного графа Н будет следующим: Kx\j{a} JTF, ..., KSKJ{O)KJTF, L,u{a}u7J;, ..., Ltu{a}uTG. Кроме того, если графы G и F — МНГ графы с непустыми основаниями, то граф И— МНГ граф с непустым основанием. Доказательство. Список всех максимальных клик графа Н получается из описания правила 25. Пусть g, и g2 - несмежные вершины графа G и flf f2 - несмежные вершины графа F. Тогда, поскольку G и F - МИГ графы, то в графе G существует гамильтонова цепь g0ggx ив графе F существует гамильтонова цепь fQ f fx. Докажем, что любые две несмежные вершины в графе Н соединены гамильтоновой цепью. Для этого без ограничения общности достаточно доказать, что в Н пары вершин g0, f0 и g0, g, соединены гамильтоновой цепью. В первом случае искомая цепь выглядит так: gog S\af\f Л-Во втором случае отметим, что в цепи g присутствует вершина из основания графа G (поскольку TG непусто; вершины g0, g, несмежны, поэтому ни одна из них не лежит в основании графа G). Тогда запишем цепь g следующим образом: где вершина z лежит в основании графа Н. Тогда искомая гамильтонова цепь между вершинами g0 и g, имеет вид: Остается доказать, что граф Н негамильтонов. Предположим противное: существует гамильтонов цикл. Пусть х — вершина графа G, не лежащая в основании графа G. Гамильтонов цикл из вершины х в вершину х можно разбить на простые цепи: от вершины х через вершины графа G до некоторой точки основания Тн; от точки основания Тн до другой точки основания Тн, причем между точками основания проходим только через вершины либо графа G либо графа F; и так далее.
Последняя простая цепь идет от точки основания Тн через вершины графа G до вершины х. Переставляя эти простые цепи, можно привести указанную гамильтонову цепь к виду: где простые цепи gt состоят только из вершин графа G и не содержат точек из TG; простые цепи ft состоят только из вершин графа F и не содержат точек из TF; вершины tt,t t принадлежат основанию графа Н, причем несколько первых элементов в последовательности /,, ..., tk, t[, ..., t r лежат в TG, а оставшийся хвост в TF. Заметим, что в цепи (19) число г может быть равно 0. Предположим, что & 7Jj. Тогда граф G гамильтонов, поскольку существует гамильтонова цепь: где tA,...,tk и Т - все вершины из TG. Получаем противоречие с тем, что G -МНГграф. Предположим, что к \TG\. Тогда г \TF\ ив этом случае цепь из TF, является гамильтоновым циклом в графе F. Противоречие с тем, что F—МНГ граф. Из описания правила 2 легко видеть, что основание Н непусто. Утверждение 7 доказано. Пример. На рис. 4 правило 2 применяется к двум экземплярам МНГ графа порядка 3 (очевидно МНГ граф порядка 3 имеет непустое основание). Замечание. Правило 2 обладает свойством коммутативности, то есть результат не зависит от того, применяется ли правило к графам G и F или к графам F и G. Также правило 2 обладает свойством ассоциативности, то есть (G n2F)II1E = G П2 (F П2 Е), где G П2 F - операция применения правила 2 к графам G и F. Следовательно, можно применять правило 2 к конечному набору графов G,,..., Gs и результат не зависит от порядка применения. Условие утверждения 7 о непустых основаниях обоих графов F и Н неослабляемо. Пусть F и G - МНГ графы и Н - граф, полученный применением к графам Fu G правила 2. Если Н— МНГ граф, то в этом графе существует гамильтонова цепь, соединяющая несмежные вершины g0 и gx из графа G (две вершины несмежны в G тогда и только тогда, когда они несмежны в Н). В доказательстве утверждения 7 показано, что тогда эту цепь можно записать в виде (18): где вершина z принадлежит основанию графа Н, в цепи g и g" входят все вершины графа G, за исключением вершин g0 и g, и, возможно, вершины z, и в цепь f входят все вершины из графа F, кроме, возможно, z.
Если основание графа G пусто, то вершина z лежит в основании графа F и, поэтому, в графе F существует гамильтонов цикл Получаем противоречие. Таким образом, предполагая, что основание хотя бы одного из МНГ графов F и G пусто, получаем, что граф Н не может являться МНГ графом. Правило 3 (Добавление конструкции). Пусть дан граф G. Добавим вершину а и соединим ее ребрами со всеми вершинами графа G. Затем добавим вершину Ь и соединим эту вершину ребрами со всеми вершинами из множества {a} U TG. Утверждение 8 (прямое утверждение для правила 3). Пусть Кх, ..., Кг - все максимальные клики графа G. Применим к графу G правило 3. Тогда список всех максимальных клик полученного графа Н будет следующим: KiKj{a), ..., KrKj{a), {a,b}\jTG. Кроме того, если G является МНГ графом с непустым основанием, то граф Н также является МНГ графом с непустым основанием. Доказательство. Из описания правила 3 видно, что вершина а графа Н лежит в основании Тн, которое, следовательно, непусто. Докажем, что Н — МНГ граф. Пусть G — МНГ граф и основание G непусто. Тогда для любых двух несмежных вершин х0, х, графа G существует гамильтонова цепь х0 Т я:,. Поскольку х0, х{ очевидно не лежат в основании G и Та непусто, то цепь Т имеет вид t{ z t2, где z — вершина, принадлежащая основанию графа G. Тогда в Н существует гамильтонова цепь из х0 в л:,
Правила вывода, использующие опорные и соединительные клики
В этом параграфе основным элементом для построения правил вывода являются опорные и соединительные клики. Правило 6 (Добавление пары опорных клик). Добавим в максимальную клику К графа G две собственные вершины ах,а2. Далее добавим еще две вершины Ьх и Ь2 в граф и соединим ребрами вершину Ьх с вершинами из TG и вершиной а{; вершину Ь2 с вершинами из Тс и вершиной а2. Затем добавим в основание полученного графа вершину d (то есть добавим вершину d и соединим ее ребрами со всеми вершинами графа, в том числе и с вершинами al,a2,b1,b2). Утверждение 13 (прямое утверждение для правила 6). Пусть Кх, ..., Kt - все максимальные клики графа G. Применим к графу G правило 6, взяв в качестве клики К клику Кх. Тогда список всех максимальных клик полученного графа Н будет следующим: KX\J{ax a2,d}, {ax,bx,d} JTG, {a2,b2,d}uTG, K2Kj{d}, K3v{d}, ..., Ktu{d}. Кроме того, если G - МНГ граф, К — соединительная и проходная клика, то Н — МНГ граф, клика KKj{ax,a2,d) - проходная клика. Доказательство. Предположим, что в Н существует гамильтонов цикл. Заметим, что в графе Н максимальная клика Ku{ax,a2,d} является соединительной кликой, которая соединяет, в частности, опорные клики {ax,bx,d}LJTG, {a2,b2,d} jTG. Поскольку вершина bt смежна только с вершиной а; и всеми вершинами основания графа Н, то существует гамильтонов цикл, который содержит отрезок ах bx z, или отрезок z, bx ах, а также отрезок а2 b2 z2 или отрезок z2 Ъ2 а2, где z,, z2 - вершины основания графа Н (не обязательно различные). Действительно, если цикл не содержит отрезков ах bx zx и zx bx ах, то он содержит отрезок k ах k , где к, к лежат в клике К и отрезок zbxz , где z, z лежат в Тн. Тогда заменим отрезок к ах к отрезком к к (вершины к, к смежны, так как принадлежат одной клике) и отрезок z bx z отрезком z ах bx z . Получившийся цикл содержит отрезок ах bx z,, где zx из основания графа Н. Если в полученном цикле нет одного из отрезков а2 b2 z2, z2 Ъ2 а2, то поступим аналогичным образом, при этом очевидно, что отрезок ах bx zx останется в цикле. По условию существует некоторая опорная клика L графа G, которая имеет непустое сильное пересечение с кликой К.
Пусть вершина л: -собственная вершина L (собственная вершина в опорной клике существует по пункту 2 леммы 3). Доказано, что существует гамильтонов цикл, который содержит один из отрезков ах bx z, и zxbx я,, а также один из отрезков а2 b2 z2 и z2 b2 а2, где z,, z2 - вершины из основания графа Н (не обязательно различные). Запишем этот гамильтонов цикл, начиная с вершины х. Цикл может записываться одним из четырех способов: где z, z,, z2 - вершины, принадлежащие основанию графа Я и z,, z2 различны. Без ограничения общности будем считать, что в случае (43) вершина z совпадает с вершиной d, а в случаях (44)-(46) z2 совпадает с d. Покажем, что каждому из вариантов (43)-(46) гамильтонова цикла в графе Н соответствует гамильтонов цикл в графе G. В случае (43): В случае (45) заметим, что в цепи t3 х tx есть вершина, которая принадлежит основанию графа G, поскольку L - опорная клика, то есть сильно пересекается только с кликой К, причем в сильном пересечении лежит одна вершина (по пункту 1 леммы 4). Без ограничения общности предположим, что вершина в пути tx лежит в TG. Тогда ТХ=Х zl?, где z лежит в TG, причем последняя вершина в цепи tx лежит в клике К. Следовательно, существует гамильтонов цикл в графе G: В случае (46) рассуждаем следующим образом. Если в цепи Т2 есть вершина v из основания Тн, то отрезок от вершины z, до вершины v можно записать в обратном порядке, приведя тем самым цепь к виду (44), и, согласно показанному выше, построить гамильтонов цикл в графе G. Если в цепи /2 есть хотя бы одна собственная вершина опорной клики L, то в цепи t2 также присутствует хотя бы одна точка основания Тн. Пусть, теперь, в цепи Т2 нет собственных вершин клики L. Обозначим вершину, лежащую в сильном пересечении клик К и L как вершину д. Если цепь Т2 содержит вершину q, то она содержит также отрезок kxqk2, где кх и к2 лежат в клике К. Заменяя этот отрезок в цепи (46) на кх к2, а отрезок хТх отрезком xqTx, получаем цепь также вида (46), но не содержащего q в цепи t2. Без ограничения общности положим, что вершина q лежит в цепи Тх. Далее, если цепь xTxzx не содержит ребро из клики К, то она содержит отрезок Тqs z , где цепи J, У состоят только из собственных вершин клики L и вершина z лежит в основании графа Н. Тогда заменим отрезок Jqfz отрезком Ts qz и получим гамильтонову цепь в графе Н вида (46), такую, что цепь Тх содержит ребро из клики К, то есть представляется в виде Tx = tx кх к2 t2 , где вершины кх и к2 лежат в клике К. Тогда существует гамильтонов цикл в графе G вида Поскольку граф G — МНГ граф, получаем противоречие. Таким образом, граф Н— негамильтонов. Пусть х, у — две несмежные вершины графа G. Поскольку G — МНГ граф и клика К - проходная, то существует гамильтонова цепь, содержащая ребро из К:
