Максимально негамильтоновые графы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ОГЛАВЛЕНИЕ.

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ И ОБЗОР ЛИТЕРАТУРЫ.

Глава I. СВОЙСТВА СТРУКТУРЫ МАКСИМАЛЬНЫХ КЛИК

МАКСИМАЛЬНО НЕГАМИЛЬТОНОВЫХ ГРАФОВ.

§1. Собственные вершины максимальных клик и сведение к упрощенным

МНГ графам.

§2. Построение МНГ-системы.

§3. Оценка порядков и числа упрощенных МНГ графов.

Выводы.

Глава И. ПРАВИЛА ВЫВОДА МАКСИМАЛЬНО НЕГАМИЛЬТОНОВЫХ

ГРАФОВ.

§ 1. Свойства некоторых элементов МНГ графов.

§2. Правила вывода, использующие основание графа.

§3. Правила вывода, использующие промежуточные клики.

§4. Правила вывода, использующие опорные и соединительные клики.

§5. Цепочки правил вывода.

Выводы.

Задача поиска простой остовной цепи в графе1 изучается уже около 150 лет (впоследствии такая цепь получила название гамильтонова цикла). В работе [38] можно найти цитаты из письма Гамильтона (W.R.Hamilton), в котором описана такая игра: первый игрок отмечает в додекаэдре путь из пяти идущих друг за другом вершин, а второй игрок должен дополнить этот путь до простого цикла, проходящего через все вершины додекаэдра2.

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

Во многих прикладных задачах требуется построить гамильтонову цепь, а не цикл. Граф, содержащий такую цепь, иногда называют трассируемым ([5]). Задачи о гамильтоновом цикле и гамильтоновой цепи эквивалентны в том смысле, что, умея решать одну из них, мы смогли бы решить и другую (см. например [5]).

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

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

2 Гамильтон продал эту игру торговцу игрушками за 25 гиней - удивительный случай совмещения математической любознательности и практической сметливости. которых он способен выполнить после соответствующей настройки. При этом необходимо затратить t{. единиц времени для того, чтобы после выполнения /-го задания выполнить j-e. В предположении, что ti} - tj{, требуется найти последовательность выполнения заданий, при которой время каждой переналадки не превосходит величины t. Если построить граф G, у которого множество вершин есть {1,2,.,«} и множество ребер есть

А У) «Чу » то наша задача сведется к отысканию гамильтоновой цепи в этом графе.

Возникает также задача о гамильтоновом цикле в случае «взвешенного» графа, то есть когда каждому из ребер графа приписано некоторое число («вес» ребра). Математически это выглядит так: в полном взвешенном графе требуется найти гамильтонов цикл минимального веса. Так называемая «задача о коммивояжере» является примером подобной прикладной задачи. Она состоит в следующем: коммивояжер должен побывать в каждом из заданных п городов по одному разу, начав от одного из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между любой парой городов. Легко показать, что замена в задаче о коммивояжере гамильтонова цикла на гамильтонову цепь не облегчает решение задачи.

Таким образом, вопрос построения простого (легко проверяемого) критерия гамильтоновости графа имеет важное практическое значение. Однако, несмотря на усилия многих математиков, в течение долгого времени такой критерий построить не удавалось. Более того, получен следующий результат.

Теорема 1. Задача о нахождении гамильтонова цикла NP-полна. Оригинальное доказательство этой теоремы можно найти в [7]. Таким образом, в предположении, что РфЫР, невозможно построить критерий существования гамильтонова цикла, проверяемый за полиномиальное время.

Поэтому весьма активно разрабатываемым направлением теории графов стало изучение достаточных или необходимых условий гамильтоновости графов. Следует отметить результат, известный как теорема Поша ([42]).

Теорема 2. Пусть граф G имеет р> 3 вершин. Если для всякого п, \< п <(р -1)/2, число вершин со степенями, не превосходящими п, меньше чем п, и для нечетного р число вершин степени (р —1)/2 не превосходит (р —1)/2, то G — гамилътонов граф.

Приведенное достаточное условие не является необходимым. Однако условия теоремы неулучшаемы, поскольку при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа (примеры графов, иллюстрирующих сказанное, можно найти в работе Харари [22]). Из теоремы Поша легко следуют более простые, но менее сильные достаточные условия, найденные Оре ([40]) и Дираком ([32]) соответственно.

Теорема 3. Если р> 3 и degw+degv>для любой пары w и v несмежных вершин графа G порядка р, то G — гамилътонов граф.

Теорема 4. Если р>3 и degv> р/2 для любой вершины v графа G, то G — гамилътонов граф.

Эти достаточные условия накладывают ограничения на степени вершин и, тем самым, на количество ребер в графе; но можно наложить ограничения на число ребер и напрямую. Следующий результат получен Оре ([39]).

Теорема 5. Если в графе G р> 3 вершин и q> (р2 - Ър + 6)/2 ребер, то G — гамилътонов.

Приведенная теорема подтверждает интуитивное соображение: граф, содержащий много ребер, «предрасположен» быть гамильтоновым. Кстати, подобного нельзя сказать о негамильтоновых графах, поскольку уже для п > 3 существует гамильтонов граф порядка п, содержащий всего п-1 ребро.

Очевидно, что односвязный граф не может быть гамильтоновым. В тоже время не все двусвязные графы гамильтоновые. Тэта-графом называется блок (связный граф, не имеющий точек сочленения), содержащий только вершины степени 2 и две вершины степени 3.

Теорема 6. Каждый негамилыпонов двусвязный граф содержит тэта-подграф.

Доказательство этой теоремы можно найти в книге [5].

Существуют негамильтоновые графы сколь угодно большой связности. Однако, если к м-связности графа добавить условие планарности, то уже при т=3 такой негамильтонов граф построить сложно, а при т=4 вообще невозможно, что доказано в 1946 году Таттом ([21]). Наименьший (по количеству вершин) негамильтонов трехсвязный планарный граф, имеющий 11 вершин, построен Д. Барнеттом и Е.Юковичем в 1970 г.

Большое количество исследований касается условий наличия гамильтонова цикла в реберных графах. Вершинами реберного графа L{G) являются ребра графа G и две вершины L(G) смежны тогда и только тогда, когда смежны соответствующие им ребра графа G. Итерированный реберный граф определяется соотношением Ln(G) = L(L"~l(G)), п>2. Следующий результат получен Чартрэндом в работе [28].

Теорема 7. Если G — связный граф с р> 1 вершинами, не являющийся простой цепью, то граф Ln (G) гамилътонов для всех п> р — 3.

Это означает, что для почти каждого связного графа G почти все графы L"(G) гамильтоновые. Относительно самого реберного графа важным результатом явилась следующая теорема, доказанная в [35] Харари и Нэш-Вильямсом.

Теорема 8. Граф L(G) гамилътонов тогда и только тогда, когда граф G содержит замкнутую цепь, имеющую по крайней мере одну вершину, инцидентную каждому ребру графа G.

Из этой теоремы очевидным образом следует следующий результат.

Теорема 9. Если G — эйлеров или гамилътонов граф, то граф L(G) гамилътонов.

Кроме того, Мун доказал, что наименьшим блоком с негамильтоновым реберным графом является тэта-граф с 8 вершинами, в котором расстояние между любой парой вершин степени 3 равно трем.

Также интересные результаты получены по поиску гамильтоновых циклов в степенях графа. Для натурального числа k определим к-ю степень графа как граф Gk, в котором множество вершин то же, что и в графе G и различные вершины и и v смежны в Gk если и только если в G существует простая цепь, соединяющая и и v, длины не более к.

Теорема 10. (Караганис, [36]) Если граф G порядка п> 3 связен, то G3 - гамилътонов граф.

Теорема 11. (Флейшнер, [33]) Если G — двусвязный граф порядка п>Ъ, то G2 - гамилътонов граф.

Одной из нерешенных задач в области негамильтоновых графов остается подсчет точного числа как помеченных, так и непомеченных гамильтоновых графов. Перечисляющий ряд для непомеченных гамильтоновых графов начинается так: х3 + Зх4 + 8х5 + 48л:6 +.

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

Теорема 12. Отношение числа помеченных гамильтоновых графов порядка п к числу всех помеченных графов порядка п стремится к единице при п, стремящемся к бесконечности.

Это доказывает, что негамильтоновых графов немного. Тем не менее, построить негамильтонов граф любого заранее заданного порядка достаточно просто: любой несвязный или односвязный граф негамильтонов. В то же время проблема построения ш-связного негамильтонова графа большого порядка (такого большого, что случайный поиск во множестве всех графов неэффективен по причине высокой трудоемкости) становится достаточно сложной. Получено сравнительно много результатов, касающихся необходимых условий негамильтоновости; например, стоит выделить теорему (см. [6]).

Теорема 13. В графе без гамильтоновых циклов длина его длиннейших простых цепей удовлетворяет неравенству

1>рг+р2, где рхи р2 - две наименьшие локальные степени.

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

Рассмотрим алгоритмы проверки гамильтоновости графа. Существует два основных типа таких алгоритмов: переборные и эвристические. Переборные алгоритмы всегда находят гамильтонов цикл в графе или доказывают, что его нет; алгоритмы второго типа работают гораздо быстрее, но могут вообще говоря и не найти существующий гамильтонов цикл3. Подробный обзор известных алгоритмов обоих типов и их последних модификаций можно найти в представленной в 1998 году диссертации Вандегринда [48].

Коротко опишем переборные алгоритмы поиска гамильтонова цикла, наиболее часто используемые на практике. Простейшим способом убедиться в наличии или отсутствии гамильтонова цикла в графе является перебор всех п\ перестановок вершин. Однако возможно построить алгоритмы, имеющие заметно меньшую по сравнению с п\ сложность (хотя и экспоненциальную в худшем случае). Таким алгоритмом является, например, способ Робертса и Флореса [43, 44], использующий принцип «поиска в ширину». Этот способ не предъявляет чрезмерных требований к памяти компьютера, но его трудоемкость зависит экспоненциально от числа вершин в графе практически для любого графа. Другой неявный метод перебора - мультицепной метод (MultiPath algorithm) имеет для большинства типов графов очень небольшой

3 К эвристическим алгоритмам относятся также и приближенные алгоритмы, которые ищут циклы большой длины в графе, но при этом необязательно находят самый длинный цикл. показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. Впервые мультицепной метод предложен в работе Селби [46]. Далее мультицепной метод модернизировался много раз: первое развитие метода можно найти в монографии Кристофидеса [8] (1978 год), одна из последних на настоящий момент модернизаций приведена в статье [37] (1992 год). Также отметим сравнительно новый метод поиска гамильтонова цикла - КТС-алгоритм, построенный в работе [25] Шафелтом и Берлинером. Этот метод перебирает возможные короткие пути в графе и определяет, пользуясь 26 правилами, предложенными авторами, может ли проверяемый путь содержаться в каком-нибудь гамильтоновом цикле. КТС-алгоритм представляется достаточно сложным для реализации, однако сам подход кажется весьма перспективным. К алгебраическим методам поиска гамильтонова цикла можно отнести методы, включающие в себя построение всех простых цепей графа с помощью последовательного перемножения матриц. Такой подход использовался в работах Иоу, Даниэльсона, Дхавана [49, 30, 31]. Алгебраические методы определения гамильтоновых циклов не могут быть применены к задачам с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера.

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

4 То есть не содержащий ребер. ребрами генерируется с вероятностью ч2у v т У

Такая процедура построения графа называется Gnm -моделью. Существует эвристический алгоритм поиска гамильтонова цикла UHC, предложенный в работе [24]. Если m>c-n-\ogn, где с>3 — некоторая константа, не зависящая от п, и граф получен при помощи Gnjn -модели, то надежность алгоритма UHC равна l-o(l) при и->оо. Трудоемкость алгоритма оценивается как o{n-(\ogrif^. Другая процедура построения графа: вероятность возникновения каждого ребра в графе с п вершинами равна р. Эта процедура называется G -моделью.

Вероятность получить какой-либо граф с q ребрами для такой модели

Gb составляет pq • (1 - ру J . Эли Шамир в статье [47] построил алгоритм, который на графах, сгенерированных при помощи G -модели, при р = — -(logw + c-loglogw), находит решение с трудоемкостью и надежностью l-o(l) при п—»оо.

Задача вычисления максимальной трудоемкости для существующих переборных алгоритмов проверки гамильтоновости является весьма сложной: для большинства методов (включая и вышеописанные переборные алгоритмы) она остается нерешенной. В этом случае допустимо использовать экспериментальные данные, однако возникает проблема построения графов, на которых предложенные методы имели бы трудоемкость, близкую к максимальной. В работе [48] в качестве решения предлагался следующий подход: рассматривался какой-нибудь алгоритм поиска гамильтонова цикла и, исходя из особенностей этого алгоритма, строились «сложные» графы, на которых именно этот алгоритм работает сравнительно долго (то есть с трудоемкостью, близкой к максимальной). Однако в этой же работе указаны и недостатки такого подхода: во-первых, алгоритм нетрудно модифицировать, чтобы он на предложенных графах работал заметно быстрее; во-вторых, как правило другие алгоритмы со «сложными» графами справляются без труда. Предложим другой подход: станем использовать для получения экспериментальных оценок трудоемкости переборных алгоритмов в худшем случае максимально негамильтоновые графы (в такой граф нельзя добавить ребро без нарушения его негамильтоновости). В статье [29] Кристофидес утверждает, что проще найти гамильтонов цикл в графе, имеющем такой цикл, чем доказать, что не существует никакого гамильтонова цикла в графе, его не имеющем. Поскольку все известные переборные алгоритмы поиска гамильтонова цикла (за исключением полного перебора) зависят от числа ребер в графе, то можно предположить, что максимально негамильтоновые графы являются наиболее трудоемкими для проверки (или по крайней мере трудоемкости на таких графах будут близкими к максимальным значениям практически для всех переборных алгоритмов). Некоторые экспериментальные данные, свидетельствующие в пользу этой гипотезы, приведены в приложении 2. Следовательно, такие графы необходимо изучать, в частности, необходимо научиться строить их для произвольного порядка. Максимально негамильтоновые графы, их свойства и методы построения, и являются основным предметом исследования диссертации.

Исследования указанного класса графов ведутся достаточно давно, в частности, важным результатом является доказательство в 1972 году Бонди [26] следующей теоремы.

Теорема 14. При заданном числе вершин пФ 5 негамильтонов граф с наибольшим числом ребер только один (с точностью до изоморфизма).

Отметим, что при п—5 таких графов два.

Несложно построить и другие максимально негамильтоновые графы порядка п — достаточно воспользоваться графом, список всех максимальных клик которого выглядит следующим образом: одна клика порядка п-к и одна клика порядка к+1, причем пересекаются эти клики по одной вершине. Как видно такой граф имеет достаточно бедную структуру максимальных клик -настолько, что установление его негамильтоновости осуществимо за полином от п.

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

Вообще говоря, максимально негамильтоновые графы относятся к классу так называемых максимальных графов исключения (см., например, [9, 41]). Для класса максимальных графов исключения при условии сингулярной связности вводятся правила для получения любого такого графа из другого максимального графа (собственно словосочетание «правила вывода МНГ графов», использующееся далее в тексте диссертации, взято по аналогии с указанной теорией). Однако свойство сингулярной связности не выполняется для максимально негамильтоновых графов (хотя бы потому, что такие графы не обязательно имеют одно и то же количество ребер), и поэтому результаты, доказанные в общем случае, слабо применимы для изучения максимально негамильтоновых графов.

Рассмотрим полный граф К1п на п вершинах. В этом графе содержится остовный подграф G. Предположим, что граф G нам неизвестен и нам требуется проверить существование гамильтонова цикла в G, пользуясь возможностью задавать следующие вопросы: принадлежит ли ребро (v, w) графу <j? Задачи такого рода рассматривались в работах [4, 23, 34]. Возможность строить, если не все, то хотя бы большой класс максимально негамильтоновых графов порядка п, позволяет упростить решение задачи, проверяя указанными тестами следующее: является ли граф G остовным подграфом в одном из известных максимально негамильтоновых графах.

Сказанное можно считать одним из обоснований актуальности приведенных в предлагаемой работе результатов. Кроме того, укажем еще одно прикладное применение максимальных негамильтоновых графов. Существует большое количество задач, в которых требуется построить граф, имеющий гамильтонову цепь между любыми двумя несмежными вершинами (например, задача построения сети дорог между п городами так, чтобы между любыми двумя городами, не связанными прямой дорогой, существовала дорога, проходящая через все остальные города по одному разу). Такой граф не обязательно является максимально негамильтоновым, то есть в нем может существовать гамильтонов цикл. Тем не менее, мы можем использовать максимальные негамильтоновые графы в качестве решения задачи; кроме того, наличие правил вывода МНГ графов позволит нам легко решить задачу о расширении сети дорог на п городах до сети на n + t городах.

Научная новизна теоретических положений, полученных автором, заключается в развитии таких направлений области максимально негамильтоновых графов, как: построение МНГ графов; сведения изучения МНГ графов к более узким классам; получения оценок мощности этих классов и ограничений, налагаемых на их элементы. Кроме того, введены новые содержательные понятия теории графов (упрощенные графы, проходные клики и другие), которые играют важную роль в описании максимально негамильтоновых графов, а также использованы методы из области максимальных графов исключения (правила вывода) для решения вопроса о генерации МНГ графов и методы линейного программирования для получения оценок на число и порядки упрощенных МНГ графов.

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

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

Диссертация состоит из введения, двух глав, двух приложений, заключения и списка литературы. Нумерация параграфов ведется независимо по главам. Нумерация формул, лемм, утверждений, теорем, таблиц и рисунков единая в рамках всего текста диссертации; в то же время в отдельных случаях для ясности перед номером может указываться номер главы: теорема 1.15 — теорема 15, сформулированная в первой главе.

Выводы.

Теперь можно сузить класс упрощенных МНГ графов, введенный в главе I. Дадим следующее определение.

Определение. МНГ граф, который не может быть получен применением правил 1-7 к какому-либо МНГ графу, называется атомарным МНГ графом.

Из утверждений 6, 9, 12 и 14, описывающих условия, при которых возможно обращение правил, легко следует следующая теорема.

Теорема 16. Атомарный МНГ граф G, имеющий порядок больше 3, обязан удовлетворять следующим свойствам:

1) граф G -упрощенный МНГ граф;

2) в графе G ровно одна конструкция;

3) между любыми двумя максимальными кликами графа G существует не более трех промежуточных клик;

4) максимальная клика графа G может соединять не более четырех опорных клик.

С использованием указанных ограничений экспериментально удалось найти два атомарных МНГ графа, приведенных на рис. 12.

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

Кроме того, экспериментально удалось установить, что для графов порядка до 10 включительно не существует атомарных МНГ графов, отличных от указанных.

Не удается получить более хорошие оценки на число и порядки атомарных МНГ графов, чем оценки на число упрощенных графов, приведенные в главе I. Однако надо отметить следующее: изучение произвольного МНГ граф порядка п можно (не зная списка всех максимальных клик этого графа) свести с полиномиальной от п сложностью к изучению МНГ графа меньшего порядка, который удовлетворяет ограничениям теоремы 16 (см. замечание к лемме 5).

В главе II предложен алгоритм генерации МНГ графов. Используя полученные результаты, можно построить достаточно большое количество МНГ графов порядка п для любого наперед заданного значения п с полиномиальной от п трудоемкостью. Кроме того, показано, что изучение всех МНГ графов можно свести к изучению достаточно небольшого класса атомарных МНГ графов (выражение «достаточно небольшой» следует понимать в том смысле, что найти атомарный МНГ граф заметно сложнее по граф G-j граф G

Рис. 12. сравнению с произвольным МНГ графом; на момент написания работы удалось найти всего два атомарных МНГ графа). Получены ограничения на структуру максимальных клик атомарного МНГ графа (теорема 16), проверяемые с полиномиальной от числа вершин трудоемкостью. В частности, доказано, что класс атомарных МНГ графов является подмножеством класса упрощенных МНГ графов.

ЗАКЛЮЧЕНИЕ

Гамильтоновые графы играют важную практическую роль в построении экономических схем товарооборота, при анализе ДНК в биологии, в вопросах организации и автоматизации производства, в электротехнике при проектировании электрических цепей и других прикладных областях. Поэтому литература, касающаяся гамильтоновых циклов, весьма обширна. Работы по этой тематике опубликовывали такие иностранные ученые, как Оре, Кристофидес, Татт, Харари, Чартрэнд, Дирак, Барнетт, Юкович, Караганис, Флейшнер, Бонди, Поша, Роберте, Флорес, Селби, Иоу, Даниэльсон, Дхаван, Мун; такие отечественные авторы, как Перепелица В.А., Зыков А.А., Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И., Гринберг Э.Я., Асанов М.О., Баранский В.А., Расин В.В., Дебрев Е.В. и многие другие. Вместе с тем следует отметить, что подавляющая часть работ изучает гамильтоновые графы (графы, заведомо содержащие простой остовный цикл).

Сформулируем основные выводы по результатам диссертации. Доказан ряд свойств, которые накладывают ограничения на взаимное расположение максимальных клик в максимально негамильтоновых графах. Получен алгоритм построения широкого класса максимально негамильтоновых графов, использующий принцип постепенного увеличения порядка МНГ графа путем изменением отдельных его элементов. Показана возможность сведения изучения класса всех МНГ графов к изучению более узкого класса упрощенных МНГ графов. Доказано, что некоторый набор числовых характеристик упрощенного МНГ графа, имеющего не более г максимальных клик, обязан являться решением системы линейных неравенств (МНГсистемы), задаваемой значением г. Используя свойства МНГ-системы удалось получить верхние оценки для порядков и числа упрощенных МНГ графов с фиксированным числом максимальных клик; в частности, получено, что число таких графов конечно. Также рассмотрена возможность дальнейшего сведения класса упрощенных МНГ графов к еще более узкому подклассу атомарных МНГ графов, однако более хороших оценок на их порядки и число не найдено. Получены ограничения на структуру максимальных клик атомарного МНГ графа порядка п, проверяемые за полиномиальное от п время. Вместе с тем экспериментальным способом удалось найти всего два атомарных МНГ графа (см. рис. 12) и проверено отсутствие других атомарных графов для порядков до 10 включительно. Приведен каталог МНГ графов порядка п для значений л от 3 до 9.

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

1. Асанов И.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск :НИЦ «Регулярная и хаотическая динамика», 2001, с. 270-277.

2. Гринберг Э.Я. Плоские однородные графы степени три без гамильтоновых циклов. -Латв. матем. ежегодник, т. 4, 1968, с. 51-58.

3. Гэри М. Джонсон Д. Вычислительные машины и труднорешаемые задачи.-М.:Мир, 1982.

4. Дебрев Е.В. Об одной задаче комбинаторного поиска. Дискретная математика, т. 4, выпуск 3, 2002, с. 8-17.

5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. -М.:Наука, 1990 г.

6. Зыков А.А. Основы теории графов. -М.:Наука, 1987 г.

7. Карп P.M. Сводимость комбинаторных проблем.- В сб.: Кибернетический сборник, новая серия, вып. 12.- М.:Мир, 1975, с. 16-38.

8. Кристофидес Н. Теория графов: алгоритмический подход. -М.: Мир, 1978 г.

9. Оре О. Теория графов. -М.:Наука, 1980, с. 117-133.

10. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. -М.:Мир, 1985, стр. 72-77.

11. Ролдугин П.В. Максимально негамильтоновые графы. В сб.: Третий Всероссийский симпозиум по прикладной и промышленной математике. Тезисы докладов. М.: ТВП, 2002, с. 238-239.

12. Y1. Ролдугин П.В. Системы линейных неравенств для максимально негамильтоновых графов. Вестник Московского государственного университета леса. Лесной вестник, №1 (26), 2003, с. 97-102.

13. Ролдугж П.В. О числе максимально негамильтоновых графов. — Математические заметки (в печати).

14. Ролдугин П.В. Метод генерации максимально негамильтоновых графов. Вестник ИКСИ, серия «К», М.: Академия ФСБ России, 2003, с. 162169.

15. Ролдугин П.В. Построение максимально негамильтоновых графов. — Дискретная математика, т. 15, выпуск 2,2003, с. 89-102.

16. Ролдугин П.В. О числе максимально негамильтоновых графов. — В сб.: V Международная конференция «Алгебра и теория чисел: современные проблемы и приложения». Тезисы докладов. Тула: Изд-во ТГПУ, 2003, с. 193.

17. Ролдугин П.В. О построении максимально негамильтоновых графов. — В сб.: V Международная конференция «Алгебра и теория чисел: современные проблемы и приложения». Тезисы докладов. Тула: Изд-во ТГПУ, 2003, с. 194.

18. Ролдугин П.В. Тарасов А.В. О числе биюнктивных функций, инвариантных относительно данной подстановки. — Дискретная математика, т. 4, выпуск 3, 2002, с. 23-41.

19. Сачков В.Н. Введение в комбинаторные методы дискретной математики.-М.:Наука, 1982, стр. 210-219.

20. Схрейвер А. Теория линейного и целочисленного программирования. -М.:Мир, 1991 г.

21. Татт У. Теория графов. -М.:Мир, 1988 г.

22. Харари Ф. Теория графов,-М.:Мир, 1973, с. 86-87.

23. AignerM. Combinatorial search. Wiley, Berlin, 1988.

24. Angluin D., Valiant L.G. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. System Sci., 18(2), 1979, pp.155-193.

25. Berliner H.J., Shufelt J.A. Generating Hamiltonian circuits without backtracking from errors. Theoretical Computer Science, 132 (1994), pp.347-375.

26. Bondy J. Variations on the Hamiltonian theme. Canad. Math. Bull., 14 (1972), № l,p. 57-62.

27. Bondy J., Jackson B. Vertices of small degree in uniquely Hamiltonian graphs. J. Combin. Theory Ser., B74 (1998), p. 265-275.

28. Chartrand G., Graphs with prescribed connectivities, в сб. Theory of Graphs (под ред. Erdos P., Katona G.), Akademiai Kiado, Budapest, 1968, pp. 6163.

29. Christofides N. Large scheduling problems with bivalent costs, The Computer J., 16 (1973), p. 263.

30. Danielson G.H. On finding the simple paths and circuits in a graph, IEEE Trans., CT-15 (1968), p. 294.

31. Dhawan V. Hamiltonian circuits and related problems in graph theory, M. Sc. Report, Imperial College, London, 1969.

32. Dirac G.A. Some theorems on abstract graphs, Proc. London Math. Soc., Ser. 3,2 (1952), 69-81.

33. Fleischner H. The square of every nonseparable graph is Hamiltonian, Bull. Amer. Math. Soc., 77 (1971), 1052-1054.

34. Grebinski V., Kucherov G. Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs. In: Proc. 5th Israel Symp. Theory of Computing and Systems. IEEE Press, 1997, pp. 166-173.

35. Harary F., Nash-Williams C. St. J. A. On Eulerian and Hamiltonian graphsand line-graphs, Canad. Mat. Bull., 8 (1965), pp. 701-709.

36. Karaganis JJ. On the cube of a graph, Canad. Math. Bull., 11 (1968), pp. 295-296.

37. Kocay W. An extension of the multi-path algorithm for finding Hamilton cycles. Discrete Mathematics, 101 (1992), pp.171-188.

38. Kruskal J.B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48-50, 1956.

39. Ore O. Arc coverings of graphs, Ann. Mat. Рига Appl., 55 (1961), 315-322.

40. Ore O. Note on Hamilton circuits. Amer. Math. Monthly, 67 (1960), 55.

41. Ore O., Motzkin T. Subsets and subgraphs with maximal properties. Proc. Amer. Math. Soc., v. 10 (1959), pp. 965-969.

42. Posa L. A theorem concerning Hamilton lines, Maguar Tud. Alad. Mat. Kutato Int. Kozl., 7 (1962), 225 226.

43. Roberts S.M., Flores B. An engineering approach to the travelling salesman problem, Man. Sci., 13 (1967), p. 269.

44. Roberts S.M., Flores B. Systematic generation of Hamiltonian circuits, Comm. of ACM, 9 (1966), p. 690.

45. Sahni S., Gonzalez T. P-complete approximation problems. Journal of the ACM, 23:555-565,1976.

46. Selby G. R. The use of topological methods in computer-aided circuit layout, Ph. D. Thesis, London University, 1970.

47. Shamir E. How many random edges make a graph Hamiltonian? Combinatorica, 3(1), 1983, pp. 123-131.

48. Vandegriend B. Finding Hamiltonian cycles: algorithms, graphs and performance. MSc Thesis, University of Alberta, Canada, 1998.

49. Yau S.S. Generation of all Hamiltonian circuits, paths and centres of a graph and related prolblems, IEEE Trans., CT-14 (1967), p. 79.