Построение совершенного паросочетания в двудольном графе

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

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

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

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

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

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

к курсовому проекту

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

на тему «Построение совершенного паросочетания в двудольном графе»

Выполнила: Студентка группы 16ВВ3 Усмонова Х.И.

Пенза 2017

• Содержание
• 1. Теоретическая часть
• 2. Описание алгоритма решения поставленной задачи
• 3. Ручной расчет
• 4. Описание программы
• 5. Тесты
• Заключение
• Список используемых источников
• Приложение
• программирование двудольный граф паросочетание
• Введение
• В данной курсовой работе был рассмотрен раздел теории графов, посвященный двудольным графам. Теория графов может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы.
• Целью работы является написание программы на языке программирования, которая из введённой матрицы смежности ищет количество совершенных паросочетаний. Также представлены результаты решения контрольных примеров, выполненные с помощью разработанной программы.
• Для реализации задачи была выбрана программная среда Microsoft Visual Studio 2013. Язык программирования С#.
• Необходимо разработать программу «Построение совершенного паросочетания в двудольном графе» на языке С#. Пользователь должен иметь возможность ручного ввода таблицы смежности графа, на основе которой программа должна будет реализовать поиск совершенных паросочетаний.
• Управление в программе должно осуществляться с помощью клавиатуры и мыши. С помощью клавиатуры осуществляется ввода значений, а с помощью мыши подтверждение ввода данных или запуск функций путем нажатий.

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

Разработка будет осуществляться с использованием среды программирования MS Visual Studio 2013. Созданная программа будет ориентирована на операционную систему MS Windows.

1. Теоретическая часть

Пусть нам даны матрица смежности двудольного графа G = (U,V, X). Необходимо получить матрицу смежности совершенного паросочетания или множество ребер (дуг), входящих в совершенное паросочетание.

1. Выберем исходное паросочетание P1, например одно ребро графа G.

2. Предположим, что паросочетание Pi=(Ui,Vi,Xi) для графа G построено. Построим паросочетание Pi+1 для G следующим образом:

1. выбираем u из U, не принадлежащую Pi, например u1. Если такой вершины u нет, то Pi есть совершенное паросочетание.

Строим в G чередующуюся цепь µi = [u1,v1,u2,v2,...up,vp] с u1=u, в которой всякое ребро (ui,vi) не принадлежит Xi , а всякое ребро (vi,ui+1) принадлежит Xi. Если такой цепи нет, то совершенного паросочетания граф G не имеет, а паросочетание Pi является для G максимальным (тупиковым). Цепь µi есть Pi-увеличитель.

Выбрасываем из Pi все ребра (vi,ui+1) и добавляем все ребра (ui,vi) цепи µi. Получившееся паросочетание Pi+1 на одно ребро длиннее паросочетания Pi. Переходим к п.1.

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

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

В качестве среды программирования был выбран программный продукт Visual Studio 2013.

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

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

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

После формирования матрицы от пользователя ожидается нажатие на кнопку «Граф», c помощью которой будут вызваны функции DPoint и DLine. Эти функции позволяют вывести граф на экран. Блок схемы данных функций представлены на рисунке 4.

Рисунок 1 - Блок-схемы функций считываний и обработки введеных данных



Рисунок 2 - Блок-схема функции rasMatrix

Рисунок 3 - Блок-схема функции rasMatrix продолжение



Рисунок 4 - Блок-схемы функций отрисовки

4. Ручной расчет

Построим совершенное паросочетание для двудольного графа G = (U,V, X), U={u1,u2,u3,u4,u5,u6}, V={v1,v2,v3,v4,v5,v6,v7}, матрица смежности которого имеет вид (рисунок 5)

Рисунок 5 - Матрица смежности

Шаг 1. Выбираем исходное паросочетание Р₁={u₁,v₁} (рисунок 6).

Шаг 2. Выберем вершину u₂, которая не входит в паросочетание P₁, но которая смежна с вершиной v₁, содержащейся в P₁. Далее ищем вершину v, смежную с вершиной u₁, содержащейся в Р₁. В результате получим чередующуюся цепь (рисунок 7):

Рисунок 6 - Паросочетания графа

Рисунок 7 - Чередующаяся цепь

Единица в первой строке из нулей и единиц означает, что соответствующее этой единице ребро {v₁,u₁} лежит в P₁. Убираем это ребро из P₁, а вместо него добавляем ребра {u₂,v₁}, {u₁,v₂}, соответствующие единицам второй строки. В результате получим паросочетание P₂ ={ {u₁,v₁}, {u₂,v₃} }, число ребер в котором на одно больше, чем в P₁ (рисунок 8)

Шаг 3.

Рисунок 8 - Паросочетания P2

Найдем чередующуюся цепь (рисунок 9):

Рисунок 9 - Чередующаяся цепь µ₂

P₃={ {u₁,v₂}, {u₂,v₃},{u₃,v₁}} (рисунок 10).

Шаг 4.

Рисунок 10 - Паросочетания P3

Найдем чередующуюся цепь(рисунок 11):

P₄={ {u₁,v₂}, {u₂,v₅},{u₃,v₁},{u₄,v₃}}(рисунок 12).

Рисунок 11 - Чередующаяся цепь µ₃

Шаг 5.

Рисунок 12 - Паросочетания P4

Найдем чередующуюся цепь (рисунок 13):

Рисунок 13 - Чередующаяся цепь µ₄

P₅={ {u₁,v₂}, {u₂,v₁},{u₃,v₆},{u₄,v₃},{u₅,v₅}}(рисунок 14).

Шаг 6.

Рисунок 14 - Паросочетания P5

Найдем чередующуюся цепь(рисунок 15):

Рисунок 15 - Чередующаяся цепь µ5

P₆={ {u₁,v₂}, {u₂,v₃}, {u₃,v₁}, {u₄,v₇},{u₅,v₅},{u₆,v₆}}.

Полученное паросочетание является совершенным для исходного графа (рисунок 16).

Рисунок 16 - Паросочетания P6

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

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

Рисунок 17 - Исходное состояние

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

6. Тесты

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

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

Добавлена защита от некорректного ввода. Если пользователь вводит матрицу некорректно, то программа выведет ошибку (рисунок 18).

Рисунок 18 - Пример неверно введенных данных

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

Заключение

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

В ходе реализации графического интерфейса пользователя, усвоены нюансы работы в среде программирования Microsoft Visual Studio 2013 , а также самой платформой WindowsForm.

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

1. Программирование С#. Джеффри Рихтер- Эксмо, 2012 г. - 230-252 с.

2. Ресурсы электронной библиотеки

3. Лекции по теории графов / Под ред. В.А. Емеличева., О.Н. Мельникова, В.И. Сарванова, Р.И. Тышкевич. - Москва, Наука, Гл. ред. физ.-мат. лит., 1990г. - 384 с.

Приложение А.

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

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace Parosochetanija

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

dataGridView1.CellValueChanged += new DataGridViewCellEventHandler(DataGridView1_CellValueChanged);

}

public class Matrix

{

private readonly double[,] _a;

public int Length { get; private set; }

public Matrix(double[,] a)

{

_a = a;

Length = a.GetLength(0);

}

public Matrix(int n)

: this(new double[n, n])

{

}

public void Generate()

{

var r = new Random();

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

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

_a[i, j] = (r.Next() % 1000) / 100.0;

}

public string PrintMatrix()

{

var result = new StringBuilder(Length * 7);

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

{

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

result.AppendFormat("{0,-7}", _a[i, j]);

result.AppendLine();

}

return result.ToString();

}

public unsafe double Determinant

{

get

{

var temp = new double[_a.Length];

Buffer.BlockCopy(_a, 0, temp, 0, temp.Length * sizeof(double));

fixed (double* pm = &temp[0]) return _Det(pm, Length); ;

}

}

unsafe double _Det(double* rmX, int n)

{

double* mtx_u_ii, mtx_ii_j;

double* mtx_end = rmX + n * (n - 1), mtx_u_ii_j = null;

double val, det = 1;

int d = 0;

// rmX указывает на (i,i) элемент на каждом шаге и называется ведущим

for (double* mtx_ii_end = rmX + n; rmX < mtx_end; rmX += n + 1, mtx_ii_end += n, d++)

{

// Ищем максимальный элемент в столбце(под ведущим)

{

//Ищем максимальный элемент и его позицию

val = Math.Abs(*(mtx_ii_j = rmX));

for (mtx_u_ii = rmX + n; mtx_u_ii < mtx_end; mtx_u_ii += n)

{

if (val < Math.Abs(*mtx_u_ii))

val = Math.Abs(*(mtx_ii_j = mtx_u_ii));

}

//Если максимальный эдемент = 0 -> матрица вырожденная

if (Math.Abs(val - 0) < double.Epsilon) return double.NaN;

//Если ведущий элемент не является максимальным - делаем перестановку строк и меняем знак определителя

if (mtx_ii_j != rmX)

{

/*Убрал знак минус*/

//det = -det;

//for (mtx_u_ii = rmX; mtx_u_ii < mtx_ii_end; mtx_ii_j++, mtx_u_ii++)

//{

// val = *mtx_u_ii;

// *mtx_u_ii = *mtx_ii_j;

// *mtx_ii_j = val;

//}

}

}

//Обнуляем элементы под ведущим

for (mtx_u_ii = rmX + n, mtx_u_ii_j = mtx_end + n; mtx_u_ii < mtx_u_ii_j; mtx_u_ii += d)

{

val = *(mtx_u_ii++) / *rmX;

for (mtx_ii_j = rmX + 1; mtx_ii_j < mtx_ii_end; mtx_u_ii++, mtx_ii_j++)

/*заменил знак минус на плюс*/

*mtx_u_ii += *mtx_ii_j * val;

}

// det *= *rmX;

}

return det * *rmX;

}

public double this[int i, int j]

{

get { return _a[i, j]; }

set { _a[i, j] = value; }

}

}

bool Operand = false;

Values element = new Values();

PointOfMass PointForMatrix = new PointOfMass();

short[,] table = new short[Values.SizeMatrix + 1, Values.SizeMatrix + 1];

public void button1_Click(object sender, EventArgs e)

{

try

{

short SizeMatrix = Convert.ToInt16(textBox1.Text);

element = new Values(SizeMatrix);

table = new short[Values.SizeMatrix + 1, Values.SizeMatrix + 1];

dataGridView1.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;

dataGridView1.AllowUserToAddRows = false;

dataGridView1.AllowUserToResizeColumns = false;

dataGridView1.AllowUserToDeleteRows = false;

dataGridView1.AllowUserToResizeRows = false;

dataGridView1.ColumnCount = SizeMatrix + 1;

dataGridView1.RowCount = SizeMatrix + 1;

dataGridView1.Rows[0].Cells[0].Style.BackColor = Color.DarkKhaki;

dataGridView1[0, 0].ReadOnly = true;

SetValue();

Operand = true;

}

catch {

MessageBox.Show("Некорректно указано число вершин");

}

} //bs

private void ElVal(Values element)

{

element.ValMatrix = new short[Values.SizeMatrix + 1, Values.SizeMatrix + 1];

//Random RandForElem = new Random();

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

element.ValMatrix[indexI, indexJ] = 0;

}

}

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

dataGridView1[indexI, indexJ].Value = element.ValMatrix[indexJ, indexI];

}

}

}

private void GetValue(Values element)

{

try

{

var d = new double[Values.SizeMatrix, Values.SizeMatrix];

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

element.ValMatrix[indexJ, indexI] = short.Parse(dataGridView1[indexI, indexJ].Value.ToString());

}

}

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

d[indexI - 1, indexJ - 1] = element.ValMatrix[indexI, indexJ];

}

}

var matrix = new Matrix(d);

var x = matrix.Determinant;

double k = double.Parse(x.ToString());

}

catch { MessageBox.Show("Некоореткный ввод матрицы"); }

}

private void SetValue()

{

int RowsColumsHeader = 1;

short SizeMatrix = Convert.ToInt16(textBox1.Text);

while (RowsColumsHeader < Values.SizeMatrix + 1)

{

dataGridView1[RowsColumsHeader, 0].Value = RowsColumsHeader;

dataGridView1[RowsColumsHeader, 0].ReadOnly = true;

dataGridView1.Rows[RowsColumsHeader].Cells[0].Style.BackColor = Color.DarkKhaki;

dataGridView1[0, RowsColumsHeader].Value = RowsColumsHeader;

dataGridView1[0, RowsColumsHeader].ReadOnly = true;

dataGridView1.Rows[0].Cells[RowsColumsHeader].Style.BackColor = Color.DarkKhaki;

++RowsColumsHeader;

}

ElVal(element);

}

private void DataGridView1_CellValueChanged(object sender, DataGridViewCellEventArgs e)

{

if (Operand)

{

GetValue(element);

}

}

public void rasMatrix(Values element)

{

int memberString = 0;

int memberColumn = 0, memberFirstRow = 0, memberColumnNotFirst = 0, memberFinallyRow = 0;

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

table[indexI, indexJ] = element.ValMatrix[indexI, indexJ];

}

}

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = indexI; indexJ < Values.SizeMatrix + 1; indexJ++)

{

if (table[indexI, indexJ] == 1)

{

table[indexI, indexJ] = 2;

break;

}

}

}

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

if (table[indexI, indexJ] == 2)

{

table[indexI, indexJ] = 2;

break;

}

if (indexJ == Values.SizeMatrix)

{

memberString = indexI;

}

}

}

for (int indexI = memberString; ; )

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

if (table[indexI, indexJ] == 1)

{

memberColumn = indexJ;

break;

}

}

break;

}

for (int indexI = memberColumn; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

if (table[indexJ, indexI] == 2)

{

memberFirstRow = indexJ;

break;

}

}

break;

}

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

if (table[indexI, indexJ] == 2)

{

table[indexI, indexJ] = 2;

break;

}

if (indexI == Values.SizeMatrix)

{

memberColumnNotFirst = indexJ;

}

}

}

for (int indexJ = memberColumnNotFirst; indexJ < Values.SizeMatrix + 1; indexJ++)

{

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

if (table[indexI, indexJ] == 1)

{

table[indexI, indexJ] = 2;

memberFinallyRow = indexI;

break;

}

}

break;

}

for (int indexI = memberFinallyRow; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

if (table[indexJ, indexI] == 2 & indexJ != memberColumnNotFirst)

{

table[indexJ, indexI] = 1;

table[memberString, indexI] = 2;

break;

}

}

break;

}

}

private void button2_Click(object sender, EventArgs e)

{

PointOfMass Points = new PointOfMass(Values.SizeMatrix);

rasMatrix(element);

DPoint( Points);

CreateLines( table, Points);

}

public void DPoint( PointOfMass PointMatrix)

{

Graphics gr = pictureBox1.CreateGraphics();

Pen PenForPoint = new Pen(Color.Black, 2);

for (int tmp = 1; tmp < Values.SizeMatrix + 1; tmp++)

{

gr.DrawEllipse(PenForPoint, new Rectangle(PointMatrix.MassPointsXcomp1[tmp], PointMatrix.MassPointsYcomp1[tmp], 2, 2));

gr.DrawString(tmp.ToString(), new Font("Arial", 9), new SolidBrush(Color.Black), new Point(PointMatrix.MassPointsXcomp1[tmp] - 12, PointMatrix.MassPointsYcomp1[tmp] - 6));

gr.DrawEllipse(PenForPoint, new Rectangle(PointMatrix.MassPointsXcomp2[tmp], PointMatrix.MassPointsYcomp2[tmp], 2, 2));

gr.DrawString(tmp.ToString(), new Font("Arial", 9), new SolidBrush(Color.Black), new Point(PointMatrix.MassPointsXcomp2[tmp] + 6, PointMatrix.MassPointsYcomp2[tmp] - 6));

}

}

public void CreateLines( short[,] table, PointOfMass PointMatrix)

{

Graphics gr = pictureBox1.CreateGraphics();

Pen[] PenForLine = new Pen[2];

PenForLine[0] = new Pen(Color.Black, 2);

PenForLine[1] = new Pen(Color.Red, 2);

int c = 0;

for (int indexI = 1; indexI < Values.SizeMatrix + 1; indexI++)

{

for (int indexJ = 1; indexJ < Values.SizeMatrix + 1; indexJ++)

{

if (table[indexI, indexJ] == 1)

{

gr.DrawLine(PenForLine[0], new Point(PointMatrix.MassPointsXcomp1[indexI], PointMatrix.MassPointsYcomp1[indexI]), new Point(PointMatrix.MassPointsXcomp2[indexJ], PointMatrix.MassPointsYcomp2[indexJ]));

}

if (table[indexI, indexJ] == 2)

{

gr.DrawLine(PenForLine[1], new Point(PointMatrix.MassPointsXcomp1[indexI], PointMatrix.MassPointsYcomp1[indexI]), new Point(PointMatrix.MassPointsXcomp2[indexJ], PointMatrix.MassPointsYcomp2[indexJ]));

c++;

}

}

}

textBox2.Text = Convert.ToString(c);

}

private void textBox2_TextChanged(object sender, EventArgs e)

{

}

}

}

Приложение Б.

Результаты работы программы

При запуске программы и вводе туда следующих данных:

4

Программы выведет следующий результат (рисунок 19):

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

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

...