Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Раскраска графа



Введение

Первые упоминания о раскраске графа и применении этой теории датируются 1852 годом. С тех пор теория претерпела множество изменений.

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

Задача раскраски графов была поставлена во многих областях применения. Раскраска вершин моделирует многие проблемы планирования. Алгоритм раскраски графа используется при распределении регистров и в технологии цифровых водяных знаков. Также решение головоломки Судоку можно рассматривать как завершение раскраски 9 цветами заданного графа из 81 вершины.



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

граф алгоритм раскраска

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

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

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

Программа должна быть разработана для работы в операционной системе Microsoft Windows. Средой разработки является Microsoft Visual Studio 2015. Язык программирования С++.

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

Пусть G - некоторый граф, k - натуральное число. Произвольная функция вида f: V > {1,2,…, k} называется вершинной k-раскраской или просто k-раскраской графа G. Раскраска называется правильной, если f(v)?f(u) для любых смежных вершин v и u. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым.

Алгоритм раскраски графа:

1. Выберем в графе G некоторое максимальное независимое множество вершин U (лучше наибольшее). Покрасим все вершины данного множества в один цвет.

2. Выберем максимальное независимое множество вершин U1 в графе G1, который получается из графа G удалением множества вершин U и всех инцидентных им ребер. Покрасим вершины множества U1 в очередной цвет.

3. Шаг 2 повторять до тех пор, пока в графе G не будут раскрашены все вершины.

На рисунке 1 приведен пример правильно раскрашиваемого графа.

Рисунок 1.- Граф G

3. Описание алгоритма поставленной задачи

Первоначально был разработан и протестирован алгоритм раскрашивания графа. Далее был разработан графический интерфейс, который позволил бы пользователю легко ориентироваться в программе. Для реализации задачи был выбран язык C++. В качестве среды программирования был выбран программный продукт Visual Studio 2013. Некоторые доработки были выполнены с помощью программного продукта Visual Studio 2010. Была создана функция InitInstance, создающая окно программы и заполняющая заголовки. Затем была создана функция LRESULT CALLBACK WndProc(), в которую был добавлен уже разработанный алгоритм построения вершин и ребер графа, действий при нажатии кнопок, а также алгоритм распределения цветов по вершинам.

4. Пример ручного расчета задачи и вычислений

На рисунке 2 изображен граф, выбранный для ручного расчета.

Рисунок 2. Граф для ручного расчета

Алгоритм расчета:

1. Берем вершины и раскрашиванием их в какие-либо цвета.

2. Берем первую вершину. Если какая-либо смежная ей вершина имеет такой же цвет, то меняем цвет взятой вершины.

3. Повторяем пункт 3, пока не будут раскрашены все вершины.

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

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

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

При запуске программы пользователя встречает окно с двумя кнопками. Кнопка «Generate» позволяет сгенерировать случайный граф и раскрасить его минимальным количеством цветов. Кнопка «Exit» выходит из программы.

Исходное состояние программы показано на рисунке 3.

Рисунок 3. Исходное состояние

6. Результаты работы

Результат работы программы представлен на рисунке 4 и 5.

Рисунок 4. Результат работы



Рисунок 5. Результат работы

7. Тесты

Программа Visual Studio 2013 была выбрана в качестве среды разработки. Для отладки программы были использованы такие инструменты тестирования как точка останова, выполнение кода по шагам, анализ содержимого локальных и глобальных переменных, анализ содержимого памяти.

В ходе тестирования было выявлено множество проблем связанных с работой алгоритма, построением графа и его раскраской. Было найдено и исправлено множество недоработок. На рисунке 7 показаны результаты тестирования.



Рисунок 6. Результат тестирования



Заключение

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

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



Список литературы

1. Электронный ресурс: stackoverflow.com.

2. Электронный ресурс: CyberForum.ru.

3. Электронный ресурс: wikipedia.org.

4. Зыков А.А. Основы теории графов.-М.:Наука, 1984 г.

5. Успенский В.А. Семенов А.Л. Теория алгоритмов: основные понятия и приложения.-М.: Наука, 1987 г.



Приложение

Листинги программы

Файл «L_CW.cpp»

#include «stdafx.h»

#include «L_CW.h»

BOOL InitInstance (HINSTANCE hInstance, int nCmdShow)

{

int XWndSize=800, YWndSize=600;

HWND hWnd;

hInst = hInstance;

hWnd = CreateWindow (

szWindowClass,

L» Raskraska grapha»,

WS_OVERLAPPEDWINDOW,

GetSystemMetrics (SM_CXSCREEN)/2-XWndSize/2,

GetSystemMetrics (SM_CYSCREEN)/2-YWndSize/2,

XWndSize, YWndSize,

NULL, NULL,

hInstance, NULL);

if (! hWnd)

{

return FALSE;

}

ShowWindow (hWnd, nCmdShow);

UpdateWindow(hWnd);

return TRUE;

}

LRESULT CALLBACK WndProc (HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)

{

int wmId, wmEvent;

PAINTSTRUCT ps;

HDC hdc;

switch (message)

{

case WM_COMMAND:

wmId = LOWORD(wParam);

wmEvent = HIWORD(wParam);

switch (wmId)

{

case IDM_N_3:

DrawN3=! DrawN3;

InvalidateRect (hWnd, NULL, true);

UpdateWindow(hWnd);

break;

case IDM_EXIT:

DestroyWindow(hWnd);

break;

default:

return DefWindowProc (hWnd, message, wParam, lParam);

}

break;

case WM_PAINT:

hdc = BeginPaint (hWnd, &ps);

if (DrawN3)

{

int M[7] [7];

TextOut (hdc, 2, 2, _T («Вывод графа с подкрашенными вершинами.»), strlen («Вывод графа с подкрашенными вершинами.»));

srand (time(0));

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

{

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

{

if (i == j) M[i] [j] = 0;

else

M[i] [j] = M[j] [i] = rand()% 2;

}

}

const int n = 7;

int kolvoEltov=7;

int color[n] = {60, 60, 60, 60, 60, 60, 60};

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

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

if (M[i] [j]!= 0) {

if (color[j] == color[i])

{

color[j] += 20;

}

}

}

}

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

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

if (M[i] [j]!= 0) {

if (color[j] == color[i])

{

color[i] += 20;

}

}

}

}

int V[7] [2]={{100,100}, {200,80}, {300,120}, {320,200}, {270,270}, {160,270}, {80,200}};

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

{

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

{

if (M[i] [j]>0)

{

MoveToEx (hdc, V[i] [0], V[i] [1], 0);

LineTo (hdc, V[j] [0], V[j] [1]);

}

}

}

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

{

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

{

Ellipse (hdc, V[i] [0] - 13, V[i] [1] - 13, V[i] [0]+13, V[i] [1]+13);

switch (color[i]) {

case(10):

SetTextColor (hdc, RGB (255, 255, 0));

break;

case(30):

SetTextColor (hdc, RGB (0, 255, 255));

break;

case(50):

SetTextColor (hdc, RGB (140, 0, 140));

break;

case(60):

SetTextColor (hdc, RGB (255, 0, 0));

break;

case(70):

SetTextColor (hdc, RGB (0, 0, 0));

break;

case(80):

SetTextColor (hdc, RGB (0, 255, 0));

break;

case(100):

SetTextColor (hdc, RGB (220, 220, 0));

break;

case(200):

SetTextColor (hdc, RGB (0, 255, 240));

break;

case(120):

SetTextColor (hdc, RGB (0, 0, 255)); break;

}

char v[2];

TextOut (hdc, V[i] [0] - 5, V[i] [1] - 7, (LPCTSTR) itoa (i+1, v, 10), 1);

}

}

DrawN3=false;

}

EndPaint (hWnd, &ps);

break;

case WM_DESTROY:

PostQuitMessage(0);

break;

default:

return DefWindowProc (hWnd, message, wParam, lParam);

}

return 0;

}

Файл «Resourse.h»

#define IDS_APP_TITLE 103

#define IDR_MAINFRAME 128

#define IDD_L_CW_DIALOG 102

#define IDM_EXIT 105

#define IDI_L_CW 107

#define IDI_SMALL 108

#define IDC_L_CW 109

#define IDC_MYICON 2

#define IDM_N_3 113

bool DrawN3 = false;

#define MAX_LOADSTRING 100

HINSTANCE hInst;

TCHAR szTitle [MAX_LOADSTRING];

TCHAR szWindowClass [MAX_LOADSTRING];

ATOM MyRegisterClass (HINSTANCE hInstance);

BOOL InitInstance (HINSTANCE, int);

LRESULT CALLBACK WndProc (HWND, UINT, WPARAM, LPARAM);

INT_PTR CALLBACK About (HWND, UINT, WPARAM, LPARAM);

int APIENTRY _tWinMain (HINSTANCE hInstance,

HINSTANCE hPrevInstance,

LPTSTR lpCmdLine,

int nCmdShow)

{

UNREFERENCED_PARAMETER(hPrevInstance);

UNREFERENCED_PARAMETER(lpCmdLine);

MSG msg;

HACCEL hAccelTable;

LoadString (hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);

LoadString (hInstance, IDC_L_CW, szWindowClass, MAX_LOADSTRING);

MyRegisterClass(hInstance);

if (! InitInstance (hInstance, nCmdShow))

{

return FALSE;

}

hAccelTable = LoadAccelerators (hInstance, MAKEINTRESOURCE (IDC_L_CW));

while (GetMessage (&msg, NULL, 0, 0))

{

if (! TranslateAccelerator (msg.hwnd, hAccelTable, &msg))

{

TranslateMessage(&msg);

DispatchMessage(&msg);

}

}

return (int) msg.wParam;

}

ATOM MyRegisterClass (HINSTANCE hInstance)

{

WNDCLASSEX wcex;

wcex.cbSize = sizeof(WNDCLASSEX);

wcex.style = CS_HREDRAW | CS_VREDRAW;

wcex.lpfnWndProc = WndProc;

wcex.cbClsExtra = 0;

wcex.cbWndExtra = 0;

wcex.hInstance = hInstance;

wcex.hIcon = LoadIcon (hInstance, MAKEINTRESOURCE (IDI_L_CW));

wcex.hCursor = LoadCursor (NULL, IDC_ARROW);

wcex.hbrBackground = (HBRUSH) (COLOR_WINDOW+1);

wcex.lpszMenuName = MAKEINTRESOURCE (IDC_L_CW);

wcex.lpszClassName = szWindowClass;

wcex.hIconSm = LoadIcon (wcex.hInstance, MAKEINTRESOURCE (IDI_SMALL));

return RegisterClassEx(&wcex);

}

Файл «Stdafx.cpp»

#include «stdafx.h»

Файл «Stdafx.h»

#pragma once

#include <windows.h>

#include <stdlib.h>

#include <malloc.h>

#include <memory.h>

#include <tchar.h>

#include <math.h>

#include <winbase.h>

#include <string.h>

#include <stdio.h>

#include <direct.h>

#include <time.h>

Размещено на Allbest.ru

...