Программирование метрических и количественных характеристик графа

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
(ФГБОУ ВО «КубГУ»)

Факультет математики и компьютерных наук
Кафедра вычислительной математики и информатики

КУРСОВАЯ РАБОТА

ПРОГРАММИРОВАНИЕ МЕТРИЧЕСКИХ И КОЛИЧЕСТВЕННЫХ ХАРАКТЕРИСТИК ГРАФА

Работу выполнил                                                                           Е. О. Филонцева
                                           (подпись)

Направление подготовки 02.03.01 Математика и компьютерные науки курс 2

Направленность (профиль) Вычислительные, программные, информационные системы и компьютерные технологии

Научный руководитель
кандидат физ.-мат.наук, доцент                                                   О. В. Иванисова
                                                    (подпись, дата)
Нормоконтролер
преподаватель                                                                                   А. А. Цыбенко
                                           (подпись, дата)

Краснодар
2019

СОДЕРЖАНИЕ

Введение        3

1 Постановка задачи        5

2 Анализ задачи        6

3 Обработчики событий, использованные для реализации алгоритма        12

4 Реализация алгоритма        13

5 Тестовые примеры        21

Заключение        23

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

ВВЕДЕНИЕ

Теория графов является одним из самых важных разделов дискретной математики.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Развитие теории графов в основном обязано большому числу всевозможных приложений. Из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.

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

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

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

-провести анализ поставленной задачи;

-изучить основные понятия теории графов;

-рассмотреть алгоритмы решающие поставленную задачу;

-разработать пользовательский интерфейс;

-разработать исходный код программы;

-выполнить тестирование программы.

В качестве средств реализации выбраны среда разработки Visual Studio и язык C#. Будет осуществлена визуализация задачи и решения с помощью Windows Forms. Исходные данные будут представлены в виде матрицы смежности, а также в программе будет предусмотрена возможность загрузки исходных данных из файлов и сохранения результатов работы в файл.

1 Постановка задачи

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