Двудольные графы и паросочетания
Этапы разработки программы для решения задачи нахождения наибольшего паросочетания в двудольном графе. Модули программы: характеристика и алгоритмы тестирования. Особенности разработки графического интерфейса с возможностью ввода и вывода информации.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 21.02.2019 |
| Размер файла | 195,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Введение
Задачи теории графов имеют важное практическое значение. Особый интерес для научной и инженерной деятельности представляют алгоритмические аспекты таких задач.
На практике, при проектировании сложных технических систем, важно уметь построить модели этих систем в виде графов, а затем вычислить их характеристики, такие, как наибольшее паросочетание, наибольшее независимое множество вершин и рёбер, остовное дерево и т.д. Таким образом, для решения практических задач проектирования и исследования технических систем, надо иметь соответствующие алгоритмы, в конечном счёте, программы для ЭВМ.
Постановка задачи
Написать программу для решения задачи нахождения наибольшего паросочетания в двудольном графе.
Программа должна предоставлять пользователю возможность задавать множество и выводить все возможные перестановки этого множества на экран. Для удобства использования программы должен быть разработан графический интерфейс с возможностью ввода и вывода информации.
Устройствами ввода информации являются клавиатура и мышь.
Программа должна быть разработана для работы в операционной системе Microsoft Windows.
1.Описание алгоритма поставленной задачи
Необходимые определения:
Паросочетанием M называется набор попарно несмежных рёбер графа (иными словами, любой вершине графа должно быть инцидентно не более одного ребра из множества M). Мощностью паросочетания назовём количество рёбер в нём. Наибольшим (или максимальным) паросочетанием назовём паросочетание, мощность которого максимальна среди всех возможных паросочетаний в данном графе. Все те вершины, у которых есть смежное ребро из паросочетания (т.е. которые имеют степень ровно один в подграфе, образованном M), назовём насыщенными этим паросочетанием.
Цепью длины k назовём некоторый простой путь (т.е. не содержащий повторяющихся вершин или рёбер), содержащий k рёбер.
Чередующейся цепью (в двудольном графе, относительно некоторого паросочетания) назовём цепь, в которой рёбра поочередно принадлежат/не принадлежат паросочетанию.
Увеличивающей цепью (в двудольном графе, относительно некоторого паросочетания) назовём чередующуюся цепь, у которой начальная и конечная вершины не принадлежат паросочетанию.
Теорема Бержа
Формулировка: Паросочетание является максимальным тогда и только тогда, когда не существует увеличивающих относительно него цепей.
Алгоритм Куна
Алгоритм Куна -- непосредственное применение теоремы Бержа. Его можно кратко описать так: сначала возьмём пустое паросочетание, а потом -- пока в графе удаётся найти увеличивающую цепь, -- будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось -- процесс останавливаем, -- текущее паросочетание и есть максимальное.
Алгоритм Куна -- просто ищет любую из таких цепей с помощью обхода в глубину или в ширину. Алгоритм Куна просматривает все вершины графа по очереди, запуская из каждой обход, пытающийся найти увеличивающую цепь, начинающуюся в этой вершине.
Удобнее описывать этот алгоритм, считая, что граф уже разбит на две доли.
Алгоритм просматривает все вершины v первой доли графа: v = 1…n1. Если текущая вершина v уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем. Иначе -- алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.
Поиск увеличивающей цепи осуществляется с помощью специального обхода в глубину или ширину (обычно в целях простоты реализации используют именно обход в глубину). Изначально обход в глубину стоит в текущей ненасыщенной вершине v первой доли. Просматриваем все рёбра из этой вершины, пусть текущее ребро -- это ребро (v,to). Если вершина to ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра (v,to); в таком случае просто включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины v. Иначе, -- если to уже насыщена каким-то ребром (p,to), то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра (v,to), (to,p). Для этого просто перейдём в нашем обходе в вершину p -- теперь мы уже пробуем найти увеличивающую цепь из этой вершины.
Можно понять, что в результате этот обход, запущенный из вершины v, либо найдёт увеличивающую цепь, и тем самым насытит вершину v, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина v уже не сможет стать насыщенной). После того, как все вершины v = 1…n1 будут просмотрены, текущее паросочетание будет максимальным.
2.Пример ручного расчета задачи и вычислений
На рисунке 1 представлен исходный двудольный граф.
Рисунок 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 - Окно с отображением графа
4.Модули программы
Main.java - точка входа в программу. В этом классе создается главное (первое) окно программы.
Constants.java - здесь задаются все строковые и числовые константы.
MainGUI.java - в этом модуле прописан графический интерфейс главного окна, а также обработка взаимодействий с элементами графического интерфейса.
FirstPanelWithSpinner - здесь описывается текстовое поле вывода и «спиннер» для выбора количества ребер у первого подграфа.
SpinnerPanelWithSpinner - здесь описывается текстовое поле вывода и «спиннер» для выбора количества ребер у второго подграфа.
GraphFrame.java - в этом модуле создается окно для отображения графа.
BipartiteGraph.java - описывает двудольный граф и методы для работы с ним.
GraphView.java - этот модуль содержит функции для отображения графа и информации о нем.
5.Тесты
В качестве среды разработки была выбрана программа Intellij IDEA которая содержит в себе все необходимые средства для разработки и отладки модулей и программ на языке java (и не только). Для отладки программы использовались различные инструменты: точка остановки, пошаговое выполнение кода программы, анализ содержимого глобальных и локальных переменных.
Тестирование проводилось в рабочем порядке, в процессе разработки и после завершения написания программы.
Тестирование программы представлено на рисунках 4, 5, 6.
6.Результаты работы программы
Результаты работы программы представлены на рисунках 4-6.
Рисунок 4 - Тест 1
Рисунок 5 - Тест 2
Рисунок 6 - Тест 3
7.Листинг программы
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. Ф.Новиков - «Дискретная математика»
3. Электронный ресурс https://ru.wikipedia.org/ дата обращения: 16.11.17
Размещено на Allbest.ru
Подобные документы
Понятия и определения орграфа и неориентированного графа, методы решения. Неориентированные и ориентированные деревья. Подробное описание алгоритмов нахождения кратчайших путей в графе: мультиграф, псевдограф. Матрица достижимостей и контрдостижимостей.
курсовая работа [251,0 K], добавлен 16.01.2012Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.
курсовая работа [330,2 K], добавлен 25.11.2011Теория высшей алгебры в решении задач элементарной математики. Программы для нахождения частного и остатка при делении многочленов, наибольшего общего делителя двух многочленов, производной многочлена; разложения многочленов на кратные множители.
дипломная работа [462,8 K], добавлен 09.01.2009Характеристики метода Эйлера. Параметры программы, предназначенной для решения систем линейных уравнений и ее логическая структура. Блок-схема программы и этапы ее работы. Проведение анализа результатов тестирования, исходя из графиков интераций.
курсовая работа [866,0 K], добавлен 27.03.2011Сущность графического метода нахождения оптимального значения целевой функции. Особенности и этапы симплексного метода решения задачи линейного программирования, понятие базисных и небазисных переменных, сравнение численных значений результатов.
задача [394,9 K], добавлен 21.08.2010Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Вычисление корня функции нелинейного уравнения методом деления отрезка пополам. Способы ввода, вывода и организации данных. Модульная организация программы. Разработка блок-схемы алгоритма задачи. Порядок создания программы на алгоритмическом языке.
реферат [30,0 K], добавлен 28.10.2010Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Модельная задача уравнения колебаний струны и деформации системы из трех струн. Вариационные методы решения: экстремум функционала, пробные функции, метод Ритца. Подпространства сплайнов и тестирование программы решения системы алгебраических уравнений.
дипломная работа [1,1 M], добавлен 29.06.2012Назначение, состав и структура математического обеспечения в автоматизированных системах, формализация и моделирование управленческих решений, этапы разработки. Модели и алгоритмы обработки информации. Характеристика метода исследования операции.
презентация [17,7 K], добавлен 07.05.2011
