Главная Коллекция "Otherreferats" Программирование, компьютеры и кибернетика Логика и основы алгоритмизации в инженерных задачах

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

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	21.02.2019
Размер файла	1,1 M

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

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

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

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

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

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

Приняли:

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

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

Пенза 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. Выполним сортировку вершин в порядке убывания их степеней.

i	5	1	2	3	4	6
deg(V_i)	4	3	3	3	2	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₌₁={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₌₂={1, 4, 6}.

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

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

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

X_k₌₃={3}.

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

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

i	5	1	2	3	4	6
deg(V_i)	4	3	3	3	2	1
k(V_i)	1	2	1	3	2	2

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) {

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

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

mass[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

}

//функция clear

private: void clear() {

for (int i=0;i < dataGridView1->Rows->Count; i++){

for (int j=0;j < dataGridView1->Rows->Count; j++){

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

}

}

}

private: System::Void dataGridView1_Click(System::Object^ sender, System::EventArgs^ e)

{

label14->Text= "";

//размер матрицы

size = Convert::ToInt32(numericUpDown1->Value);

if (size<=12){

//создание массива для матрицы

int **mass = new int *[size];

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

mass[i]= new int[size];

}

//создание таблицы под матрицу

dataGridView1->ColumnCount = size;

dataGridView1->RowCount = size;

//заполнение значениями вручную

typing(size, mass);

//вывод матрицы

show(size, mass);

}

else label14->Text = "Выберите меньшее число вершин (не более 12)";

}

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e)

{

label14->Text = "";

label15->Text = "";

clear();

size=0;

memset(mass, 0, sizeof(mass));

memset(mass2, 0, sizeof(mass2));

memset(mass3, 0, sizeof(mass3));

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

{

versh[i].stepen = 0;

versh[i].num = 0;

versh[i].colour = 0;

}

}

private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e)

{

switch (size)

{

case 1:

this->ovalShape1->Visible = true;

this->label2->Visible = true;

break;

case 2:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j))

{

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

break;

}

}

}

}

break;

case 3:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape4->Visible = true;

this->label4->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 4:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 5:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 6:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

this->ovalShape6->Visible = true;

this->label7->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 7:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

this->ovalShape6->Visible = true;

this->label7->Visible = true;

this->ovalShape8->Visible = true;

this->label8->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 8:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

this->ovalShape6->Visible = true;

this->label7->Visible = true;

this->ovalShape7->Visible = true;

this->label8->Visible = true;

this->ovalShape8->Visible = true;

this->label9->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 9:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

this->ovalShape6->Visible = true;

this->label7->Visible = true;

this->ovalShape7->Visible = true;

this->label8->Visible = true;

this->ovalShape8->Visible = true;

this->label9->Visible = true;

this->ovalShape9->Visible = true;

this->label10->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 10:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

this->ovalShape6->Visible = true;

this->label7->Visible = true;

this->ovalShape7->Visible = true;

this->label8->Visible = true;

this->ovalShape8->Visible = true;

this->label9->Visible = true;

this->ovalShape9->Visible = true;

this->label10->Visible = true;

this->ovalShape10->Visible = true;

this->label11->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 11:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

this->ovalShape6->Visible = true;

this->label7->Visible = true;

this->ovalShape7->Visible = true;

this->label8->Visible = true;

this->ovalShape8->Visible = true;

this->label9->Visible = true;

this->ovalShape9->Visible = true;

this->label10->Visible = true;

this->ovalShape10->Visible = true;

this->label11->Visible = true;

this->ovalShape11->Visible = true;

this->label12->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

case 12:

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

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

{

{

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i!=j)) {

if (z > 0) {break;}

x1 = coords[i][0];

y1 = coords[i][1];

x2 = coords[j][0];

y2 = coords[j][1];

Graphics^ g = Graphics::FromHwnd(this->panel1->Handle);

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

x1=0;y1=0;x2=0;y2=0;

this->ovalShape1->Visible = true;

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

this->ovalShape3->Visible = true;

this->label4->Visible = true;

this->ovalShape4->Visible = true;

this->label5->Visible = true;

this->ovalShape5->Visible = true;

this->label6->Visible = true;

this->ovalShape6->Visible = true;

this->label7->Visible = true;

this->ovalShape7->Visible = true;

this->label8->Visible = true;

this->ovalShape8->Visible = true;

this->label9->Visible = true;

this->ovalShape9->Visible = true;

this->label10->Visible = true;

this->ovalShape10->Visible = true;

this->label11->Visible = true;

this->ovalShape11->Visible = true;

this->label12->Visible = true;

this->ovalShape12->Visible = true;

this->label13->Visible = true;

}

else {

if ((Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value)==1) && (i==j))

{

label14->Text = "Ошибка ввода";

z++;

}

};

};

};

break;

}

z=0;

}

Алгоритм нахождения хроматического числа:

private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e)

{

memset(mass2, -1, sizeof(mass2));

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

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

{

mass2[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

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

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

{

if (mass2[i][j] == -1) {continue;}

else

mass3[i][j] = mass2[i][j];

}

}

int i=0, j=0;

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

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

{

if (mass3[i][j]==1)

{c=c+1;}

}

versh[i].stepen=c;

versh[i].num=i;

c=0;

}

for (int i = size - 1; i >= 0; i--)

{

ns = 1;

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

{

if (versh[j].stepen < versh[j+1].stepen)

{

t = versh[j].stepen;

m = versh[j].num;

versh[j].stepen = versh[j+1].stepen;

versh[j].num = versh[j+1].num;

versh[j+1].stepen = t;

versh[j+1].num = m;

ns = 0;

}

}

if (ns == 1)

break;

}

k = 0;

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

{

if (versh[i].colour == 0)

{

k++;

versh[i].colour = k;

memset(versh2, -1, sizeof(versh2));

versh2[i] = versh[i].num;

d++;

}

for (int j = i + 1; j < size; j++)

{

h = versh[i].num;

n = versh[j].num;

if ((mass3[h][n]==0) && (versh[j].colour == 0))

{

b = proverka(j,n);

if (b==1){

versh[j].colour = k;

versh2[j] = versh[j].num;

d++;

}

}

}

d=0;

}

label15->Text =System::Convert::ToString(k);

this->label16->Visible = true;

}

}

int proverka(int j,int n)

{

ch=0;

for(s=j-1; s >= 0; s--)

{

int e = versh2[s];

if((versh2[s] >= 0) && (mass3[n][e]==0))

ch++;

}

if(ch==d) return 1;

else return 0;

}

}

};

};

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

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

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

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

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

Подобные документы

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

курсовая работа [1,1 M], добавлен 26.06.2012

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

курсовая работа [145,5 K], добавлен 27.01.2013

Основы алгоритмизации
Математическая постановка задачи для алгоритмизации, рекуррентная зависимость. Алгоритм решения задачи, блок-схема программы. Тестовые данные для тестирования программы. Результаты, соответствующие для первых вводимых данных и листинг программы.

контрольная работа [27,0 K], добавлен 09.05.2012

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

курсовая работа [336,8 K], добавлен 28.05.2016

Решение графа с помощью программы
История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.

контрольная работа [646,9 K], добавлен 19.01.2016

Прикладная программа для нахождения раскраски неориентированного графа ограниченным числом цветов
Разработка граф-схемы алгоритма раскраски на языке Object Pascal. Формат файла для хранения графов. Выбор удобочитаемых идентификаторов. Переменные, константы, типы, компоненты, процедуры и функции модулей uMain, uInputk, uFiling, uColoring, uHelp.

курсовая работа [1,3 M], добавлен 22.11.2013

Разработка программы формирования матрицы смежности
Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.

курсовая работа [8,1 M], добавлен 07.09.2012

Поиск вершины в графе между двумя заданными вершинами
Вершина в заданном графе с различным количеством вершин. Результаты обработки графа программой MyProject.exe. Сопряжение модулей программы. Модуль вывода матрицы смежности. Тесты черного ящика. Комбинаторное покрытие условий тестами черного ящика.

курсовая работа [44,8 K], добавлен 13.10.2012

Реализация алгоритма нахождения множеств элементарных циклов графа средствами языка С++
Способ представления графа в информатике. Алгоритмы поиска элементарных циклов в глубину в неориентированных графах. Описание среды wxDev-C++, последовательность создания проекта. Руководство пользователю программы поиска и вывода на экран простых циклов.

курсовая работа [783,2 K], добавлен 18.02.2013

Разработка приложения для поиска максимально удалённых вершин в графе
Разработка программного продукта для поиска максимально удалённых вершин в графе. Характеристика ориентированного, смешанного и изоморфного графов. Обзор способов представления графа в информатике. Алгоритм поиска пути. Графический интерфейс программы.

курсовая работа [384,0 K], добавлен 10.01.2015

Другие документы, подобные "Логика и основы алгоритмизации в инженерных задачах"

главная

рубрики

по алфавиту

вернуться в начало страницы

вернуться к началу текста

вернуться к подобным работам

Рубрики

По алфавиту

Закачать файл

Заказать работу

весь список подобных работ

скачать работу можно здесь

сколько стоит заказать работу?

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

Файл Form1.h

int c = 0;

bool ns=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},

int proverka(int j,int n);

using namespace System::Drawing;

(Object^ sender, DataGridViewCellValidatingEventArgs^ e)

{

{

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

e->Cancel = true;

}

}

//функция show

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

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

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

//функция typing

//функция clear

private: System::Void dataGridView1_Click(System::Object^ sender, System::EventArgs^ e)

label14->Text= "";

//размер матрицы

size = Convert::ToInt32(numericUpDown1->Value);

if (size<=12){

//создание массива для матрицы

int **mass = new int *[size];

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

mass[i]= new int[size];

}

//создание таблицы под матрицу

dataGridView1->ColumnCount = size;

dataGridView1->RowCount = size;

//заполнение значениями вручную

typing(size, mass);

//вывод матрицы

show(size, mass);

}

else label14->Text = "Выберите меньшее число вершин (не более 12)";

}

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e)

size=0;

}

private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e)

this->label2->Visible = true;

break;

g->DrawLine(gcnew Pen(Color::Black,3),x1,y1,x2,y2);

this->label2->Visible = true;

this->ovalShape2->Visible = true;

this->label3->Visible = true;

}

label14->Text = "Ошибка ввода";