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

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

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

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

к курсовому проектированию

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

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

Выполнил: студент группы 16ВВ1 Чиркин К.Д.

Пенза 2017

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

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

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

Устройствами ввода информации являются клавиатура и мышь.

Программа должна быть разработана для работы в операционной системе Microsoft Windows.

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

Необходимые определения:

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

Цепью длины k назовём некоторый простой путь (т.е. не содержащий повторяющихся вершин или рёбер), содержащий k рёбер.

Чередующейся цепью (в двудольном графе, относительно некоторого паросочетания) назовём цепь, в которой рёбра поочередно принадлежат/не принадлежат паросочетанию.

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

Теорема Бержа

Формулировка: Паросочетание является максимальным тогда и только тогда, когда не существует увеличивающих относительно него цепей.

Алгоритм Куна -- непосредственное применение теоремы Бержа. Его можно кратко описать так: сначала возьмём пустое паросочетание, а потом -- пока в графе удаётся найти увеличивающую цепь, -- будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось -- процесс останавливаем, -- текущее паросочетание и есть максимальное.

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

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

Алгоритм просматривает все вершины v первой доли графа: v = 1…n₁. Если текущая вершина v уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем. Иначе -- алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.

Поиск увеличивающей цепи осуществляется с помощью специального обхода в глубину или ширину (обычно в целях простоты реализации используют именно обход в глубину). Изначально обход в глубину стоит в текущей ненасыщенной вершине v первой доли. Просматриваем все рёбра из этой вершины, пусть текущее ребро -- это ребро (v,to). Если вершина to ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра (v,to); в таком случае просто включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины v. Иначе, -- если to уже насыщена каким-то ребром (p,to), то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра (v,to), (to,p). Для этого просто перейдём в нашем обходе в вершину p -- теперь мы уже пробуем найти увеличивающую цепь из этой вершины.

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

После того, как все вершины v = 1…n₁ будут просмотрены, текущее паросочетание будет максимальным.

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

Исходный двудольный граф:

Рис. 1

Просматриваем все вершины первой доли графа. Начинаем обход с вершины 0. Просматриваем все ребра, соединенные с этой вершиной. Находим ребро 0-3. Вершина 3 не насыщена паросочетанием, следовательно, включаем ребро 0-3 в паросочетание.

Переходим к следующей вершине (1). Находим ребро 1-3. Это ребро насыщено паросочетанием, поэтому пытаемся найти из ребра 1-3 увеличивающуюся цепь. Идем из 1-3 в 0-3. Ребро 0-3 уже включено в паросочетание, следовательно, найти увеличивающуюся цепь не удалось.

Возвращаемся к вершине 1. Просматриваем ребро 1-4. Вершина 4 не насыщена паросочетанием, поэтому добавляем ребро 1-4 в паросочетание.

Переходим к последней вершине первой доли графа (2). Находим только ребро 2-4. 4 вершина насыщена и уже включена в паросочетание в составе ребра 1-4. Поэтому больше ребер включить в паросочетание невозможно.

Наибольшее паросочетание в итоге состоит из ребер 0-3, 1-4.

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

Общее описание

Программа представляет собой графическое приложение с двумя окнами: окно для задания свойств двудольного графа и окно для графического отображения графа. Программа написана на языке Java с использованием библиотек Swing и AWT для создания графического интерфейса.

На первом окне (рис. 2) мы можем задать количество узлов в 1-м и во 2-м подграфе двудольного графа (от 1 до 6). Затем мы можем нажать кнопку «Сгенерировать граф». При нажатии на эту кнопку открывается второе окно (рис. 3), на котором мы видим визуальное представление графа. На графе красным цветом выделено наибольшее паросочетание. В верху окна с графом отображается количество ребер в наибольшем паросочетании.

Рис. 2 - Главное окно

Рис. 3- окно с отображением графа

Модули программы

Main.java - точка входа в программу. В этом классе создается главное (первое) окно программы.

Constants.java - здесь задаются все строковые и числовые константы.

MainGUI.java - в этом модуле прописан графический интерфейс главного окна, а также обработка взаимодействий с элементами графического интерфейса.

FirstPanelWithSpinner - здесь описывается текстовое поле вывода и «спиннер» для выбора количества ребер у первого подграфа.

SpinnerPanelWithSpinner - здесь описывается текстовое поле вывода и «спиннер» для выбора количества ребер у второго подграфа.

GraphFrame.java - в этом модуле создается окно для отображения графа.

BipartiteGraph.java - описывает двудольный граф и методы для работы с ним.

GraphView.java - этот модуль содержит функции для отображения графа и информации о нем.

4. Тесты

В качестве среды разработки была выбрана программа Intellij IDEA которая содержит в себе все необходимые средства для разработки и отладки модулей и программ на языке java (и не только). Для отладки программы использовались различные инструменты: точка остановки, пошаговое выполнение кода программы, анализ содержимого глобальных и локальных переменных.

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

Тестирование программы представлено на рисунках 4, 5, 6.

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



Рис. 4 - тест 1

Рис. 5 - тест 2

Рис. 6 - тест 3

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

Main.java

import gui.MainGUI;

public class Main {

public static void main(String[] args) {

MainGUI mainWindow = new MainGUI();

mainWindow.setVisible(true);

} }

Constants.java

package common;

public class Constants {

public static final int MAIN_WINDOW_WIDTH = 400;

public static final int MAIN_WINDOW_HEIGHT = 200;

public static final int GRAPH_WINDOW_WIDTH = 300;

public static final int GRAPH_WINDOW_HEIGHT = 700;

public static final int MAX_NUMBER_OF_NODES = 6;

public static final int DEFAULT_NUMBER_OF_NODES = 3;

public static final int NODE_WIDTH = 30;

public static final int NODE_HEIGHT = 30;

public static final String MAIN_WINDOW_TITLE =

"Курсовая работа по ЛиОА в ИЗ";

public static final String GRAPH_WINDOW_TITLE =

"Двудольный граф";

public static final String DESC_FOR_SPINNERS_TEXT =

"Введите кол-во узлов для 1-й и 2-й части графа:";

public static final String FIRST_SPINNER_TEXT = "1-я часть";

public static final String SECOND_SPINNER_TEXT = "2-я часть";

public static final String GENERATE_BUTTON_TEXT = "Сгенерировать граф";

public static final String MATCH_SIZE_TEXT = "Кол-во ребер в паросочетании = "; }

MainGUI.java

package gui;

import common.Constants; import graph.BipartiteGraph;

import javax.swing.*; import java.awt.*;

public class MainGUI extends JFrame {

int firstGraphNodesCount = Constants.DEFAULT_NUMBER_OF_NODES;

int secondGraphNodesCount = Constants.DEFAULT_NUMBER_OF_NODES;

private BipartiteGraph bipartiteGraph;

public MainGUI() {

configureMainWindow(Constants.MAIN_WINDOW_TITLE);

initViews();

}

private void configureMainWindow(String title) {

setTitle(title);

setSize(Constants.MAIN_WINDOW_WIDTH, Constants.MAIN_WINDOW_HEIGHT);

setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);

}

private void initViews() {

FirstPanelWithSpinner firstPanelWithSpinner = new FirstPanelWithSpinner();

firstPanelWithSpinner.firstPanelSpinner.addChangeListener(e -> {

firstGraphNodesCount = (Integer) firstPanelWithSpinner.firstPanelSpinner.getValue();

});

SecondPanelWithSpinner secondPanelWithSpinner = new SecondPanelWithSpinner();

secondPanelWithSpinner.secondPanelSpinner.addChangeListener(e ->

secondGraphNodesCount = (Integer) secondPanelWithSpinner.secondPanelSpinner.getValue());

JButton generateBtn = new JButton(Constants.GENERATE_BUTTON_TEXT);

generateBtn.addActionListener(e -> {

bipartiteGraph = new BipartiteGraph(firstGraphNodesCount, secondGraphNodesCount);

bipartiteGraph.printInConsole();

bipartiteGraph.printMaxMatchInConsole();

GraphFrame graphFrame = new GraphFrame(new GraphView(bipartiteGraph));

graphFrame.setVisible(true);

});

JPanel rootPanel = new JPanel();

rootPanel.setLayout(new BoxLayout(rootPanel, BoxLayout.PAGE_AXIS));

rootPanel.add(new JLabel(Constants.DESC_FOR_SPINNERS_TEXT));

rootPanel.add(firstPanelWithSpinner);

rootPanel.add(secondPanelWithSpinner);

rootPanel.add(generateBtn);

Container container = this.getContentPane();

container.add(rootPanel);

} }

FitstPanelWithSpinner.java

package gui;

import common.Constants;

import javax.swing.*; import java.awt.*;

public class FirstPanelWithSpinner extends JPanel{

JSpinner firstPanelSpinner;

public FirstPanelWithSpinner(){

firstPanelSpinner = new JSpinner(new SpinnerNumberModel(

Constants.DEFAULT_NUMBER_OF_NODES,

1,

Constants.MAX_NUMBER_OF_NODES,

1));

setLayout(new FlowLayout());

add(new JLabel(Constants.FIRST_SPINNER_TEXT));

add(firstPanelSpinner);

} }

SecondPanelWithSpinner.java

package gui;

import common.Constants;

import javax.swing.*; import java.awt.*;

public class SecondPanelWithSpinner extends JPanel {

JSpinner secondPanelSpinner;

public SecondPanelWithSpinner(){

secondPanelSpinner = new JSpinner(new SpinnerNumberModel(

Constants.DEFAULT_NUMBER_OF_NODES,

1,

Constants.MAX_NUMBER_OF_NODES,

1));

setLayout(new FlowLayout());

add(new JLabel(Constants.SECOND_SPINNER_TEXT));

add(secondPanelSpinner);

} }

GraphFrame.java

package gui;

import common.Constants;

import javax.swing.*;

public class GraphFrame extends JFrame{

public GraphFrame(GraphView graphView){

setTitle(Constants.GRAPH_WINDOW_TITLE);

setDefaultCloseOperation(WindowConstants.HIDE_ON_CLOSE);

setSize(Constants.GRAPH_WINDOW_WIDTH, Constants.GRAPH_WINDOW_HEIGHT);

setContentPane(graphView);

} }

BipartiteGraph.java

package graph;

import java.util.ArrayList; import java.util.Random;

public class BipartiteGraph {

private int[][] graph; //строки соответствуют вершинам первой доли, а столбцы - вершинам второй доли

private ArrayList<Boolean> usedNodes = new ArrayList<>(); //"просмотренные" узлы левого (1-го) подграфа

private ArrayList<Integer> maxMatch = new ArrayList<>(); //наибольшее паросочетание

private int matchSize = 0;

private int leftNodeNumber, rightNodeNumber;

public BipartiteGraph(int leftNodeNumber, int rightNodeNumber) {

this.leftNodeNumber = leftNodeNumber;

this.rightNodeNumber = rightNodeNumber;

graph = new int[leftNodeNumber][rightNodeNumber];

generate();

findMaxMatch();

}

public int[][] getGraph() {

return graph;

}

public ArrayList<Integer> getMaxMatch() {

return maxMatch;

}

public int getLeftNodeNumber() {

return leftNodeNumber;

}

public int getRightNodeNumber() {

return rightNodeNumber;

}

public int getMatchSize() {

return matchSize;

}

private void generate() {

Random random = new Random();

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

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

if (random.nextInt(10) <= 7) {

graph[i][j] = 1;

} else {

graph[i][j] = 0;

}

}

}

}

private void findMaxMatch() {

if(leftNodeNumber == 1 || rightNodeNumber == 1){

maxMatch.add(0);

matchSize = 1;

return;

}

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

maxMatch.add(-1);

}

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

usedNodes.add(false);

kuhnAlgorithm(i);

}

}

private boolean kuhnAlgorithm(int leftNodeIndex) {

if (usedNodes.get(leftNodeIndex)) {

return false;

}

usedNodes.set(leftNodeIndex, true);

for (int i = 0; i < graph[leftNodeIndex].length; i++) {

int to = graph[leftNodeIndex][i];

if(to > rightNodeNumber){

break;

}

if (maxMatch.get(to) == -1 || kuhnAlgorithm(maxMatch.get(to))) {

maxMatch.set(to, leftNodeIndex);

matchSize++;

return true;

}

}

return false;

}

public void printInConsole() {

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

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

if (graph[i][j] == 1) {

System.out.print(1 + " ");

} else {

System.out.print(0 + " ");

}

}

System.out.println("\n");

}

}

public void printMaxMatchInConsole() {

System.out.println("Max match:\n");

for (int match : maxMatch) {

if (match != -1) {

System.out.println(match + " -> " + maxMatch.indexOf(match));

}

}

System.out.println("match size = " + matchSize);

} }

GraphView.java

package gui;

import common.Constants; import graph.BipartiteGraph;

import javax.swing.*; import java.awt.*;

public class GraphView extends JPanel {

private BipartiteGraph bipartiteGraph;

private int[][] graph;

private final int leftXOffset = 20;

private final int rightXOffset = leftXOffset + 200;

private final int yOffset = 50;

public GraphView(BipartiteGraph bipartiteGraph) {

this.bipartiteGraph = bipartiteGraph;

this.graph = bipartiteGraph.getGraph();

}

@Override

protected void paintComponent(Graphics g) {

drawLeftNodes(g);

drawRightNodes(g);

drawEdges(g);

drawMatchNumber(g);

}

private void drawLeftNodes(Graphics g) {

int y;

for (int i = 0; i < bipartiteGraph.getLeftNodeNumber(); i++) {

y = yOffset * (i + 1);

g.drawOval(leftXOffset, y, Constants.NODE_WIDTH, Constants.NODE_HEIGHT);

}

}

private void drawRightNodes(Graphics g) {

int y;

for (int i = 0; i < bipartiteGraph.getRightNodeNumber(); i++) {

y = yOffset * (i + 1);

g.drawOval(rightXOffset, y, Constants.NODE_WIDTH, Constants.NODE_HEIGHT);

}

}

private void drawEdges(Graphics g) {

for (int i = 0; i < bipartiteGraph.getLeftNodeNumber(); i++) {

for (int j = 0; j < bipartiteGraph.getRightNodeNumber(); j++) {

if (graph[i][j] == 1) {

drawEdge(g, i, j);

}

}

}

for (int match : bipartiteGraph.getMaxMatch()) {

if (match != -1) {

drawEdgeColored(g, match, bipartiteGraph.getMaxMatch().indexOf(match));

}

}

}

private void drawEdge(Graphics g, int leftNodeIndex, int rightNodeIndex) {

int y1 = yOffset * (leftNodeIndex + 1) + (Constants.NODE_HEIGHT / 2);

int y2 = yOffset * (rightNodeIndex + 1) + (Constants.NODE_HEIGHT / 2);

int x1 = leftXOffset + Constants.NODE_WIDTH;

g.drawLine(x1, y1, rightXOffset, y2);

}

private void drawEdgeColored(Graphics g, int leftNodeIndex, int rightNodeIndex) {

g.setColor(Color.RED);

drawEdge(g, leftNodeIndex, rightNodeIndex);

g.setColor(Color.BLACK);

}

private void drawMatchNumber(Graphics g) {

g.drawString(Constants.MATCH_SIZE_TEXT + bipartiteGraph.getMatchSize(), 20, 20); } }

Заключение

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

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

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

1. Р. Стивенс - «Алгоритмы. Теория и практическое применение»

2. Ф.Новиков - «Дискретная математика»

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