Реализация основных алгоритмов из теории графов

ВВЕДЕНИЕ

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

Ресурсы в моей игре были ограничены, поэтому дабы защитить, большинство жителей от отключения воды некоторые трубы укреплялись. Мне надо было узнать при поломке какой трубы, воду не получать большинство жителей. Однако я не смог даже реализовать обход по всем вершинам. Теперь я знаю, что мне поможет “Поиск в глубину”, тогда я этого не знал.

Я нашел решения этой задачи, однако для моего любимого языка программирования Python его не было, а в других я разбираюсь плохо, мне пришлось реализовывать его самим. Для сравнения результатов, мне необходимо было пользоваться онлайн сервисами подсчета подобных задач, и тут встала проблема, ввод графа был настолько не удобный, что я ошибался десятками раз. И бросил свой проект.

Взявшись за выбор темы курсовой работы, я вспомнил мой болезненный опыт, и решил создать программу с удобным вводом графов и их связей, а также реализовать базовые алгоритмы из “Теории графов” на языке Python. Это и есть цель курсовой работы.

Объект и предмет исследования: 

• Предмет исследования: раздел математики «Теория графов».
• Объект исследования: программа, написанная на языке Python.

Методы исследования: Анализ, синтез, диалектический метод, индукция, дедукция, научный метод.

Задачи, поставленные в данной курсовой работе:

• Изучить основы теории графов
• Изучить основы алгоритмизации
• Изучить правила построения блок схем
• Создать Блок-схемы алгоритмов.
• Реализовать алгоритмы
• Создать пользовательский интерфейс
• Провести тесты над программой

Структура работы:

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

Во второй главе, рассмотреть основной синтаксис Python, и реализовать основные алгоритмы, а именно алгоритма «Поиска в ширену», «Поиска в глубину», «Алгоритма Дейксры» для которых построить блок-схему и описать словесно.

В заключительной, объяснить работу программы. Рассмотреть работу кода с комментариями, и провести ряд тестов для проверки программы.  

1.1. Теория

1.1.1. Теория графов

Начало теории графов дал Леонард Эйлер. Эйлеру была предложена задача про семь кёнигсбергских мостов. Она звучала так: в городе Кёнигсберг было семь мостов, соединяющих два больших острова, окруженных рекой, и две части материка, разделенные той же рекой. (Рисунок 1)[pic 1][pic 2]

Нужно найти такой путь, чтобы пройти все мосты проходя только один раз. Эйлер пытался доказать, что такого пути нет. [pic 3][pic 4]

В современном представление это задача выглядит так (Рисунок 2):

Кружки или земля называються вершиной. А мосты или линии ребрами.

Строгое определение графа: Графов называется такая пара множеств  где V есть подмножество любого счетного множества, а E – подмножество ») [3, с. 35][pic 5][pic 6]

Граф бывает трех видов, ориентированный, неориентированный, смешанный.

Неориентированный граф представлен в рисунке 2. Неориентированный граф – это граф, ребра которого не имеют определенного направления. Смешанный имеет ребра обоих типов