пу, в которой всегда окажется либо четверо людей знакомых (опять знакомых!) друг с другом, либо четверо, друг с другом не знакомых? Оказывается, во всякой группе из восемнадцати человек всегда найдутся либо четверо знакомых, либо четверо не знакомых друг с другом. Фрэнк Рамсей, молодой математик, философ и экономист, впервые доказавший это утверждение в 1928 году, вырос в Кембридже (Англия). Задача о знакомствах положила начало новому направлению в теории графов и комбинаторике – теории Рамсея, который доказал, что полная неупорядоченность невозможна.
Каждое достаточно большое множество (в том числе случайно сформированное) чисел, точек или других объектов обязательно содержит высокоупорядоченную структуру. Одна из базовых задач теории Рамсея – определение наименьшего значения числа объектов R ( n ), из которых можно выбрать либо n , попарно не связанных («незнакомых»), либо n , попарно связанных («знакомых»).
Как указано выше, было установлено, что R (4) = 18, но дальнейшие точные значения пока не известны. Рассмотрим более простые примеры (рис. 5.4). Очевидно, что среди трёх человек всегда найдутся двое одного пола (имеется всего два пола!). Среди трёх человек всегда есть пара одного пола (хотя бы пара). Два мужчины и одна женщина, например.
Теорема Холла. Олимпиадная математика. Be Student School
Или две женщины и один мужчина. Три мужчины. Три женщины. 74
Обозначим красным цветом инверсное отношение (рис. 5.5). Всегда найдётся либо чёрная (отношение «быть одного пола» – «однополость»), либо красная («разнополость») линия! Рассмотрим отношение знакомства в группе из шести человек. Например (рис.
5.6).
| Рис. 5.5. Отношение «быть | Рис. 5.6. Вариант отношения |
| разного пола» | знакомства в группе из шести человек |
Рис. 5.7. Вариант отношения знакомства в группе из пяти человек Можно убедиться, что при любых вариантах всегда обязательно найдётся либо красный (три незнакомых), либо чёрный (три знакомых) треугольник! А вот если пять человек – это свойство не выполняется. Например, может сложиться следующая ситуация (рис. 5.7).
Здесь нет ни красного, ни чёрного треугольника. Поэтому шес- тёрка является экстремальной (в данном случае наименьшей) характеристикой, при которой выполняется требуемое свойство – три человека либо знакомы, либо не знакомы. 75
6. СЕТЬ ПЕТРИ Карл Адам Петри немецкий математик и исследователь в области информатики.
Карл Адам Петри (нем.
Carl Adam Petri ; 1926–2010)
Сети Петри – математический аппарат для моделирования динамических дискретных систем, параллельных процессов. Впервые были описаны Карлом Петри в 1962 году. Сеть Петри (Petri net) представляет собой двудольный ориентированный граф, состоящий из вершин двух типов – позиций P и переходов T , соединённых между собой дугами, вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (фишки, маркеры, tokens), способные перемещаться по сети.
4 Система различных представителей, или теорема Холла о свадьбе
Рис. 6.1. Пример сети Петри Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. Временная сеть Петри – переходы обладают весом, определяющим продолжительность срабатывания (задержку). Стохастическая сеть Петри – задержки являются случайными величинами.
Функциональная сеть Петри – задержки определяются как функции некоторых аргументов, например, количества меток в ка- ких-либо позициях, состояния некоторых переходов. 76
Цветная сеть Петри – метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях. Ингибиторная сеть Петри – возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка.
Основными свойствами сети Петри являются : – ограниченность – число меток в любой позиции сети не может превысить некоторого значения K ; – безопасность – частный случай ограниченности, K = 1; – сохраняемость – постоянство загрузки ресурсов, зависящее от числа маркеров в i -й позиции и некоторого весового коэффициента; – достижимость – возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое; – живость – возможность срабатывания любого перехода при функционировании моделируемого объекта. В основе исследования перечисленных свойств лежит анализ достижимости.
6.1. Пример сети Петри Рассмотрим пример некоторой сети Петри (рис. 6.2). Рис. 6.2. Некоторая сеть Петри 77
Поместим в позицию р1 метку 1 (фишку) (рис. 6.3).
| а | б |
Рис. 6.3. Некоторая сеть Петри с активизированной позицией р1 ( а ) и таблица состояний рi ( б ) Теперь активизированы переходы t1 и t2. Если быстрее срабатывает t1, то фишка забирается из р1 и передается в р2 (рис. 6.4).
| а | б |
в Рис. 6.4. Активирование перехода t1 ( а ), занесение фишки в позицию р2 ( б ), таблица состояний рi ( в ) 78
Получаем маркировку 010, возбужден только переход t3; после его срабатывания сеть возвращается к начальной маркировке 100 (рис. 6.5).
| а | б |
в Рис. 6.5. Активирование перехода t3 ( а ), возвращение фишки в позицию р1 ( б ), таблица состояний рi ( в ) Если же быстрее срабатывает переход t2, то фишки появляются в р2 и р3. Получаем маркировку 011, при которой возбуждены переходы t3 и t4, каждый из которых может сработать (рис. 6.6).
79
| а | б |
в Рис. 6.6. Срабатывание перехода t2 ( а ), занесение фишек в позиции р2, р3 ( б ), таблица состояний рi ( в ) Если срабатывает t4, то сеть возвращается к начальной маркировке: обе фишки изымаются из р2, р3 и в р1 опять оказывается «1» (рис. 6.7).
| а | б |
Рис. 6.7. Срабатывание перехода t4 ( а ), изъятие фишек из р2, р3 и возвращение фишки в позицию р1 ( б ), таблица состояний рi ( в ) (см. также с. 81) 80
Источник: studfile.net
Теорема о свадьбах
Теорема о свадьбах (также теорема о мальчиках и девочках или теорема Холла), утверждает, что если в двудольном графе для любого положительного целого 
любые элементов одной из долей связаны по крайней мере с элементами другой, то граф разбивается на пары.
Названа в честь английского математика Филипа Холла (англ.), доказавшего её в 1935 году.
Теорема обобщается на граф, имеющий произвольное (не обязательно конечное или счётное) множество долей.
Доказательство при помощи теоремы Форда — Фалкерсона
Пусть мощность первой доли — 
. Сделаем из данного графа сеть. Для этого на каждом ребре введем пропускную способность по 1 в направлении от вершины первой доли к вершине второй.
При этом создадим две дополнительные вершины — 
и 
, от первой проведем все стрелки в вершины первой доли, а из каждой вершины второй проведем стрелки во вторую добавленную вершину. Заметим, что получившаяся сеть — целочисленная, то есть в ней существует максимальный целочисленный поток, и что если мы сможем доказать, что пропускная способность минимального разреза равна , то по теореме Форда-Фалкерсона величина максимального потока равна пропускной способности минимального разреза, то есть тоже равна . Очевидно, что если в бинарной транспортной сети величина максимального потока равна , то существует непересекающихся по вершинам путей из истока в сток. Это следует из алгоритма для нахождения максимального целочисленного потока в целочисленном графе, а из каждого такого пути можно выбрать смежную пару вершин из разных долей исходного графа.
То, что мощность минимального разреза не превышает , очевидно — достаточно рассмотреть разрез, в котором множество 
содержит одну вершину .
Теперь рассмотрим произвольный разрез 
. Пусть в попали ровно 
вершин из первой доли и 
из второй.
- Пусть
. Тогда пропускная способность разреза складывается из 
рёбер, ведущих из в вершины первой доли, лежащие в 
и рёбер, ведущих из вершин второй доли, лежащих в , в . Суммируя, получаем: 
. - Иначе,
. По условию теоремы, эти 
вершин связаны с вершинами второй доли, а так как , то они связаны хотя бы с 
вершинами во второй доле, попавшими во множество . Тогда пропускная способность разреза рассчитывается так же, как в предыдущем пункте, плюс рёбер из вершин первой доли, принадлежащих в вершины второй доли, принадлежащими . Итого, 
.
В обоих случаях величина максимального потока равна , что и требовалось доказать.
Ссылки
- Н. Костюкова, Курс «Графы и их применение», Лекция 15: Паросочетания и свадьбы: «Теорема Холла о свадьбах» // Интуит.ру, 25.07.2006
| Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
- Незавершённые статьи по математике
- Теоремы теории графов
Источник: www.wikiznanie.ru
Первый взгляд на лемму Холла
В школьных околоолимпиадных кругах пользуется популярностью следующее утверждение, носящее название леммы Холла о свадьбах.
Теорема [Hall’s marriage lemma, 1935]. Пусть есть (n) мальчиков и сколько-то девочек. Некоторые мальчики знакомы с некоторыми девочками (знакомства взаимны). Тогда для того, чтобы всех мальчиков можно было посватать за знакомых им девочек (разумеется, нельзя приписывать одну девочку нескольким мальчикам), необходимо и достаточно выполнение следующего условия: для любого (1 le k le n) любые (k) мальчиков должны совокупно быть знакомы не менее, чем с (k) девочками, т.е. если объединить множества их знакомых девочек, их должно выйти не меньше (k).
Доказательство. Необходимость очевидна: если удалось посватать мальчиков и девочек, то для любых (k) мальчиков множество их знакомых девочек состоит по крайней мере из тех (k) девочек, за кого они посватаны. Докажем достаточность (именно это есть содержательная часть теоремы, которой все пользуются). Индукция по (n). База очевидна. Для того, чтобы провести рассуждение с переходом индукции, рассмотрим два случая.
- Для любого (k) любая группа из (k) мальчиков знает совокупно строго более (k) девочек. Тогда назначим первому мальчику невесту произвольным образом, выбросим эту пару из рассмотрения, а к остальным применим предположение индукции. Легко видеть, что из-за того, что мы выбросили лишь одну девочку, то выполнено условие «для любого (1 le k le n-1) любые (k) мальчиков совокупно знакомы не менее, чем с (k) девочками», поэтому по предположению индукции можно образовать (n-1) пар. В этом случае всё ясно.
- Для некоторого (k) существует группа из (k) мальчиков, которая знает совокупно ровно (k) девочек. Легко проверить (проверьте!) что к этой группе мальчиков и знакомых им девочек можно применить предположение индукции, и построить на них (k) пар. Ничуть не сложнее проверить (проверьте!), что для всех остальных мальчиков и девочек также применимо предположение индукции, и на них можно образовать (n-k) пар. Так что и в этом случае всё хорошо.
Теорема доказана. (square)
—1.2—
Эквивалентно лемму Холла можно переформулировать в терминах паросочетаний в двудольных графах. Двудольным называется граф, вершины которого можно разбить на две доли (L) и (R) так, что любое ребро будет идти между долями, а внутри каждой доли рёбер не будет. Паросочетанием в двудольном графе называется подмножество рёбер, никакие два из которых не имеют общего конца. Совершенным паросочетанием в двудольном графе с размерами долей (|L| le |R|) называется паросочетание, состоящее из (|L|) рёбер (максимальное потенциально возможное).
Теорема [Hall’s lemma revisited]. Для существования совершенного паросочетания в двудольном графе с долями (L) и (R) необходимо и достаточно выполнение следующего свойства: для любого (1 le k le |L|) любые (k) вершин доли (L) должны быть совокупно смежны не менее чем с (k) вершинами доли (R), т.е. если объединить множества с ними смежных вершин, то должно получиться не менее (k) штук.
Доказательство. Воспринимаем вершины доли (L) как мальчиков, вершины доли (R) как девочек, рёбра как знакомства и применяем предыдущую формулировку. (square)
На ФУПМе обычно формулируют лемму Холла немножко иначе, в терминах множеств и представителей. Пусть “мальчики” – это подмножества (S_1, ldots, S_n) некоторого конечного базового множества (S = < x_1, ldots, x_m >). Пусть “девочки” – это элементы (x_1, ldots, x_m) множества (S). Давайте говорить, что мальчик (S_i) знаком с девочкой (x_j), если (x_j in S_i).
В таких терминах получаем ещё одну эквивалентную переформулировку. Будем говорить, что некоторые (n) элементов множества (S) образуют систему различных представителей для подмножеств (S_1, ldots, S_n), если можно их занумеровать (z_1, ldots, z_n) так, чтобы (z_i in S_i).
Теорема [Hall’s lemma one more time]. Для существования системы различных представителей для подмножеств (S_1, ldots, S_n) множества (S) необходимо и достаточно выполнение следующего свойства: для любого (1 le k le n) любые (k) множеств (S_, ldots, S_) имеют в объединении не менее (k) элементов.
Доказательство следует из вышесказанного. (square)
—1.3—
В качестве простейшего примера применения леммы Холла приведу решение задачи 4.23 из книжки Флёрова из главы о комбинаторике.
Пусть (S_1, ldots, S_n) – подмножества (m)-элементного множества (S = ). Для этой системы строится матрица инциденций (A) размера (ntimes m): [ a_ = begin 1, quad text end ] Пусть оказалось, что в каждой строке матрицы (A) ровно (r) единиц, и в каждом столбце ровно (r) единиц. (Отсюда, кстати, тривиально следует (n=m).) Доказать, что в этой конфигурации существует система различных представителей.
Рассмотрим пример чуть посложнее. Лемму Холла можно применить для доказательства верхней оценки числа монотонных функций алгебры логики.
Естественным образом эти функции определяются на булевом кубе (^n), на котором также вводится отношение порядка: говорят, что набор (alpha = (alpha_1, ldots, alpha_n) in ^n) не превосходит набор (beta = (beta_1, ldots, beta_n)in ^n) (пишем (alpha le beta)), если поразрядно выполнено (alpha_i le beta_i). Цепью в булевом кубе тогда будет называться последовательность элементов булева куба, упорядоченная в линейную цепочку в соответствии с введённым отношением порядка. Функция (f : ^n to \) называется монотонной, если (f(alpha) le f(beta)) для любых (alpha le beta). Пусть (mathcal^) – множество монотонных функций алгебры логики от (n) переменных. Докажем следующую верхнюю оценку.
Доказательство. Двойка в правой части – это функции-константы 0 и 1. Оценка числа неконстантных монотонных функций проводится следующим образом. С помощью леммы Холла ниже мы докажем, что булев куб (^n) можно разбить на () цепей. Каждая цепь, как легко видеть, будет состоять не более, чем из (n+1) вершин.
Если мы посмотрим на значения монотонной функции на вершинах цепи (в порядке обхода цепи, задаваемом отношением (le)), то сразу же поймём, что они представляют собой подряд идущие нули, в какой-то момент сменяемые подряд идущими единицами. Задать монотонную функцию на одной из цепей – это то же, что задать “момент переключения” с нулей на единицы.
Мы рассматриваем неконстантные функции (f), поэтому можно считать, что (f(0, ldots, 0) = 0), (f(1, ldots, 1) = 1). Поэтому момент переключения для произвольной цепи может быть выбран как максимум (n) способами. Для того, чтобы задать монотонную функцию на булевом кубе, необходимо корректно задать монотонную функцию на наборе из () цепей, на которые куб разбит. Это можно сделать не более, чем (n^) способами. Не любое задание функции на цепях породит монотонную функцию на всём кубе, так как цепи каким-то сложным образом согласованы, но нам это и не важно – мы строим грубую оценку сверху.
Осталось уточнить вопрос, как разбить булев куб на () цепей. Для этого вспомним слоёную структуру куба: все вершины, имеющие ровно (i) единиц в координатах, образуют слой (L_i) булева куба. Очевидно, что весь куб разбивается на непересекающееся объединение слоёв (L_0, L_1, ldots, L_n), и что ( | L_i | = ). Теперь мы можем забыть про ориентацию отношений между вершинами.
Отныне булев куб – неориентированный граф, где две вершины соединены рёбрами, если они сравнимы в смысле отношения (le). Наша локальная задача – для любой пары соседних слоёв (L_i, L_) построить паросочетание, по мощности равное (min<|L_i|, |L_|>), т.е. максимальное потенциально возможное. Если нам удастся это осуществить по всем (i), то рёбра паросочетаний автоматически образуют нужное нам количество цепей.
Итак, рассмотрим соседние слои (L_i, L_). Считаем, что (i < n/2), т.е. что (|L_i| le |L_|) (обратная ситуация может быть аналогично рассмотрена, если заменить нули на единицы и наоборот). Из каждой вершины слоя (L_i) исходит (n-i) рёбер в слой (L_), а из каждой вершины слоя (L_) исходит (i+1) рёбер в слой (L_i). Я утверждаю, что это позволяет нам гарантировать выполнение условия леммы Холла.
Аргумент по сути такой же, как и в предыдущей задаче. Действительно, рассмотрим произвольные (1 le k le ) вершин из слоя (L_i). Предположим, что они совокупно смежны с менее, чем (k) вершинами слоя (L_). Посчитаем, сколько рёбер проходит между этими подмножествами вершин. С одной стороны, если считать их по инцидентностям с вершинами слоя (L_i), то таких рёбер окажется ровно (k cdot (n-i)).
С другой стороны, если считать их по инцидентностям с вершинами слоя (L_), то таких рёбер не может быть больше, чем ((k-1)cdot (i+1)). Имеем: [ k cdot (n-i) le (k-1)cdot (i+1) < k cdot (i+1) quad Rightarrow quad n-i < i+1 quad Rightarrow quad 2i ge n, ] что противоречит нашему предположению (i < n/2). Холловское условие выполнено, максимальное паросочетание существует, рассуждение успешно завершено. (square)
Ту же самую верхнюю оценку можно получить короче, если воспользоваться чуть более тяжёлой артиллерией (теорема Шпернера + теорема Дилворта), мы обсудим это позже. Что касается нижней оценки на количество монотонных функций, самый простой аргумент может быть таким. Положим функцию (f) равной нулю на всех слоях (L_i, i < lfloor n/2 rfloor), и равной единице на всех слоях (L_j, j >lfloor n/2 rfloor). На среднем слое функция (f) может быть произвольной. Пересчитывая все такие функции, а также две константы, получаем [ |mathcal^| ge 2 + 2^. ]
Вышеприведённое доказательство верхней оценки на самом деле очень грубое; используя более тонкую технику так называемых цепей Анселя, можно доказать верхнюю оценку [ |mathcal^| le 3^. ] Существуют и более точные оценки, но их доказательств я не знаю. Окончательного и удовлетворительного ответа на вопрос “(|mathcal^| = ?)” нету.
—1.4*—
В этом параграфе для знатоков я хочу привести линейно-алгебраический аналог леммы Холла. Для его понимания нужна хорошая база линейной алгебры, но идейно его доказательство чем-то проще, чем у исходной теоремы, так как не требует ветвления. Смело пропускайте эту часть, если что-то непонятно; пользоваться этим результатом мы не будем. Задачу и доказательство я заимствовал у своего блестящего научного руководителя Романа Николаевича Карасёва. Упражнением для читателя может быть вывод обычной леммы Холла из этой версии.
Пусть в векторном пространстве (V) (над некоторым полем, необязательно (mathbb)) даны конечные множества (S_1,ldots, S_n) со следующим свойством: для любого набора индексов (1le i_1 < i_2 < dots < i_k le n) (включая наборы из одного индекса) линейная оболочка [ leftlangle S_cup S_ cup dots cup S_ rightrangle ] имеет размерность не менее (k). Докажите, что найдётся система представителей (s_iin S_i), которая является линейно независимой.
Решение. Докажем сначала, что линейно независимую систему представителей можно выбрать из пространств (V_i = langle S_i rangle). Предположим для начала, что поле коэффициентов бесконечно.
Воспользуемся индукцией. Возьмём некоторый вектор (vin V_n) и рассмотрим проекцию набора (V_1,ldots, V_) на факторпространство (V/langle v rangle). Если к проекции применимо предположение индукции и некоторый набор (v_1in V_1,ldots, v_in V_) линейно независим в этом факторпространстве, то добавив к этому набору (v), мы получаем требуемое. Иначе, для всякого (vin V_n) найдётся набор (1le i_1 < i_2 < dots < i_k le n-1) такой, что проекция суммы (V_+dots + V_) на (V/langle v rangle) имеет размерность меньше (k). Но так как до проекции размерность (V_+ldots + V_) была не менее (k), то получается что она была ровно (k), стала ровно (k-1), и (v in V_+dots + V_).
Если для некоторой суммы (V_+dots + V_) ((i_kle n-1)) размерности (k) оказалось, что [ V_nsubseteq V_+dots + V_ ] то сумма (V_+dots + V_+V_n) имеет также размерность (k), что противоречит условию. Значит, для всякой суммы (V_+dots + V_) ((i_kle n-1)) размерности (k) пересечение [ (V_+dots + V_)cap V_n ] является собственным подпространством (V_n). Таких собственных подпространств (V_n), соответствующих наборам (i_1
Теперь решим исходную задачу. Если поле конечное, то вложим его в бесконечное и умножим тензорно (V) на новое поле над старым. Теперь поле можно будет считать бесконечным. Теперь по доказанному у нас есть линейно независимые вектора [ v_i = sum_ alpha_ s. ] В линейной оболочке (W = langle v_1,ldots, v_n rangle) они составляют базис, в котором (det(v_1, ldots, v_n) = 1). Тогда используя полилинейность детерминанта и раскрывая скобки в равенстве [ detleft(sum_ alpha_ s, ldots, sum_ alpha_ sright) = 1 ] мы получим, что для некоторой системы представителей (s_iin S_i) будет [ det(s_1,ldots, s_n) neq 0, ] что и гарантирует их линейную независимость. (square)
От комбинаторики к геометрии
Источник: balit.ski