Отчет 5

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра ВМиК

Отчёт

по лабораторной работе

«Нахождение эйлерова цикла в графе»

Выполнила: студ. гр. МО-204

Валиева Э.А.

Проверила:

Верхотурова Г.Н.

Уфа - 2014

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

Написать программу, реализующую алгоритм нахождения эйлерова цикла в заданном графе.

Входные и выходные данные:

matr-матрица смежных вершин

STEC-Промежуточный стек

CE-Результирующий стек

Алгоритм:

Теорема: Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем 2 вершины нечетной степени.

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

1. Делаем проверку на эйлеров цикл, считывая степень вершин графа. Если граф содержит не более чем 2 вершин нечетной степени, то «Эйлерова цикла нет». Иначе выполняем следующий шаг.

2. Делаем проверку на связность графа, используя алгоритм обхода в глубину, либо в ширину. Если количество задействованных вершин графа в обходе в глубину/ширину меньше, чем количество вершин графа, то «Граф не связный».

3. Помещаем начальную вершину в стек

4. Начинаем итерационный процесс:

   1. Получаем значение вершины стека

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

5. Процесс завершается, когда список становится пустым.

Реализация:

private void button6_Click(object sender, EventArgs e)

{

int N = dataGridView1.RowCount-1;

int[,] matr = new int[N, N];//Матрица смежных вершин

Stack<int> STEC = new Stack<int>(); //Промежуточный стек

Stack<int> CE = new Stack<int>();//Результирующий стек

bool flag1 = true;

int flag = 0;

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

O(N²)

if (dataGridView1.Rows[i].Cells[j].Value == null)

matr[i, j] = 0;

else matr[i, j] = 1;

flag = 0;

int degree = 0;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++)

if (matr[i, j] == 1)

O(N)

{

degree++;

}

if (degree % 2 != 0 || degree == 0)

{

textBox3.Text = "Нет эйлерова цикла";

flag1 = false;

break;

}

}

if (flag1 == true)

{

STEC.Clear();

CE.Clear();

int V = Convert.ToInt32(textBox4.Text) ;

int U = 0;

int K = 0;

flag = 0;

STEC.Push(V);

while (STEC.Count != 0)

{

K = STEC.Peek();

for (int i = 0; i < N; i++)

O(N²)

if (matr[K - 1, i] == 1)

{

flag = 1;

break;

}

if (flag == 1)

{

for (int i = 0; i < N; i++)

if (matr[K - 1, i] == 1)

{

U = i + 1;

matr[K - 1, i] = 0;

matr[i, K - 1] = 0;

break;

}

STEC.Push(U);

flag = 0;

}

else

{

U = STEC.Pop();

CE.Push(U);

}

}

}

for (int i =CE.Count ; i > 0; i--)

{

textBox3.Text = textBox3.Text + CE.Pop().ToString() + " ";

O(N)

}

string[] arrstring = textBox1.Text.Split(' ');

if ((arrstring.Length-1)<n)

{

textBox3.Text = "Не связный граф";

}

}

Оценка сложности: О(N²)

Вывод:

В ходе лабораторной работы я познакомилась с такими понятиями как эйлеров цикл, эйлеров путь.