Паросочетания в двудольных графах - раздел Математика, ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Двудольные Графы Упоминались Ранее, Но Формального Определени...
Двудольные графы упоминались ранее, но формального определения не было.
ОПРЕДЕЛЕНИЕ 32.Граф Г называется двудольным, если множество его вершин является объединением двух непересекающихся множеств A и B таких, что никакие две вершины из каждого из этих множеств не являются смежными.
Таким образом, смежными в двудольном графе могут быть только вершины из разных множеств.
Рассматриваются и аналоги таких графов, в которых число «долей» больше двух, здесь мы такие графы не рассматриваем.
Приведем две ситуации, приводящие к подобным графам.
1. Задача о назначениях. Одно из множеств вершин это должности, втрое – претенденты. Наличие дуги означает, что претендента на должность можно рекомендовать. При этом на одну должность можно рекомендовать нескольких претендентов, а одному претенденту может подходить несколько должностей.
2. Задача о свадьбах. Одно из множеств вершин это невесты, другое – женихи.
Паросочетание в этих примерах можно интерпретировать как способ выбрать претендентов на должности или подобрать потенциальные семейные пары.
Особый интерес представляют графы, в которых |A|=|B|, т.е. когда в приведенных примерах претендентов столько же, сколько и должностей, а женихов столько же, сколько и невест. В случае |A|=|B| можно поставить вопрос о возможности замещения всех вакансий или подбора подходящих женихов для всех невест (разумеется, и наоборот). Паросочетание в двудольном графе при |A|=|B|=n, содержащее n дуг, естественно назвать полным. Полное паросочетание одновременно является и минимальным реберным покрытием. Следующая замечательная теорема является критерием существования полного паросочетания. Пусть A1ÌA. Через Г(A1) обозначим множество вершин, смежных с вершинами из A1. Разумеется, Г(A1)ÌB.
Теорема 25. (Холл) Полное паросочетание в двудольном графе, у которого |A|=|B|, существует тогда и только тогда, когда для любого множества вершин A1ÌA выполняется неравенство |A1|≤|Г(A1)|.
В примере с женихами и невестами это означает, что для любой группы невест число женихов, подходящих хотя бы одной из этих невест, не меньше числа невест в группе. Далее будем говорить о женихах и невестах – так веселее, чем просто о множествах!
Доказательство. Если полное паросочетание существует, то любой группе невест соответствуют как минимум те женихи, которые инцидентны дугам паросочетания (а может быть и еще какие-нибудь), т.е. подходящих женихов не меньше, чем невест в группе. Таким образом, условие выполняется.
Обратное будем доказывать индукцией по числу невест (n). Если n=1, то единственной невесте подходит как минимум один жених, а жених при этом всего один и полное паросочетание существует.
Пусть полное паросочетание при выполнении условия теоремы существует при 1,…,n. Докажем, что это так и при n+1.
Рассмотрим вначале ситуацию, когда существует множество A¢ÌA, A¢¹A такое, что |A¢|=|Г(A¢)|, т.е. есть группа невест, которым в совокупности подходят ровно столько женихов, сколько невест в группе. Пусть B¢=Г(A¢). Поскольку Г(A1)ÌB¢ при A1ÌA¢, то подграф, порожденный множеством вершин A¢ÈB¢, обладает нужным свойствам, причем число вершин в каждой «доле» не превосходит n. По предположению индукции, каждой невесте из A¢ можно подобрать жениха (естественно, из Г(A¢)). Пусть A¢¢=AA¢, B¢¢=BB¢. Если бы выполнялось условие Г(A¢¢)=B¢¢, то можно было бы действовать точно так же, как и с множеством A¢, но может оказаться, что невестам из A¢¢ подходят и некоторые женихи из B¢. Но оказывается все равно для двудольного подграфа исходного графа, порожденного множеством вершин A¢¢ÈB¢¢ условие теоремы соблюдается. Пусть A1ÌA¢¢. Множество Г(A1) распадается на два подмножества: B1¢=Г(A1)ÇB¢, B1¢¢=Г(A1)ÇB¢¢. Необходимо доказать, что |B1¢¢|³|A1|. Для этого рассмотрим более широкое множество A1ÈA¢. По условию |A1ÈA¢|≤|Г(A1ÈA¢)|. Поскольку
Г(A1ÈA¢)=Г(A1)ÈГ(A¢)=B¢ÈB1¢¢ и множества в правой части (как и A1, A¢) не пересекаются, то |A1|+|A¢|≤|B¢|+|B1¢¢|. Но по предположению |A¢|=|B¢|, откуда и следует нужное неравенство.
Пусть теперь |A¢|<|Г(A¢)| для любого A¢ÌA, A¢¹A. Выберем любую невесту. Ей подходит более одного жениха. Удалим эту невесту вместе с любым подходящим ей женихом. В каждой «доле» оставшегося двудольного графа по n элементов. Пусть A1ÌA и в это множество не входит невеста, которую мы исключили из рассмотрения (успешно выдали замуж). По предположению, этой группе невест в исходном двудольном графе подходит больше женихов, чем невест в группе. Возможно, сюда входит и исключенный жених. Тогда без него число подходящих женихов не меньше, чем число невест в A1, т.е. для оставшегося двудольного графа (с меньшим числом вершин) условие теоремы выполняется, т.е. полное паросочетание в «усеченном» двудольном графе существует, что и завершает доказательство.
Теорема Холла, несмотря на ее элегантность, трудно применима к реальной проверке существования полного паросочетания на практике и тем более к его построению. Разработано множество алгоритмов построения паросочетания (или проверки его отсутствия). Одним из методов является поиск с возвращением. Для этого удобно двудольный граф записать в виде таблицы размеров n´n, в которой отмечены клетки, соответствующие дугам.
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования... Уфимский государственный авиационный технический университет...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Паросочетания в двудольных графах
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Основной принцип комбинаторики
1.1.1 . От Москвы до Уфы можно добраться поездом, самолетом или теплоходом, а от Уфы до Чишмов – поездом, автобусом или на такси. Сколькими способами можно в совокупности добраться
Размещения с повторениями
1.2.1 . Замок в автоматической камере хранения состоит из 4 дисков, на каждом из которых написаны буквы а, б, в, г, д, е. Сколько различных кодов можно получить?
1.2.2 . В
Размещения без повторений
1.3.1 . Сколько словарей следует издать, чтобы можно было переводить тексты непосредственно с любого из шести языков на каждый из них? А если языков десять?
1.3.2 . Каков о
Перестановки
1.4.1 .Сколькими способами могут встать в очередь 10 человек?
1.4.2 . Каков ответ в задаче 1.3.3, если студентов 20?
1.4.3 . Каков ответ в задаче 1.3.4, если разли
Сочетания (без повторений)
1.5.1 .В шахматном турнире участвовали 10 человек. Сколько состоялось партий, если каждая пара игроков встретилась один раз?
1.5.2 .Из колоды карт (36 штук) игрок получает
Свойства биномиальных коэффициентов
1.6.1. Докажите, что . Сделайте это четырьмя способами: по определению, по формуле и используя результаты задач 1.5.6 и 1.5.7.
1.6.2. Докажите, что
.
Сдел
Разбиения множеств
Число сочетаний можно интерпретировать как число способов, которым n-элементное множество можно разбить на два подмножества, в одном из которых m, а во втором ( ) элем
Сочетания с повторениями
1.8.1. В магазине продаются карандаши двух видов. Сколькими способами можно купить пять штук? А если надо купить 8 карандашей 4 видов?
1.8.2. Каков ответ в задаче 1.2.4, ес
Разные задачи
В предыдущих параграфах вы познакомились с основными приемами элементарной комбинаторики. В этом параграфе эти приемы (или их комбинации) применяются в различных ситуациях.
Производящие функции
По биному Ньютона (задача 1.5.7) коэффициентами многочлена являются величины .
1.10.1. Каков смысл коэффициентов при zm многочленов
Использование рекуррентных соотношений
1.11.1. Пусть f(n.m) – число сочетаний с повторениями из n по m (задача 8.4). Проверьте, что
1.11.2. f(n.0)=1, f(
Формула включений и исключений
1.12.1. В группе 25 студентов, 15 занимаются лыжами, 12 – коньками, 8 и тем, и другим. Сколько студентов не занимается этими видами спорта?
1.12.2. (Обобщение) Проверьте, ч
Булеан множества
Каждое множество порождает новое множество несколько необычным образом.
ОПРЕДЕЛЕНИЕ 1. Булеаном множестваA называется совокупность всех подмножеств множества A
Отношения на множествах
ОПРЕДЕЛЕНИЕ 3. n-арным отношением на множествеA называется подмножество G прямого произведения An. Таким образом, n-арное отношение на A
Отображения (функции)
С понятием «функция»в некоторых частных случаях вы познакомились в школе. Приведем общее определение.
ОПРЕДЕЛЕНИЕ 7. Пусть A, B - множества. Отображением(ф
Мощность множеств
Речь пойдет о том, как сравнивать между собой разные множества. Начнем с простого примера. Перед вами кучки болтов и гаек. Требуется ответить на вопрос: поровну ли деталей в этих ку
Счетные множества
ОПРЕДЕЛЕНИЕ 15. Множество, равномощное множеству N, называется счетным.
Иными словами счетными являются такие множества, элементы которых можно занумеровать н
Некоторые свойства бесконечных множеств
Уже отмечалось, что конечное множество не равномощно своей части, в то же время, бесконечное множество может быть равномощным своей части. Оказывается, это характеристическое
Вопросы для самопроверки
1. Что такое объединение, пересечение, дополнение, симметрическая разность множеств?
2. Какими алгебраическими свойствами обладают операции над множествами?
3. Что
Упражнения
1. Существуют ли такие множества A,B,C, что
2. Справедливы ли следующие утверждения для любых A,B,C?
А) Если A¹B и B¹ C, то
Компьютерные представления графов
Естественно, графы представляются в виде некоторых наборов данных. Подобных представлений существует множество, у каждого есть свои достоинства и недостатки. Общий недостаток состои
Маршруты и связность
ОПРЕДЕЛЕНИЕ 22.Маршрутом (путем)в графе называется последовательность вида , где v – вершины, e – дуги, . Этот маршрут соединяет вершины
Кратчайшие пути в графах
Рассмотрим следующую задачу. В графе Г выделены две вершины: b (начальная) и e (конечная). Требуется найти все пути минимальной длины из b в e (если e
Деревья
ОПРЕДЕЛЕНИЕ 25.Лесомназывается неориентированный граф без циклов. Деревомназывается связный лес.
Таким образом, дерево характеризуется тремя
ПРЕДЛОЖЕНИЕ.
1. Всякие две вершины дерева можно соединить единственной цепью.
2. Если в дереве не менее двух вершин, то у него не менее двух листов.
Доказательство.
1. Поскольку дерев
Кодирование деревьев
Для помеченных деревьев существует эффективный способ кодирования(его можно использовать для компьютерного представления деревьев).
Найдем лист с минимальным номером, удали
Центр дерева
Под расстоянием d(a,b) между вершинами неориентированного графа, как и ранее, понимается минимальное число дуг в пути, соединяющем эти вершины.
Минимальное остовное дерево(остов)
Пусть некоторое семейство пунктов требуется связать сетью дорог. Известна стоимость прокладки дороги между теми парами пунктов, для которых это возможно. Стоимость прокладки сети до
Эйлеровы графы
Вернемся к задаче Эйлера о кенигсбергских мостах. По существу, задача сводится к построению в графе цикла, который содержит каждую дугу графа по одному разу. Графы, в которых такой
Гамильтоновы графы
Понятие гамильтонова графа очень близко к понятию эйлерова графа, но между ними пропасть, как вскоре выяснится!
ОПРЕДЕЛЕНИЕ 28.Цикл в графе называется г
Графовые векторы
Понятие степени вершины было введено выше.
ОПРЕДЕЛЕНИЕ 29.Графовым вектором(иногда говорят о графовом разбиении) неориентированного графа называется
Паросочетания и реберные покрытия
ОПРЕДЕЛЕНИЕ 30.Паросочетаниемв неориентированном графе называется семейство дуг, попарно не имеющих общих вершин.
Очевидно, что подмножество паросоч
Правильная нумерация вершин графа
ОПРЕДЕЛЕНИЕ 33.Нумерация вершин в ориентированном графе называется правильной(или топологической), если наличие дуги (vi,vj
Сетевые графики
ОПРЕДЕЛЕНИЕ 34.Сетевым графикомназывается ориентированный взвешенный ациклический граф с единственным истоком и единственным стоком.
Сетевые графики
Потоки в сетях
Весам дуг можно дать иную интерпретацию, в результате возникает интересная и важная задача. Пусть в ориентированном взвешенном графе выделены две вершины (b – начальная и
Вопросы для самопроверки
1. Что такое граф? Из чего он состоит? Какие виды графов вы знаете?
2. Какие вершины, дуги называются смежными? Инцидентными?
3. Какие графы называются изоморфными
Упражнения
1. Существует ли неориентированный граф, степени всех вершин которого различны?
2. Постройте неориентированный граф, степени вершин которого равны 2,2,2,3,3,4,5. Существует
Предметный указатель
n-арное отношение на множестве, 21
алгоритм Дейкстры, 50
алгоритм построения матрицы достижимости, 48
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов