Читать реферат по математике: "Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов" Страница 1

(Назад) (Cкачать работу)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

По дисциплине «Дискретная математика»

студент группы

АСОиУзс-07-01

Быстров Евгений М.

Шифр: 742301020016500

Проверил

Гапанович И.В..

Задание на курсовую работу по дисциплине «Дискретная математика».

Студент группы АСОиУзс-07-01 Быстров Евгений М.

Специальность «Автоматизированные системы обработки информации и управления»

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов.

ЗАДАНИЕ 13. Построить гамильтонову цепь в графе, используя алгоритм с возвратом.

Определения.

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

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

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

Матрица смежности графа – квадратная матрица, показывающая взаимосвязь вершин и рёбер.

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

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

Для того, что сократить число шагов в предложенном методе, рассмотрим следующий алгоритм. Предположим, что решение имеет вид последовательности v1…vi. Идея метода состоит в следующем: решение строится последовательно, начиная с пустой последовательности (длины 0). Далее, имея

Похожие работы