ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.11.2023
Просмотров: 20
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
КУРСОВОЙ ПРОЕКТ
ТЕМА: ПОИСК ЭЙЛЕРОВОЙ ЦЕПИ ГРАФА
Руководитель
_________________________________________________________
подпись, дата
Исполнитель
студент ________________________________________________
подпись, дата
Тула 2023
Содержание
Содержание 2
Введение 2
2 Схема алгоритма 4
Данный раздел содержит схемы алгоритмов. 4
2.1 Пошаговый алгоритм и его словесное описание 4
2.1Схема алгоритма 5
3.1 Входные данные 6
3.2 Выходные данные 6
3Аспекты реализации на языке C# 6
5 Руководство пользователя 6
6.2 Тест второй 7
Заключение 8
Список использованных источников 9
Приложение А 10
Введение
Данная работа нацелена на проверку существования эйлерова цикла в графе.
Эйлеров цикл - это эйлеров путь, являющийся циклом.
Эйлеров путь (эйлерова цепь) в графе - это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Ясно, что эйлеров цикл содержит не только все ребра по одному разу, но и все вершины графа (возможно, по несколько раз). Очевидно также, что эйлеровым циклом может быть только связный граф.
1 Постановка задачи курсового проектирования
Разработка алгоритма и выполнение его программно для проверки существования эйлеровой цепи в графе.
2 Схема алгоритма
Данный раздел содержит схемы алгоритмов.
2.1 Пошаговый алгоритм и его словесное описание
Суть алгоритма, необходимого для решения задачи, в следующем. Пусть STACK – упорядоченное множество, которое будет содержать вершины графа, куда изначально помещается одна произвольная вершина. При каждой итерации вытаскиваем из STACK вершину и заносим в STACK все смежные с ней вершины, которые еще не занесены в массивaccess. Массив accessсодержит значения, которые указывают на достижимость i-той вершины графа. Повторяем эти действия до тех пор, пока STACKне пуст. Если все элементы accessистины, то следовательно можно добраться до каждой из вершин – граф связный. Далее проверяем количество ребер каждой вершины. Если у какой-либо вершины количество ребер нечетное, следовательно, по определению эйлерова цикла, он не существует, а если количество ребер четное, то эйлеров цикл существует.
- Схема алгоритма
Пусть V – число вершин в графе, mas – массив, содержащий матрицу смежности графа, Stack – массив, содержащий вершины эйлерова цикла. Access – массив, содержащий значения, которые указывают на достижимость i-той вершины графа. Схема алгоритма представлена на рисунке 1.
Рисунок 1 – Схема алгоритма
3 Описание структур данных
Данный раздел содержит описание основных структур данных, использованных в разработанном приложении.
3.1 Входные данные
V - количество вершин графа.
mas - матрица смежности графа.
3.2 Выходные данные
Переменная типа bool.
- Аспекты реализации на языке C#
Граф задается матрицей смежности. При реализации алгоритма были использованы: одномерные массивы (типа int и bool), переменные типа int, также используется Stack. Для ввода исходных данных используются: поле ввода NumericUpDown (для ввода количества вершин), таблица DataGridView (для ввода матрицы смежности). Полученные результаты выводятся на экран. Имеется возможность сохранять и открывать матрицу смежности в формате xml. Также предусмотрена функция случайного заполнения. Основные алгоритмы работы программы (программная реализация) приведена в приложении А.
5 Руководство пользователя
Данный раздел создан для пользователя программы поиска эйлерова цикла в графе.
Шаг 1. Вводим количество вершин в графе. Автоматически создается пустая матрица смежности.
Шаг 2. Заполнить матрицу смежности (вручную или при помощи случайного заполнения).
Шаг 3. Нажав кнопку «Проверить» выскакивает окно с ответом.
6 Тестовые примеры
Для тестирования алгоритма были созданы 2 графа.
6.1 Тест первый
Был создан граф с 4-мя вершинами. Эйлеров цикл в этом графе не существует. Матрица смежности и полученный результат на рисунке 2.
Рисунок 2 – Результат работы программы
6.2 Тест второй
Был создан граф с 6-ю вершинами. Эйлеров цикл в этом графе существует. Матрица смежности и полученный результат на рисунке 3.
Рисунок 3– Результат работы программы
Заключение
В данной курсовой работе разработан алгоритм, позволяющий проверить существования эйлерова цикла в графе, и его программная реализация на языке C#. В результате тестирования была проверена правильность работы разработанного алгоритма и созданного приложения.
Список использованных источников
1. Эйлеров цикл [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/wiki/Эйлеров_цикл
Приложение А
(обязательное)
private bool Way()
{
bool result = true;
Stack
bool[] access = new bool[V];
access[0] = true;
dots.Push(0);
while (dots.Count > 0)
{
int current = dots.Pop();
for (int i = 0; i < V; i++)
{
if (mas[current, i] != 0 && access[i] == false)
{
dots.Push(i);
access[i] = true;
}
}
}
foreach (bool b in access)
if (b == false)
result = false;
return result;
}
private void button2_Click(object sender, EventArgs e)
{
mas = new double[V, V];
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dataGridView1[j, i].Value != null)
mas[i, j] = Convert.ToInt32(dataGridView1[j, i].Value);
else
mas[i, j] = 0;
}
}
if (Way())
{
for (int i = 0; i < V; i++)
{
int kol = 0;
for (int j = 0; j < V; j++)
{
if (mas[i, j] != 0)
kol++;
}
if (kol % 2 != 0)
{
MessageBox.Show("Эйлеров цикл не существует");
return;
}
}
MessageBox.Show("Эйлеров цикл существует");
}
else
{
MessageBox.Show("Эйлеров цикл не существует");
}
}