лгоритмы построения гамильтоновых циклов в усеченных прямоугольных графах

Оглавление

Введение 3

Глава 1 Графы и алгоритмы обхода графов 4

1.1 Общие понятия теории графов 4

1.2 Алгоритмы обхода графов 4

Глава 2 Алгоритмы построения гамильтоновых циклов в усеченных прямоугольных графах 4

2.1 Гамильтова цепь и гамильтонов цикл в графе 4

2.2 Алгоритмы поиска гамильтонова цикла в усеченных прямоугольных графах 4

Заключение 4

Список использованных источников 4

Введение

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

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

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

Объект исследования – гамильтоновы циклы.

Предмет исследования – алгоритмы поиска гамильтоновых циклов в усеченных графах.

Цель работы – рассмотрение основных алгоритмов поиска гамильтоновых циклов в прямоугольных усеченных графах.

Для достижения поставленной цели необходимо решить следующие задачи:

1. Рассмотреть основные понятия теории графов;

2. Изучит основные алгоритмы обхода графов;

3 Рассмотреть понятия гамильтоновой цепи и гамильтонового цикла в графе;

4. Описать основные алгоритмы поиска гамильтонового цикла в прямоугольных усеченных графах.