Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    Сам записывает клиентов и напоминает им о визите;
    Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом
  • Лабораторная работа № 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`) -чередующаяся. Вершины, инцидентные ребрам, из М назовем насыщенными, прочие - ненасыщенными. Очевидно, что если в графе существует чередующаяся относительно М цепь с ненасыщенными концевыми вершинами (т.е. тонкими концевыми ребрами), то в ней тонких ребер на одно больше, чем жирных. Если цепь " перекрасить", т.е. сделать все жирные ребра тонкими, а тонкие - жирными, то число жирных ребер, а, следовательно, и паросочетание увеличатся на одно ребро. Чередующаяся относительно М цепь с ненасыщенными концевыми вершинами называется увеличивающей относительно М цепью.

    Теорема:

    Паросочетание М является наибольшим тогда и только тогда, когда нет увеличивающих относительно М цепей. Данная теорема служит основой для алгоритма нахождения наибольшего паросочетания.

    Содержание отчета:

    1) Составление алгоритмов.

    2) Написание программы на языке Turbo Pascal.

    3) Отладка программы.

    Контрольные вопросы:

    1) Какой граф называется двудольным?

    2) Дайте понятие паросочетания.

    3) Какая цепь графа называется чередующейся относительно М?

    4) Какая цепь графа называется увеличивающейся относительно М?

    5) Сформулируйте метод чередующихся цепей.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.