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

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

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

Курсовая работа

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

Выполнил Щетинин К.

Введение

Алгоритм Куна ищет максимальное паросочетание в неориентированном невзвешенном двудольном графе, представленном на матрице смежности двудольного графа за время O(N3).

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

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

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

Теперь вся проблема свелась к тому, как искать чередующиеся цепочки. В качестве потенциального начала следующей цепочки будем перебирать последовательно все вершины одной из долей графа, а потом пытаться найти цепочку, выходящую из этой вершины. Для успешного проведения подобных действий нам понадобится дополнительный массив меток Use: array[0..MaxX] of Boolean и массив P: array[1..MaxY] of Integer, в котором мы будем хитрым образом хранить текущее состояние "зелёности" рёбер.

Действительно, как нам лучше хранить информацию о зелёных рёбрах, в данный момент присутствующих в графе? Можно, конечно, в матрице смежности двудольного графа хранить не True и False в зависимости от наличия ребра, а хранить, скажем, 0 для отсутствия ребра, 1 для чёрного и 2 для зелёного ребра. Но это неудобная и неоптимальная фишка, забейте на неё.

Чтобы придумать более хитрый метод хранения, надо сначала слегка подумать, а потом заметить вот что: из одной вершины может выходить не более одного зелёного ребра. Действительно, если из одной вершины выходит два зелёных ребра, то они однозначно смежны, что противоречит понятию паросочетания. Таким образом мы можем сделать следующее: будем хранить 0 в элементе массива P[I], если из I-ой вершины одной доли не выходит зелёных рёбер, а если зелёное ребро выходит в вершину с номером K другой доли, то положим P[I] равным K. И вот ещё что: для реализации алгоритма нам понадобится массив P лишь для вершин второй доли, поэтому его размерность равна MaxY. Таким образом, если, скажем, P[1] = 3, это значит, что из первой вершины второй доли выходит зелёное ребро в третью вершину первой доли.

Ниже приведён фрагмент программы, реализующей алгоритм Куна (здесь I: Integer).

Function Find(V: Integer): Boolean;

Var I: Integer;

Begin

Use[V]:= True;

For I:= 1 to Y do

If A[V, I] and not Use[P[I]] and ((P[I] = 0) or Find(P[I])) Then Begin

P[I]:= V;

Find:= True;

Exit;

End;

Find:= False;

End;

...

For I:= 1 to X do Begin

FillChar(Use, SizeOf(Use), False);

Find(I);

End;

Функция Find(V) возвращает False, если ей не удалось найти чередующаяся цепочку, начинающуюся в вершине V первой доли, а если удалось, то она возвращает True и инвертирует цепочку. Изначально P[I] = 0 для всех I от 1 до X. Утверждение: если запустить функцию Find по порядку из всех вершин первой доли, будут найдены все чередующиеся цепочки, т.е. мы построим максимальное паросочетание. В цикле, начинающемся в строке 13, обнуляется массив меток в строке 14, а в строке 15 запускается очередная функция Find.

Рассмотрим теперь работу функции. Запустившись из вершины V, она в строке 4 помечает её, чтобы в дальнейшем к ней уже не обращаться (повторное обращение может возникнуть из-за рекуррентности функции). Далее в строке 5 запускается цикл, в котором она пытается найти первое ребро чередующейся цепи. Если оно выходит в вершину I второй доли, то оно должно удовлетворять следующим условиям (строка 6): во-первых, оно должно существовать.условие A[V, I]). Во-вторых, если из его вершины во второй доле (I) выходит зелёное ребро, то другая вершина этого зелёного ребра в первой доле должна быть ещё не помечена (условие not Use[P[I]]). И если это всё так, то или вершина I во второй доле свободна (условие P[I] = 0), или из другой вершины выходящего из неё зелёного ребра мы можем построить продолжение чередующейся цепочки (условие Find(P[I])). Если P[I] = 0, то условие not Use[P[I]], не нужное в данном случае, автоматом даст True (т.к. в нулевом элементе массива Use всегда хранится False), и не повлияет на итоговое значение выражения.

Если условие выполнилось, мы инвертируем текущее звено цепи в строке 7. Один стековый экземпляр функции, как Вы уже могли заметить, отвечает за поиск лишь одной пары рёбер чёрное-зелёное; если для вершины I второй доли P[I] = 0, значит ребро {V, I} замыкает цепь. В строке 8 мы говорим, что чередующаяся цепочка найдена, а в строке 9 завершаем текущий экземпляр функции.

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

Найденное максимальное паросочетание можно вычленить из массива P. Количество ненулевых элементов массива будет соответствовать мощности паросочетания.

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

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

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

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

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

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

Совершенным паросочетанием называется паросочетание, в котором участвуют все вершины графа. То есть любая вершина графа сопряжена ровно одному ребру, входящему в паросочетание. Любое совершенное паросочетание является максимальным. Совершенное паросочетание является также реберным покрытием минимального размера. Таким образом, н (G) ? с (G) {\displaystyle \nu (G)\leq \rho (G)} Размещено на http://www.allbest.ru/

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

-- размер максимального паросочетания не превосходит минимального рёберного покрытия.

Граф G = (V,X) называется двудольным, если множество V его вершин допускает разбиение на два непересекающихся подмножества V1 и V2 (две доли), причем каждое ребро графа соединяет вершины из разных долей.

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

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

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

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

Затем была написана функция Parosochetania() отображающая данный интерфейс.

Также была реализована button1_Click (), обрабатывающая данные, введенные пользователем. Она считывает данные, введенные пользователем, и осуществляет проверку возможности существования в графе совершенного паросочетания.

Если совершенное паросочетание существует, то программа выводит число паросочетаний и число этих паросочетаний

В итоге данная функция стала частью цикла главной функции программы Parosochetania(). Данная функция была реализована как функция, отвечающая за алгоритм процесса работы программы и выдающая конечный результат работы. Функция использует результаты работы функции _Det и строит как исходный граф, введенный изначально пользователем, так и паросочетания (или выдаёт информацию о его не существовании).

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



Рисунок 1. Схема данных



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

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

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

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

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



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

Тесты

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

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

Также были добавлены проверки связанные с вводом исходной матрицы смежности.

Если пользователь неправильно вводит исходную матрицу смежности (допускает ошибку при вводе или указывает не соответствующее количество вершин), то после ввода выдаётся окно с ошибкой «Ошибка ввода»,что покахано на 6-ом рисунке

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

совершенное паросочетание двудольный граф

Если же граф введен правильно, но совершенные паросочетания в нём найдены не будут, то в нижнем поле формы выведется сообщение «Совершенное паросочетание не найдено», что представлено на 5-ом рисунке

Рисунок 6. Пример графа без совершенного паросочетания

Заключение

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

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

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

1. Язык Си: Б.В. Керниган, Д.М. Ричи - Санкт-Петербруг, Невский диалект, 2003г. - 355 с.

2. Как программировать на С: Харви Дейтел, Пол Дейтел - Москва, Бином-пресс, 2006 г. - 512 с.

3. Ресурсы электронной библиотеки http://msdn.microsoft.com/

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

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

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

Файл « Form1.cs»

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;

using System.Text.RegularExpressions;

using System.IO;

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];

private void SetElelementsValuesReadyValues(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 RefreshValuesData(Values element)

{

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

string c;

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

{

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

{

c = dataGridView1[indexI, indexJ].Value.ToString();

if ((c == "1") || (c == "0"))

{

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

}

else {

MessageBox.Show(" Вы ввели неправильное значение введите снова");

}

}

}

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;

textBox2.Text = x.ToString();

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

if (k > 1)

{

textBox3.Text = "Совершенное паросочетание найдено!".ToString();

textBox4.Text = "Рисунок рабочий".ToString();

}

if (k == 0)

{

textBox3.Text = "Совершенное паросочетание не найдено!".ToString();

textBox4.Text = "Рисунок ошибочен!".ToString();

}

}

private void SetElelementsValues()

{

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;

}

SetElelementsValuesReadyValues(element);

}

public void button1_Click(object sender, EventArgs e)

{

Regex rxNums = new Regex(@"^\d+$");

if (rxNums.IsMatch(textBox1.Text))

{

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;

SetElelementsValues();

Operand = true;

}

else

{

MessageBox.Show(" Вы ввели неправильный размер матрицы. Повторите ввод.");

}

}

private void DataGridView1_CellValueChanged(object sender, DataGridViewCellEventArgs e)

{

if (Operand)

{

RefreshValuesData(element);

}

}

public void FindTable(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];

}

}

/*заменим места для 1 на 2*/

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;

}

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)

{

//FindTable(element);

}

}

}

//FindTable(element);

}

/*Найти столбец в той строчке куда можно поставить единицу

находим в том столбце уже проставленную единицу

запоминаем ту строчку с этой единицей

*/

private void button2_Click(object sender, EventArgs e)

{

PointOfMass Points = new PointOfMass(Values.SizeMatrix);

FindTable(element);

Form2 FormForDraw = new Form2();

FormForDraw.Show();

FormForDraw.ObjectDraw(element, Points);

FormForDraw.CreateLines(element, table, Points);

}

}

}

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

На рисунке 7 отображены результаты работы программы.

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

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



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

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

...