Теорема Холла — это… Что такое Теорема Холла?
Теорема Холла (или теорема о свадьбах), утверждает, что если в двудольном графе для любого любые элементов одной из долей связаны по крайней мере с элементами другой, то граф разбивается на пары.
Названна в честь английского математика Филипа Холла (англ.).
Теорема обобщается на граф, имеющий произвольное (не обязательно конечное или счётное) множество долей.
Пусть мощность первой доли — . Сделаем из данного графа сеть. Для этого на каждом ребре введем пропускную способность по 1 в направлении от вершины первой доли к вершине второй. При этом создадим две дополнительные вершины — и , от первой проведем все стрелки в вершины первой доли, а из каждой вершины второй проведем стрелки во вторую добавленную вершину. Заметим, что получившаяся сеть — целочисленная, то есть в ней существует максимальный целочисленный поток, и что если мы сможем доказать, что пропускная способность минимального разреза равна , то по теореме Форда-Фалкерсона величина максимального потока равна пропускной способности минимального разреза, то есть тоже равна . Очевидно, что если в бинарной транспортной сети величина максимального потока равна , то существует непересекающихся по вершинам путей из истока в сток. Это следует из алгоритма для нахождения максимального целочисленного потока в целочисленном графе, а из каждого такого пути можно выбрать смежную пару вершин из разных долей исходного графа.
То, что мощность минимального разреза не превышает , очевидно — достаточно рассмотреть разрез, в котором множество содержит одну вершину .
Теперь рассмотрим произвольный разрез . Пусть в попали ровно вершин из первой доли и из второй.
- Пусть . Тогда пропускная способность разреза складывается из рёбер, ведущих из в вершины первой доли, лежащие в и рёбер, ведущих из вершин второй доли, лежащих в , в . Суммируя, получаем: .
- Иначе, . По условию теоремы, эти вершин связаны с вершинами второй доли, а так как , то они связаны хотя бы с вершинами во второй доле, попавшими во множество . Тогда пропускная способность разреза рассчитывается так же, как в предыдущем пункте, плюс рёбер из вершин первой доли, принадлежащих в вершины второй доли, принадлежащими . Итого, .
В обоих случаях величина максимального потока равна , что и требовалось доказать.
Ссылки
(PDF) Задачи о фокусниках и теоремы Холла и Шпернера
З А Д А Ч И О Ф О К У С Н И К А Х И Т Е О Р Е М Ы Х О Л Л А И Ш П Е Р Н Е Р А 17
Задача 4. Зритель пишет на доске
слева направо n цифр. Помощник фокус-
ника закрывает одну из цифр красной
карточкой, другую синей, еще одну зеле-
ной. После этого входит фокусник и
называет закрытые цифры. При каком
наименьшем n такой фокус возможен?
Ответ: при n = 12.
Решение. Пусть 1
V и 2
V – множества
тех «картинок», которые могут увидеть
помощник и фокусник соответственно.
Рассмотрим двудольный граф
12
,
GV V ,
ребра которого описывают возможные пе-
реходы от картинок из 1
V к картинкам из
2
V. Граф полурегулярный, 110n
V ,
21 2
Vn n n
•3
10n. По следствию
2, для существования совершенного паро-
сочетания из 1
V в 2
V необходимо и доста-
точно, чтобы в доле 2
V вершин было не
меньше, чем
в 1
V. Отсюда
12
n n n
t
3
10
t, что равносильно
неравенству 12
nt.
Таким образом, наименьшее значение n
равно 12.
Покажем, как фокус осуществить прак-
тически при 12
nt. Места, где записаны
первые 12 цифр, пронумеруем слева на-
право: 1, 2, …, 9, 0, 11, 12 (остальные
места, если они есть, не нумеруем!). Пусть
S – сумма всех записанных зрителем цифр.
Будем действовать за помощника следую-
щим образом. Закроем красной карточкой
место, номер которого является последней
цифрой числа S, после чего мысленно
удалим это место, а синей карточкой закроем
место с номером, равным цифре, которая
спрятана под красной карточкой. Затем
зеленой карточкой закроем место, номер
которого (вычисленный после «удаления»
цифр, находящихся под красной и синей
карточками) спрятан под синей карточкой.
Теперь фокусник по положению зеленой
карточки поймет, какая цифра под синей,
а по положению синей карточки – какая
цифра под красной. Все цифры, кроме
той, которая под зеленой карточкой, уже
известны фокуснику, а положение крас-
ной карточки говорит о последней цифре
суммы всех цифр, записанных зрителем.
Поэтому фокусник сможет определить
цифру и под зеленой карточкой.
Задачи для самостоятельного решения
Приведем подборку задач 1, при реше-
нии которых возможно применение теоре-
мы Холла. Некоторые задачи совсем про-
стые (решаются простой ссылкой, напри-
мер, на следствие 1; нужно лишь увидеть
соответствующий двудольный граф!), не-
которые предлагались на школьных и сту-
денческих олимпиадах различного уров-
ня. Задачи 11–15 посвящены доказатель-
ству и применениям теоремы Шпернера.
1. Имеется бесконечное множество юношей
и бесконечное множество девушек. Для лю-
бого натурального числа k верно, что любые
k юношей знакомы в совокупности не менее
чем с k девушками. Верно ли, что всех юно-
шей удастся одновременно поженить на зна-
комых им девушках? Другими словами, спра-
ведлива ли теорема Холла в случае бесконеч-
ного графа?
2. Решите задачу 1 в предположении счетно-
сти 2 множеств юношей и девушек.
3. В некотором районе, состоящем из не-
скольких деревень, число женихов равно чис-
лу невест. В каждой деревне общее число
женихов и невест не больше половины общего
их числа. Докажите, что можно всех переже-
нить так, чтобы в каждой паре жених и невеста
были из разных деревень.
4. Однокруговой волейбольный турнир 2n
команд продолжался 2n –
1 дней. Каждый день
проходило n игр, каждая команда в один день
проводила ровно одну игру. По окончании
турнира организаторы решили наградить тор-
тами некоторые команды: за каждый игровой
1 Задача 3 предлагалась на III этапе Россий-
ской олимпиады школьников 1995 года, задача
4 – на Putnam Competition 2012 года, задача 14
– на Московской олимпиаде 2017 года, задача
15 – на Открытой олимпиаде ФМЛ 239 в 2004
году. Остальные задачи взяты из сборников
[3,4].
2 Множество называется счетным, если су-
ществует взаимно однозначное соответствие
между ним и множеством натуральных чисел
(другими словами, элементы данного беско-
нечного множества можно пронумеровать на-
туральными числами). Счетными являются
множества натуральных чисел, неотрицатель-
ных целых чисел, целых чисел, рациональных
чисел.
НОУ ИНТУИТ | Лекция | Паросочетания и свадьбы
Аннотация: Паросочетания и свадьбы. Теорема Холла о свадьбах. Приложение теоремы Холла. Латинские квадраты.
Паросочетания и свадьбы
Результаты этой главы носят более комбинаторный характер, чем результаты всех предыдущих глав, хотя они тесно связаны с теорией графов. Обсудим хорошо известную «теорему о свадьбах», принадлежащую Филиппу Холлу, и некоторые приложения этой теоремы, например, построение латинских квадратов.
Теорема Холла о свадьбах
Теорема о свадьбах, доказанная Филиппом Холлом в 1935 г., отвечает на следующий вопрос, известный под названием задачи о свадьбах: рассмотрим некоторое конечное множество юношей, каждый из которых знаком с несколькими девушками; спрашивается,
Эту задачу можно представить графически, взяв двудольный граф с множеством вершин, разделенных на два непересекающихся подмножества , представляющих юношей и девушек, соответственно, и соединив ребром каждого юношу со знакомой ему девушкой.
Рис. 15.1.
Напомним определение двудольного графа. Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества и так, что каждое ребро в соединяет какую-нибудь вершину из с какой-либо вершиной из , тогда называем двудольным графом. Такие графы иногда обозначают , если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому в терминах раскраски его вершин двумя цветами, скажем, красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой — синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из соединена с каждой вершиной из ; если же это так и если при этом граф , простой, то он называется полным двудольным графом и обычно обозначается , где — число вершин, соответственно, в и .
Совершенным паросочетанием из в в двудольном графе называется взаимно однозначное соответствие между вершинами из и подмножеством вершин из , обладающее тем свойством, что соответствующие вершины соединены ребром. Ясно, что задачу о свадьбах можно выразить в терминах теории графов следующим образом: если — двудольный граф, то при каких условиях в существует совершенное паросочетание из в ?
Используя прежнюю «матримониальную» терминологию, можно сформулировать следующее очевидное утверждение: необходимое условие для существования решения в задаче о свадьбах в том, что любые юношей из данного множества должны быть знакомы (в совокупности ), по меньшей мере, с девушками (для всех целых , удовлетворяющих неравенствам , где через обозначено общее число юношей). Необходимость этого условия сразу вытекает из того, что если оно не верно для какого-нибудь множества юношей, то мы не сможем женить требуемым способом даже этих юношей, не говоря уже об остальных.
Паросочетания и свадьбы — Графы и архитектура
Результаты этой главы носят более комбинаторный характер, чем результаты всех предыдущих глав, хотя они тесно связаны с теорией графов. Обсудим хорошо известную «теорему о свадьбах», принадлежащую Филиппу Холлу, и некоторые приложения этой теоремы, например, построение латинских квадратов.
Теорема Холла о свадьбах
Теорема о свадьбах, доказанная Филиппом Холлом в 1935 г., отвечает на следующий вопрос, известный под названием задачи о свадьбах: рассмотрим некоторое конечное множество юношей, каждый из которых знаком с несколькими девушками; спрашивается, при каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой ему девушке? (Будем считать, что полигамия не разрешена.)
Совершенным паросочетанием из V1
Используя прежнюю «матримониальную» терминологию, можно сформулировать следующее очевидное утверждение: необходимое условие для существования решения в задаче о свадьбах в том, что любые
Поразительно, что это очевидное необходимое условие является в то же время и достаточным. В этом и состоит теорема Холла о свадьбах; ввиду ее важности мы приведем три доказательства. Первое из них принадлежит Халмошу и Вогену.
Теорема (Ф. Холл, 1935) Решение задачи о свадьбах существует тогда и только тогда, если любые к юношей из данного множества знакомы в совокупности по меньшей мере с к девушками (1 ≤ к ≤ m).
Доказательство. Как было отмечено выше, необходимость условия очевидна. Для доказательства достаточности воспользуемся индукцией и допустим, что утверждение справедливо, если число юношей меньше m. (Ясно, что при m = 1 теорема верна.) Предположим теперь, что число юношей равно m, и рассмотрим два возможных случая.
(1) Сначала будем считать, что любые к юношей (1 ≤ к ≤ m) в совокупности знакомы по меньшей мере с
к + 1девушками
(т.е. что наше условие всегда выполняется «с одной лишней девушкой»).
Тогда, если взять любого юношу и женить его на любой знакомой ему девушке, для
других m — 1 юношей останется верным первоначальное
условие. По предположению индукции мы можем женить этих m
— 1 юношей; тем самым доказательство в первом случае завершено.
(2) Предположим теперь, что имеются к юношей (к < m), которые в совокупности знакомы ровно с к девушками. По индуктивному предположению этих к юношей можно женить. Остаются еще m — к юношей, но любые h из них (1 ≤ h ≤ m-k) должны быть знакомы, по меньшей мере, с h девушками из оставшихся, поскольку в противном случае эти
Теорему Холла можно также сформулировать на языке паросочетаний в двудольном графе; число элементов множества S обозначается через |S| .
Следствие. Пусть G = G(Vi, V2) — двудольный граф, и для любого подмножества А множества Vi пусть φ(А) — множество тех вершин из V2, которые смежны, по крайней мере, с одной вершиной из А . Тогда совершенное паросочетание из Vi в V2 существует в том и только в том случае, если |А| ≤ | φ(А) | для каждого подмножества А из Vi.
Доказательство. Доказательство этого следствия является просто переводом изложенного выше доказательства на языке теории графов.3.09.2. Теорема Холла о свадьбах
Пусть А – подмножество множества вершин V(G) графа G. Множество всех вершин графа G, каждая из которых смежна с некоторой вершиной из А, называется Окружением множества А и обозначается NA.
Теорема. В двудольном графе G с долями V и U существует совершенное паросочетаиие V на U тогда и только тогда, когда для любого АV мощность |NA| ≥ .
Доказательство. Действительно, если для какого-то АV условие |NA| ≥ не выполняется, т. е. (пользуясь терминологией задачи о свадьбах) rкакое-то множество юношей (предположим K человек) знакомы в совокупности меньше, чем с K девушками, то уже этих K юношей нельзя всех женить, тем более — всех юношей множества V. Таким образом необходимость данного условия очевидна.
Докажем достаточность. Пусть АV условие |NA| ≥ выполняется.
Возможны два случая.
а) Любые K юношей знакомы в совокупности не менее, чем с K+1 девушкой. Тогда, рассуждая по индукции по числу юношей (база индукции очевидно имеется) женим произвольного юношу на знакомой ему девушке. Для остальных юношей, количество знакомых девушек уменьшается не более, чем на 1. Значит, для любого числа K любые K юношей будут знакомы не менее, чем с K девушками. По индукционному предположению их можно женить.
б) Существует K юношей, у которых ровно K знакомых девушек (K < N = |A|). По предположению индукции их можно женить. Остается N-k юношей. Для них по-прежнему будет выполняться условие, что любые L из них знакомы не менее, чем с L девушками. Действительно, если бы это было не так, то соответствующие L Юношей вместе с предыдущими K имели бы в совокупности не менее L+K знакомых девушек, что противоречит условию теоремы. Значит, и оставшихся N-k юношей можно женить по индукционному предположению.
| < Предыдущая | Следующая > |
|---|
Математическая школа для участников Заключительного этапа XII олимпиады имени Леонарда Эйлера: Новости
Положение о Летней математической школе для участников заключительного этапа
XII Олимпиады имени Леонарда Эйлера
1. Общие положения
Настоящее Положение определяет порядок организации и проведения Летней математической школы для участников заключительного этапа XII Олимпиады имени Леонарда Эйлера Образовательного центра «Сириус» (далее – образовательная программа), ее методическое и финансовое обеспечение.
1.1. Образовательная программа проводится в Образовательном центре «Сириус» (Образовательный Фонд «Талант и Успех) с 1 по 19 июля 2020 года.
1.2. Для участия в образовательной программе приглашаются школьники 8-х классов (по состоянию на май 2020 года) из образовательных организаций всех субъектов Российской Федерации, кроме г. Москвы. К участию в виде исключения могут быть допущены учащиеся 6-7 классов (по состоянию на май 2020 года).
1.3. Общее количество участников образовательной программы — до 80 человек.
1.4. К участию в образовательной программе могут быть допущены только граждане Российской Федерации.
1.5. Персональный состав участников образовательной программы утверждается Экспертным советом Образовательного Фонда «Талант и успех» по направлению «Наука».
1.6. В связи с целостностью и содержательной логикой образовательной программы, интенсивным режимом занятий и объемом академической нагрузки, рассчитанной на весь период пребывания обучающихся в Образовательном центре «Сириус», не допускается участие школьников в отдельных мероприятиях или части образовательной программы: исключены заезды и выезды школьников вне сроков, установленных Положением о программе.
1.7. В случае нарушений правил пребывания в Образовательном центре «Сириус» или требований настоящего Положения решением Координационного совета участник образовательной программы может быть отчислен с образовательной программы.
1.8. В течение учебного года (с июля 2019 по июнь 2020) допускается участие школьников не более чем в двух образовательных программах по направлению «Наука» (по любым профилям, включая проектные образовательные программы), не идущих подряд. Программа относится к 2019/20 учебному году.
2. Цели и задачи образовательной программы
2.1. Образовательная программа ориентирована на развитие и сопровождение математически одаренных школьников, повышение образовательного уровня участников образовательной программы, формирование навыков математического исследования, подготовку к участию в олимпиадах по математике всероссийского и международного уровней.
2.2. Задачи образовательной программы:
— развитие математических способностей учащихся и расширение их математического кругозора путём интенсивных занятий по углублённой программе с ведущими педагогами России;
— развитие у школьников свойственного математике стиля мышления;
— повышение общей и математической культуры у участников образовательной программы, воспитание научной честности и умения вести научную дискуссию;
— формирование навыков математического исследования;
— популяризация математики как науки.
3. Порядок отбора участников образовательной программы
3.1. Отбор участников образовательной программы осуществляется на основании требований, изложенных в настоящем Положении, а также в соответствии с общим порядком отбора на программы по направлению «Наука». Отбор участников осуществляет Координационный совет, формируемый Экспертным советом Фонда «Талант и успех» по направлению «Наука».
3.2. К участию в образовательной программе приглашаются:
— участники заключительного этапа XII Олимпиады имени Леонарда Эйлера (далее – Олимпиада), набравшие не менее 19 баллов, за исключением обучающихся в школах города Москвы и Санкт-Петербурга;
— обладатели дипломов I-III степени заключительного этапа XII Олимпиады имени Леонарда Эйлера, обучающиеся в школах города Санкт-Петербурга.
3.3. Отбор участников образовательной программы осуществляется на основании рейтинга участников заключительного этапа Олимпиады.
3.3.1. Учащиеся, отказавшиеся от участия в образовательной программе, могут быть заменены на следующих за ними по рейтингу школьников.
3.4. Для участия в конкурсном отборе школьникам необходимо подать заявку по ссылке, направленной представителем Образовательного центра «Сириус». Письмо со ссылкой направляется до 29 мая 2020 года. Регистрация будет доступна до 03 июня 2020 года.
3.5. Список участников образовательной программы будет опубликован на официальном сайте Образовательного центра «Сириус» не позднее 05 июня 2020 года.
4. Аннотация образовательной программы
Образовательная программа включает интенсивные аудиторные занятия, самостоятельную внеаудиторную работу, индивидуальные отчёты о решениях задач, а также интеллектуальные соревнования, спортивную, досуговую и экскурсионную программы с посещением олимпийских объектов и достопримечательностей г. Сочи.
5. Финансирование образовательной программы
Оплата проезда, пребывания и питания школьников – участников образовательной программы — осуществляется за счет средств Образовательного Фонда «Талант и успех».
set-theory — Теорема Холла vs Аксиома выбора?
Я оставлю (1) и (3) для Асафа, который, несомненно, скоро будет.
(2) Предположим, что $ S = \ big \ {\ {0,1 \}, \ {1,2 \} \ big \} $; то функция $ f: T_0 = \ {0,1 \} \ to S $, определяемая $ f (0) = \ {0,1 \}, f (1) = \ {1,2 \} $ является трансверсально для $ S $. {- 1} \ big (\ {1, 2 \} \ большой) = 1 \ в \ {1,2 \} $.
Но каждая из этих обратных функций делает больше, чем выбор одного представителя из каждого из множеств в $ S $: они выбирают представителей разных из разных наборов. Функция $ c: S \ to \ {0,1,2 \} $, определяемая $ c \ big \ {0,1 \} \ big) = c \ big \ {1,2 \} \ big) = 1 $ — функция выбора для $ S $, но она не выбирает отдельный представитель из множеств $ \ {0,1 \} $ и $ \ {1,2 \} $; скорее, он выбирает тот же объект, $ 1 $, как представитель для каждого из множеств.
(4) Различия между трансверсальностью и функцией выбора проиллюстрированы приведенным выше примером. Первое различие чисто формально: функция выбора для семейства $ \ mathscr {S} $ непустых множеств является функцией $ c $ от $ \ mathscr {S} $ до $ \ bigcup \ mathscr {S} $ такой что $ c (S) \ in S $ для каждого $ S \ in \ mathscr {S} $, тогда как трансверсаль (как определено в статье Википедии) является функцией $ f $ из подмножества $ T $ $ \ bigcup \ mathscr {S} $ to $ \ mathscr {S} $, что $ t \ in f (t) $ для каждого $ t \ в T $. То есть функции идут в противоположных направлениях. Важное отличие состоит в том, что функция выбора может выделять один и тот же объект из множества разных наборов, в то время как трансверсаль должен выбирать разные элементы из разных множеств.
4.1 Наличие СПЗ
В этом разделе sdr означает полный sdr . Несложно заметить, что не в каждой коллекции наборов есть sdr . Для пример, $$ A_1 = \ {a, b \}, A_2 = \ {a, b \}, A_3 = \ {a, b \}. $$ Проблема ясна: есть только два возможных представителя, поэтому набор из трех различных представителей не может быть найден. Этот пример является немного более общим, чем может показаться на первый взгляд. Рассмотреть возможность $$ A_1 = \ {a, b \}, A_2 = \ {a, b \}, A_3 = \ {a, b \}, A_4 = \ {b, c, d, e \}.k A_ {i_j} | \ ge k $. То есть количество возможных представители в любой коллекции наборов должны быть не меньше, чем количество комплектов. Оба примера не обладают этим свойством потому что $ | A_1 \ чашка A_2 \ чашка A_3 | = 2
Примечательно, что это условие необходимо и достаточно. k A_ {i_j} | \ ge k $.
Доказательство. Мы уже знаем, что условие необходимо, поэтому доказываем достаточность с помощью индукция по $ n $.
Предположим, что $ n = 1 $; условие состоит в том, что $ | A_1 | \ ge 1 $. Если это true, то $ A_1 $ непусто, поэтому sdr . Этот устанавливает базовый вариант.
Теперь предположим, что теорема верна для набора $ ksdr.
Предположим сначала, что для каждого $ ksdr $ \ {x_1, x_2, \ ldots, x_ {n-1} \} $ и для каждые $ isdr для $ A_1, A_2, \ ldots, A_n $.k A_ {j} $ для $ i> k $. Предположим, что $ \ {x_ {k + 1}, \ ldots, x_ {n} \} $ — это an sdr для $ B_ {k + 1}, \ ldots, B_ {n} $; то это тоже sdr для $ A_ {k + 1}, \ ldots, A_ {n} $. Кроме того, $ \ {x_1, \ ldots, x_n \} $ — это sdr для $ A_ {1}, \ ldots, A_ {n} $. Таким образом, для завершения доказательства достаточно показать что $ B_ {k + 1}, \ ldots, B_ {n} $ имеет SDR . Количество комплектов здесь $ н-к
Итак, рассмотрим некоторые наборы $ B_ {i_1}, B_ {i_2},…, B_ {i_l} $. Сначала мы замечаем что $$ | A_1 \ чашка A_2 \ чашка \ cdots \ чашка A_k \ чашка B_ {i_1} \ чашка B_ {i_2} \ чашка \ cdots B_ {i_l} | = k + | B_ {i_1} \ чашка B_ {i_2} \ чашка \ cdots B_ {i_l} |.$$ Также $$ | A_1 \ чашка A_2 \ чашка \ cdots \ чашка A_k \ чашка B_ {i_1} \ чашка B_ {i_2} \ чашка \ cdots B_ {i_l} | = | A_1 \ чашка A_2 \ чашка \ cdots \ чашка A_k \ чашка A_ {i_1} \ чашка A_ {i_2} \ cup \ cdots A_ {i_l} | $$ а также $$ | A_1 \ чашка A_2 \ чашка \ cdots \ чашка A_k \ чашка A_ {i_1} \ чашка A_ {i_2} \ чашка \ cdots A_ {i_l} | \ ge k + l. $$ Объединение всего этого дает $$ \ eqalign { k + | B_ {i_1} \ чашка B_ {i_2} \ cup \ cdots \ cup B_ {i_l} | & \ ge k + l \ cr | B_ {i_1} \ чашка B_ {i_2} \ чашка \ cdots \ чашка B_ {i_l} | & \ ge l \ cr. } $$ Таким образом, $ B_ {k + 1}, \ ldots, B_ {n} $ имеет sdr , что завершает доказательство. $ \ qed $
Упражнения 4.1
Пример 4.1.1 Сколько разных систем разных есть представители для $ A_1 = \ {1,2 \} $, $ A_2 = \ {2,3 \} $, …, $ A_n = \ {n, 1 \} $?
Пример 4.1.2 Сколько разных систем разных представители есть для наборы $ A_i = [n] \ backslash {i} $, $ i = 1,2, \ ldots, n $, $ n \ ge2 $?
Пример 4.1.3 Предположим, что заданная система $ A_1, A_2, \ ldots, A_n $ имеет sdr , и что $ x \ in A_i $. Покажите, что в системе набора есть SDR , содержащий $ x $.k A_ {i_j} | \ ge k + 1 $ для каждого $ 1 \ le ksdr, в котором $ x $ представляет $ A_i $.
Пример 4.1.5 Шахматная доска размером $ m \ times n $, с четными $ m $ и одновременно $ m $ и $ n $ не менее 2, удалили один белый и один черный квадраты. Покажи то доска может быть покрыта домино.
Теорема Холла — Дискретные мысли
В 1935 году математик Филип Холл открыл критерий идеального соответствия на двудольном графе, известный как теорема Холла, также известная как теорема о браке.
Рассмотрим два набора вершин, обозначенных как A = \ {a_1, \ cdots, a_m \} и B = \ {b_1, \ cdots, b_n \}.Ребра соединены между a_i и b_j для некоторых пар (i, j). Здесь мы допускаем несколько ребер между двумя вершинами. Этот граф, названный G, называется двудольным графом. Двудольный граф можно рассматривать как модель брачной системы. Взятые наборы A и B как мальчики и девочки, грань между мальчиком и девочкой говорит о том, что они могут быть парой. Возникает естественный вопрос: существует ли идеальное соответствие, то есть каждый мальчик может найти свою девочку, не вступая в конфликт с другими мальчиками. Формально, совершенное паросочетание — это инъективное отображение из A в B, которое индуцирует подграф G.
Теорема Холла утверждает, что в вышеприведенном двудольном графе G существует идеальное паросочетание, если и в том случае, если для каждого подмножества S из A кардинальное число S (количество членов в наборе) не превышает количества соседей S . Здесь соседями S являются все вершины в B, которые связаны с одной вершиной в S.
Необходимое условие, по-видимому, выполнено. С другой стороны, доказательство достаточной части немного сложно. Испытайте себя с этой проблемой.
Теперь мы представляем несколько приложений теоремы Холла.
- Пусть A = (a_ {ij}) будет матрицей порядка n с неотрицательными целыми числами в качестве элементов, так что каждая строка и столбец A имеет сумму l. Тогда A — это сумма l матриц перестановок.
- Предположим, что все вершины ориентированного графа G имеют одинаковые входные и исходящие степени l, фиксированного положительного целого числа. Таким образом, граф можно разделить на l групп окружностей. Каждая вершина появляется ровно один раз в каждой группе, и каждое ребро появляется только в одном круге.
- (Теорема Биркгофа-фон Неймана) Двойная стохастическая матрица — это квадратная матрица неотрицательных действительных чисел, сумма каждой строки и столбца которой равна 1. Утверждение: каждая дважды стохастическая матрица представляет собой просто выпуклую комбинацию матриц перестановок.
Первые два вопроса эквивалентны друг другу, если вы заметили связь между графом и смежной матрицей. Кроме того, в первой задаче мы строим двудольный граф G, состоящий из 2n вершин, u_1, \ cdots, u_n и v_1, \ cdots, v_n и a_ {ij} ребер между каждой парой вершин u_i и v_j.Несложно проверить, что этот граф удовлетворяет условию, требуемому теоремой Холла, с помощью противоречивых аргументов. Таким образом, мы получаем идеальное соответствие в этом графике, который, наоборот, представляет собой матрицу перестановок. После исключения идеального совпадения на этом графике, мы подошли к ситуации l-1 в градусах и выходах. Это позволяет использовать математическую индукцию по параметру l.
Если все элементы матрицы рациональны в третьей задаче, результат сводится к первой задаче.\ infty, можно потребовать, чтобы все эти подпоследовательности сходились по одним и тем же индексам, и они сходились к пределу c_k. В конце концов, исходная матрица (a_ {ij}) может быть выражена как выпуклая комбинация матриц перестановок с коэффициентами c_k.
Комбинаторика локального поиска: оптимальная 4-локальная теорема Холла для плоских графов
Antunes, Daniel ; Матье, Клэр ; Мустафа, Набиль Х.Комбинаторика локального поиска: оптимальная 4-локальная теорема Холла для плоских графов
Абстрактные
Локальный поиск задач комбинаторной оптимизации становится доминирующей алгоритмической парадигмой, и несколько статей используют его для решения давних открытых проблем.В этой статье мы доказываем следующую «4-локальную» версию теоремы Холла для плоских графов: задан двудольный планарный граф G = (B, R, E) такой, что | N (B ‘) | > = | B ‘| для всех | B ‘| <= 4, в G существует паросочетание размером не менее | B | / 4; кроме того, эта граница жесткая. Этот вариант теоремы Холла, помимо немедленного получения улучшенных оценок для нескольких проблем, изученных в предыдущих статьях, представляет самостоятельный интерес в теории графов.BibTeX — Запись
@InProceedings {antunes_et_al: LIPIcs: 2017: 7829,
author = {Даниэль Антунес, Клэр Матье и Набиль Х.Мустафа},
title = {{Комбинаторика локального поиска: оптимальная 4-локальная теорема Холла для плоских графов}},
booktitle = {25-й ежегодный европейский симпозиум по алгоритмам (ESA 2017)},
pages = {8: 1–8: 13},
series = {Международные слушания по информатике им. Лейбница (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
год = {2017},
объем = {87},
editor = {Кирк Прухс и Кристиан Солер},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
адрес = {Дагштуль, Германия},
URL = {http: // drop.dagstuhl.de/opus/volltexte/2017/7829},
URN = {urn: nbn: de: 0030-drops-78293},
doi = {10.4230 / LIPIcs.ESA.2017.8},
annote = {Ключевые слова: плоские графы, локальный поиск, теорема Холла, комбинаторная оптимизация, расширение}
}
| Ключевые слова: | Плоские графы, Локальный поиск, Теорема Холла, Комбинаторная оптимизация, Расширение | |
| Семинар: | 25-й ежегодный европейский симпозиум по алгоритмам (ESA 2017) | |
| Дата выдачи: | 2017 | |
| Дата публикации: | 01.09.2017 | 01.09.2017
Fel med trasig länk
SF2740HT191
Hoppa över till innehåll ÖversiktЛогга в
Översikt
Каландр
Инкорг
Historik
Hjälp
- Min översikt
- SF2740HT191
- Startsida
- Uppgifter
- Sidor
- Filer
- Kursöversikt
- Moduler
- Samarbeten
- Запись видео
- Галерея мультимедиа
