Курсовая работа: Логика и основы алгоритмизации в инженерных задачах

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

Пензенский государственный университет

Кафедра «Вычислительная техника»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по курсу «Логика и основы алгоритмизации в инженерных задачах»

на тему «Раскраска графа»

Выполнила: Мультяева И.И.

Приняли:

Николаева Е.А.

д. т. н., Пащенко Д.В.

Пенза 2017

Содержание

Введение

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

2. Теоретическая часть задания

2.1 Общие теоретические сведения

2.2 Описание алгоритма программы

3. Ручной расчёт задачи

4. Описание программы

5. Тестирование

Заключение

Список используемых источников

• Приложения

Введение

программа хроматический граф раскраска

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

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

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

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

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

Исходный граф должен задаваться матрицей смежности, при вводе должна выполняться проверка корректности введённых данных. Программа должна быть разработана для работы в операционной системе Microsoft Windows. Интерфейс приложения должен быть представлен в виде оконного приложения, так как он дает лучшее восприятие элементов управления на экране, делает приложение наглядным и понятным. Программа должна обеспечивать ввод и вывод данных; управление программой происходит при помощи мыши, ввод информации - при помощи мыши и клавиатуры.

В качестве среды разработки выбран программный продукт Microsoft Visual Studio 2010, для написания кода программы выбран язык C++. Он сочетает свойства как высокоуровневых, так и низкоуровневых языков. Синтаксис C++ унаследован от языка C, одним из принципов разработки было сохранение совместимости с C. С++ является языком программирования общего назначения, на нём разрабатывают программы для самых различных платформ и систем. C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования.

Задание выполняется в соответствии с вариантом №16.

2. Теоретическая часть задания

2.1 Общие теоретические сведения

Задача раскраски вершин (поиска хроматического числа) графа может быть решена точными или приближенными алгоритмами.

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

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

Алгоритм раскраски вершин графа и нахождения хроматического числа имеет следующий вид:

- Шаг 1. Сортировать вершины графа по степеням убывания:

- deg(V_i) deg(V_j), V_i,V_j G;

- Установить текущий цвет k=1; i=1.

- Шаг 2. Выбрать очередную не раскрашенную вершину из списка и назначить ей новый цвет: col(V_i)=k; X_k={V_i}.

- Шаг 3. i=i+1. Выбрать очередную не раскрашенную вершину V_i и проверить условие смежности: V_i X_k = , где X_k - множество вершин, уже раскрашенных в цвет k. Если вершина V_k не является смежной с данными вершинами, то также присвоить ей цвет k:col(V_i)=k.

- Шаг 4. Повторить Шаг 3, пока не будет достигнут конец списка (i=n).

- Шаг 5. Если все вершины графа раскрашены, то - конец алгоритма;

- Хроматическое число графа ч (G)=k.

- Иначе: k=k+1; i=1, вернуться к Шагу 2.

2.2 Описание алгоритма программы

На рисунке 1 показана схема работы программы.

Рисунок 1. Схема работы программы.

На рисунке 2 показан алгоритм нахождения хроматического числа графа.

Рисунок 2. Схема алгоритма нахождения хроматического числа графа.

3. Ручной расчёт задачи

Рисунок 3. Исходный граф для ручного расчёта.

Рисунок 4. Матрица смежности графа.

Шаг 1. Выполним сортировку вершин в порядке убывания их степеней.

Устанавливаем текущий цвет k = 1;

Шаг 2. Присваиваем вершине 5 цвет k = 1. X_k={5}.

Шаг 3. Переходим к следующей неокрашенной вершине 1, проверяем на смежность с вершиной 5. Вершина 1 смежна с вершиной 5, поэтому ей нельзя присвоить цвет k = 1.

Шаг 4. Переходим к следующей неокрашенной вершине 2, проверяем на смежность с вершиной 5. Вершина 2 не смежна с вершиной 5, присваиваем ей цвет k = 1.

X_k={5, 2}.

Шаг 5. Переходим к следующей неокрашенной вершине 3, проверяем на смежность с вершинами 5 и 2. Вершина 3 смежна с вершиной 5 и вершиной 2, поэтому ей нельзя присвоить цвет k = 1.

Шаг 6. Переходим к следующей неокрашенной вершине 4, проверяем на смежность с вершинами 5 и 2. Вершина 4 смежна с вершиной 5 и вершиной 2, поэтому ей нельзя присвоить цвет k = 1.

Шаг 7. Переходим к следующей неокрашенной вершине 6, проверяем на смежность с вершинами 5 и 2 . Вершина 6 смежна с вершиной 5, поэтому ей нельзя присвоить цвет k = 1.

В цвет 1 окрашиваются вершины 2 и 5.

X_k=1={5, 2}.

Шаг 8. Устанавливаем текущий цвет k = 2.

Шаг 9. Переходим к первой из оставшихся неокрашенных вершин - вершине 1. Присваиваем вершине 1 цвет k = 2. X_k={1}.

Шаг 10. Переходим к следующей неокрашенной вершине 3, проверяем на смежность с вершиной 1. Вершина 3 смежна с вершиной 1, поэтому ей нельзя присвоить цвет k = 2.

Шаг 11. Переходим к следующей неокрашенной вершине 4, проверяем на смежность с вершиной 1. Вершина 4 не смежна с вершиной 1, присваиваем ей цвет k = 2.

X_k={1, 4}.

Шаг 12. Переходим к следующей неокрашенной вершине 6, проверяем на смежность с вершинами 1 и 4. Вершина 6 не смежна с вершиной 1, не смежна с вершиной 4, присваиваем ей цвет k = 2.

X_k={1, 4, 6}.

В цвет 2 окрашиваются вершины 1, 4 и 6.

X_k=2={1, 4, 6}.

Шаг 13. Устанавливаем текущий цвет k = 3.

Шаг 14. Переходим к последней оставшейся неокрашенной вершине - вершине 3. Присваиваем вершине 3 цвет k = 3. X_k={3}.

В цвет 3 окрашивается вершина 3.

X_k=3={3}.

Так как всем вершинам присвоен цвет, алгоритм раскраски графа завершён.

Хроматическое число графа ч (G)=3.

4. Описание программы

Разработанная программа состоит из двух модулей:

1. graph_colouring.cpp является основным модулем программы. Он содержит главную функцию main(), которая создаёт и запускает окно программы;

2. Form1.h является модулем описания главного окна программы, соответствует главной форме приложения.

Фрагменты листинга программы находятся в Приложении 1.

На рисунке 5 показано главное окно программы.

Рисунок 5. Главное окно программы.

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

На рисунке 6 показано главное окно программы с созданной матрицей и нарисованным графом.

Рисунок 6. Главное окно программы с созданной матрицей и нарисованным графом.

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

На рисунке 7 показано диалоговое окно выбора цвета.

Рисунок 7. Диалоговое окно выбора цвета.

После выбора каждого цвета пользователь может раскрасить вершины графа.

На рисунке 8 показан конечный результат программы.

Рисунок 8. Конечный результат программы.

5. Тестирование

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

На рисунке 9 показана реакция программы на попытку создания петли.

Рисунок 9. Реакция программы на создание петли.

На рисунке 10 показана реакция программы на ввод нечислового значения, притом пользователь не может редактировать остальные ячейки, пока не введёт числовое значение в ячейку.

Рисунок 10. Реакция программы на ввод нечислового значения.

На рисунке 11 показана реакция программы на превышение максимального числа вершин (не более 12).

Рисунок 11. Реакция программы на превышение максимального числа вершин.

Результаты работы программы на нескольких наборах входных данных показаны в Приложении 2.

Заключение

При выполнении данной курсовой работы была разработана программа, находящая хроматическое число заданного графа и показывающая, какие вершины в какой цвет окрашиваются. Были изучены алгоритмы раскраски графа и способ реализации одного из них на языке C++.

Список используемых источников

1. Брайан Керниган, Деннис Ритчи - Язык программирования Си,

2-еиздание, 2016.

2. Б. Пахомов. C/C++ и MS Visual С++ 2010 для начинающих.2011 г.

3. Библиотека Microsoft Developer Network.

4. Информационный ресурс на просторах интернета wikipedia.ru

5. Информационный ресурс на просторах интернета cyberforum.ru

Приложение 1. Листинг программы

Файл Form1.h

#pragma once

#include <string.h>

#include "stdafx.h"

#include <math.h>

namespace graph_colouring {

int mass[12][12];

int mass2[12][12];

int mass3[12][12];

int c = 0;

bool ns=0;

int t=0,m=0,h=0,n=0,k=0,s=0,d=0,b=0,ch=0,z=0,f=0;

int size=0;

int coords[12][2] = { {180,49},

{108,91},

{68,162},

{68,247},

{109,318},

{180,360},

{265,360},

{336,318},

{376,247},

{376,162},

{334,91},

{264,49},

};

struct graf{

int stepen;

int num;

int colour;

}versh[12];

int versh2[12] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

int x1,y1,x2,y2;

int proverka(int j,int n);

using namespace System;

using namespace System::ComponentModel;

using namespace System::Collections;

using namespace System::Windows::Forms;

using namespace System::Data;

using namespace System::Drawing;

#pragma endregion

void dataGridView1_CellValidating

(Object^ sender, DataGridViewCellValidatingEventArgs^ e)

{

int cellValue;

if (!Int32::TryParse(e->FormattedValue->ToString(),cellValue)

|| ((cellValue == '1') && (cellValue == '0')))

{

label14->Text = "Вводите только 0 или 1";

e->Cancel = true;

}

}

//функция show

private: void show(int size,int **mass){

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

for (int j=0;j < size; j++){

//вывод номеров столбцов

dataGridView1->Columns[j]->HeaderCell->Value = Convert::ToString(j+1);

//вывод номеров строк

dataGridView1->Rows[i]->HeaderCell->Value = Convert::ToString(i+1);

//вывод значений ячеек

dataGridView1->Rows[i]->Cells[j]->Value = mass[i][j];

}

}

}

//функция typing

private: void typing(int size,int **mass) {