![]() Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Лабораторная работа № 4.
Наибольшее паросочетание
Цель работы: 1) Рассмотреть понятие двудольный граф. 2) Изучить понятие паросочетание. 3) Научиться определять наибольшее паросочетание. Литература: 1) " Графы и их применение", Березина Л.Ю., М.: Просвещение, 1979г. 2) " Теория графов. Алгоритмический подход", Кристофидес II. 3) " Применение теории графов в программировании", Евстигнеев В.А. - М.: Наука, 1985г. Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задание: Имеется m мужчин и n женщин. Каждый мужчина указывает несколько (может, нуль; может, одну; может, много) женщин, на которых он согласен жениться. Мнение женщин не спрашивают. Заключить наибольшее количество моногамных браков. Можно поставить эту задачу в терминах теории графов: Дан двудольный граф Bm, n. Найти наибольшее паросочетание. Краткие теоретические сведения: Двудольным графом называется граф Г( Паросочетанием называется множество ребер, не имеющих общих вершин. На рис. а) показан пример паросочетания, а на рис. б) - пример наибольшего паросочетания. 1 2 3 4 5
a)
1` 2` 3` 4` 5`
1 2 3 4 5
б)
1` 2` 3` 4` 5` Для решения задачи о наибольшем паросочетании применяется метод чередующихся цепей. Пусть М -паросочетание в двудольном графе. Цепь, в которую поочередно входят ребра из М (жирные) и из пе-М (тонкие) назовем чередующейся относительно М. Например, на рис. а) цепь (1, 1`, 2, 3`) -чередующаяся. Вершины, инцидентные ребрам, из М назовем насыщенными, прочие - ненасыщенными. Очевидно, что если в графе существует чередующаяся относительно М цепь с ненасыщенными концевыми вершинами (т.е. тонкими концевыми ребрами), то в ней тонких ребер на одно больше, чем жирных. Если цепь " перекрасить", т.е. сделать все жирные ребра тонкими, а тонкие - жирными, то число жирных ребер, а, следовательно, и паросочетание увеличатся на одно ребро. Чередующаяся относительно М цепь с ненасыщенными концевыми вершинами называется увеличивающей относительно М цепью. Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок. — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта. — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы). — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание. SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение Теорема: Паросочетание М является наибольшим тогда и только тогда, когда нет увеличивающих относительно М цепей. Данная теорема служит основой для алгоритма нахождения наибольшего паросочетания. Содержание отчета: 1) Составление алгоритмов. 2) Написание программы на языке Turbo Pascal. 3) Отладка программы. Контрольные вопросы: 1) Какой граф называется двудольным? 2) Дайте понятие паросочетания. 3) Какая цепь графа называется чередующейся относительно М? 4) Какая цепь графа называется увеличивающейся относительно М? 5) Сформулируйте метод чередующихся цепей.
|