Реферат на тему Гамильтонов граф. Задача коммивояжера. Метод ветвей и границ

Содержание:

Введение 3
Гамильтоновы циклы и графы 5
Задача коммивояжера. Метод «ветвей и границ». 9
Заключение 16
Список использованных источников 17

Введение:

ТЕОРИЯ ГРАФОВ — это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов — граф и его обобщения [2].
С помощью графов можно описать и решить множество конкретных практических задач, например:
— Задача о кратчайшей цепи
* замена оборудования
* составление расписания движения транспортных средств
* размещение пунктов скорой помощи
* размещение телефонных станций
— Задача о максимальном потоке
* анализ пропускной способности коммуникационной сети
* организация движения в динамической сети
* оптимальный подбор интенсивностей выполнения работ
* синтез двухполюсной сети с заданной структурной надежностью
* задача о распределении работ
— Задача об упаковках и покрытиях
* оптимизация структуры ПЗУ
* размещение диспетчерских пунктов городской транспортной сети
— Раскраска в графах
* распределение памяти в ЭВМ
* проектирование сетей телевизионного вещания
— Связность графов и сетей
* проектирование кратчайшей коммуникационной сети
* синтез структурно-надежной сети циркуляционной связи
* анализ надежности стохастических сетей связи
— Изоморфизм графов и сетей
* структурный синтез линейных избирательных цепей
* автоматизация контроля при проектировании БИС
— Изоморфное вхождение и пересечение графов
* локализация неисправности с помощью алгоритмов поиска МИПГ
* покрытие схемы заданным набором типовых подсхем
— Автоморфизм графов
* конструктивное перечисление структурных изомеров для производных органических соединений
* синтез тестов цифровых устройств
Целью данной курсовой работы является рассмотрение таких частных вопросов, как Гамильтоновы графы и одно из их применений – решение задачи коммивояжера.

Заключение:

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

Фрагмент текста работы:

Гамильтоновы циклы и графы
Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира [1, 3].
Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным.

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…, vp графа G добавить вершины u1, …, up и множество ребер {(vi, ui)} {(ui, vi+1)}.
Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) — по входящим.
Рассмотрим несколько достаточных условий существования гамильтоновых циклов в графе.
Во-первых, всякий полный граф является гамильтоновым. Действительно, он содержит такой простой цикл, которому принадлежат все вершины данного графа. Во-вторых, если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие ребра, то он также является гамильтоновым.