отчет по 2 лабе
Описание файла
Документ из архива "отчет по 2 лабе", который расположен в категории "". Всё это находится в предмете "параллельные компьютерные системы" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "параллельные компьютерные системы" в общих файлах.
Онлайн просмотр документа "отчет по 2 лабе"
Текст из документа "отчет по 2 лабе"
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Московский Государственный Технический Университет имени Н.Э. Баумана»
(МГТУ им. Н.Э. Баумана)
Факультет «Информатика и системы управления»
Кафедра «Компьютерные системы и сети»
Отчёт
по лабораторной работе № 2
«ВЫЧИСЛЕНИЕ НАИБОЛЬШЕГО ПАРОСОЧЕТАНИЯ МЕТОДОМ ХОПКРОФТА-КАРПА»
по курсу
«Параллельные компьютерные системы»
Преподаватель,
к. т. н., доц. ______________________ Можаров Г.П.
Исполнитель,
студ. гр. ИУ6-119 __________________ Денисов А.В.
Москва,
2014 год
Цель работы – написать и отладить программу нахождения наибольшего паросочетания методом Хопкрофта-Карпа.
Ответы на контрольные вопросы
1. Какие графы называются двудольными?
Двудольными называются неориентированные графы такие, что множества их вершин можно разбить на 2 непересекающиеся множества , причём каждое ребро имеет вид , где .
2. Что собой представляет паросочетание в неориентированном графе ?
Паросочетание в неориентированном графе - это произвольное множество рёбер такое, что никакие два ребра из не инцидентны одной вершине.
3. Что понимается под термином чередующаяся цепь?
Для данного паросочетания чередующейся цепью относительно называют произвольное множество дуг вида
где >0, все вершины различны, свободная вершина в свободная вершина в , каждая вторая дуга принадлежит .
4. Когда паросочетание в двудольном графе наибольшее?
Паросочетание в двудольном графе наибольшее тогда и только тогда, когда в не существует чередующейся цепи относительно .
Описание обрабатывающего алгоритма
Главная программа
Для всех вершин сначала отсутствуют паросочетания. Строится вспомогательный граф, состоящий из свободных вершин x и соединённых с ними вершин y, а также истока и стока. Далее в цикле находятся паросочетания и снова строится вспомогательный граф. Условием выхода из цикла является наличие во вспомогательном графе единственной вершины – истока, т.е. в графе уже нет свободных вершин x.
Блок схема алгоритма основной программы показана на рисунке 1.
Рисунок 1 - Блок-схема алгоритма главной программы.
Процедура PGA
В данной процедуре сначала выполняется инициализации всех вершин, очистка очереди и добавление во вспомогательный граф вершины s. Затем во вспомогательный граф добавляются все свободные вершины x. Затем разбирается очередь, откуда каждая вершина добавляется во вспомогательный граф. Если вершина из Y, то в зависимости от того, свободная она или нет, происходит инициализация либо вершины t, либо состоящей в паросочетании с данной вершиной вершины x. При этом вершина x добавляется в очередь, а вершина t – сразу во вспомогательный граф.
Если вершина из очереди принадлежит множеству X, то проверяются связанные с ней вершины y. Каждая неинициализированная вершина добавляется в очередь и инициализируется.
Блок-схема алгоритма данной процедуры приведена на рисунке 2.
Рисунок 2 – Блок-схема алгоритма процедуры PGA.
Процедура ФАЗА
Паросочетания ищутся следующим образом: в стек помещается вершина s и среди связанных с ней вершин ищутся ещё не рассмотренные и помещаются в стек. Далее для каждой из них также ищутся новые связанные с ней вершины. Если такой вершиной будет t, то считается, что найдена чередующаяся цепь, которая разбирается на паросочетания. В противном случае, вершина добавляется в стек. Если новых вершин не обнаружено, из стека удаляется верхний элемент. Эта последовательность действий повторяется до тех пор, пока в стеке не останется вершин.
Блок-схема алгоритма данной процедуры приведена на рисунке 3.
Рисунок 3 – Блок-схема алгоритма процедуры ФАЗА.
Примеры экранных форм
Пример работы программы приведен на рисунке 4.
Рисунок 4 – Пример выполнения расчета №1.