Разработка программы поиска простого цикла графа

1.

{
Разработка
программы поиска
простого цикла
графа
Выполнил: студент группы ИНБб-2301-02-00
Т.С. Чебыкин
Киров, 2024

2.

Актуальность работы
Нахождение простого цикла
ориентированного графа с минимальным
средним геометрическим его ребер.

3.

Цель курсовой работы: разработка программы
поиска простого цикла графа и нахождение
минимального среднего геометрического весов
его ребер
Следует реализовать следующие задачи:
1.
ввод графа вручную;
2.
ввод графа с помощью матрицы смежности;
3.
графическое представление
ориентированного графа;
4.
поиск простого цикла с наименьшим
средним геометрическим весов
ориентированного графа;
5.
создание пользовательского интерфейса.

4.

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

5.

Поиск простого цикла
Краткое описание реализации алгоритма для разработки
программы:
1.
Проверяем наличие путей через промежуточные
вершины с меньшим средним геометрическим, которые
меньше чем среднее геометрическое прямого пути;
2.
Если такой путь найден, прямой путь заменяется путем
через промежуточные вершины;
3.
Проверяем наличие пути обратно в начальную вершину
из конечной (поиск цикла);
4.
Сравниваем среднее геометрическое найденного простого
цикла с переменной (изначально равной FLT_MAX). Если
значение меньше этой переменной, оно заменяет ее.

6.

Пользовательский интерфейс

7.

Задание графа с помощью рисования
графа

8.

Задание графа с помощью матрицы
смежности

9.

Графическое представление
ориентированного графа

10.

Выполнение алгоритма поиска простого
цикла

11.

Для проверки результата был выбран сайт
programfouyou.ru, где был задан аналогичный
граф

12.

Произведён поиск простого цикла.
Результаты совпадают.

13.

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

14.

Библиографический список
Карпов, Д.В. Теория графов: учебное пособие
URL:https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf (Дата
обращения: 01.12.2023)- Текст: электронный.
Алгоритм Флойда-Уоршелла
URL:https://cpp.mazurok.com/tag (Дата обращения:
01.12.2023) - Текст: электронный.
Как я простые циклы искал
URL:https://habr.com/ru/post/510174/ (Дата
обращения:02.12.2023) - Текст: электронный

15.

Спасибо за
внимание!!!