Основная образовательная программа cb. 5005. 2016 Прикладная математика, фундаментальная информатика и программирование
 Скачать 0.51 Mb.
|
|
Санкт-Петербургский государственный университет АПАЛЬКО Данил Фаддеевич Выпускная квалификационная работа Нахождение гамильтонова цикла с использованием методов решения линейных систем с применением модульного сложения Уровень образования: бакалавриат Направление 01.03.02 «Прикладная математика и информатика» Основная образовательная программа CB.5005.2016 «Прикладная математика, фундаментальная информатика и программирование» Профиль «Математическое и программное обеспечение вычислительных машин» Научный руководитель: профессор, кафедра информационных систем, д. ф.-м. н. Олемской Игорь Владимирович Рецензент: профессор, кафедра прикладной математики, д. т. н. Голоскоков Дмитрий Петрович Санкт-Петербург 2020 СОДЕРЖАНИЕ СОДЕРЖАНИЕ 2 ВВЕДЕНИЕ 4 1. ТЕОРИЯ ДЛЯ ОБОСНОВАНИЯ МЕТОДА 5 1.1. Основные определения 5 1.2. Циклическое пространство графа 9 1.3. Пространство разрезов 11 2. ПРАКТИЧЕСКАЯ ЧАСТЬ 15 2.1 Описание метода с применением теории 15 2.2 Формализация метода 20 2.3 Оценка алгоритмической сложности метода 22 ЗАКЛЮЧЕНИЕ 25 СПИСОК ЛИТЕРАТУРЫ 27 ПРИЛОЖЕНИЕ А 29 Реализации алгоритма на языке программирования Java, с использованием побитовых операций 29 ВВЕДЕНИЕ 3 1. ТЕОРИЯ ДЛЯ ОБОСНОВАНИЯ МЕТОДА 4 1.1. Основные определения 4 1.2. Циклическое пространство графа 8 1.3. Пространство разрезов 10 2. ПРАКТИЧЕСКАЯ ЧАСТЬ 14 2.1 Описание метода с применением теории 14 2.2 Формализация метода 19 2.3 Оценка алгоритмической сложности метода 21 ЗАКЛЮЧЕНИЕ 24 СПИСОК ЛИТЕРАТУРЫ 26 ПРИЛОЖЕНИЕ А 28 Реализации алгоритма на языке программирования Java, с использованием побитовых операций 28 ВВЕДЕНИЕ Задача о поиске и существовании гамильтонова цикла в простых графах является классической NP полной [4], которая известна своей теоретической и вычислительной сложностью. Несмотря на последние достижения в области теории графов, эта неопределенность представляет собой неизбежную проблему для теории алгоритмов. За последние десятилетия гамильтоновы циклы были достаточно хорошо изучены. А так же, благодаря своей вычислительной сложности, нашли применение в области криптографии и используются в системе так называемых протоколов с нулевым разглашением для передачи зашифрованной информации. Одним из направлений в исследованиях являются условия их существования. Большинство этих условий основаны на сумме степеней узлов графа. Их применение в методах нахождения гамильтонова цикла обычно требует большого количества ребер. Однако часто, если результаты имеют смысл - существуют контрпримеры среди аналогичного вида графов, когда эти условия ослаблены. Другое направление в решении задачи заключается в разработке случайных алгоритмов, которые обычно находят циклы Гамильтона с высокой вероятностью или успешно справляются с определенными классами графов. Целью и задачей данной работы является теоретическая постановка, обоснование и разработка метода по нахождению всех гамильтоновых циклов для класса разряженных графов с использованием свойств циклического пространства, а также практическая реализация алгоритма для наглядной проверки полученных результатов. 1. ТЕОРИЯ ДЛЯ ОБОСНОВАНИЯ МЕТОДА 1.1. Основные определения Пусть  — неориентированный граф определенный на множестве узлов  и множестве ребер  , где  ,  — соответственно количество узлов и ребер графа .Дальнейшее изложение будет вестись в предположении, что граф является простым — в котором нет кратных рёбер и петель, данное условие не обязательно и накладывается для удобства и лаконической составляющей доказательств. Итак, для теоретического обоснования нам понадобится ряд определений: |