Начнем с типичной олимпиадной задачи:
На далекой планете есть 20 государств, некоторые из которых установили дипломатические отношения и обменялись посольствами. При этом среди любых трех государств некоторые два еще не установили между собой дипломатических отношений. Доказать, что на этой планете не более 200 посольств.
Вот так условие: «Друг моего друга мне не друг"! Не знаю, как вам, а мне нравится. Помню, как в юности я довольно комфортно чувствовал себя в tête-à-tête, но очень смущался, когда в нашу скромную компанию вливался кто-то третий. Как вы догадались, дело было вовсе не в секретности наших разговоров. (Скажу более, у меня никогда не было желания обсуждать с кем-либо какие-либо тайны, и ко мне относились соответственно.) Всегда получалось так, что в результате этого я оказался выброшенным на обочину беседы, так как весь интерес моего бывшего собеседника переключался на «третьего лишнего», и если я пытался вставить свою робкую фразу, она (случайно или понарошку) оставалась незамеченной. Как спокойно я бы себя чувствовал, зная, что третьего не будет, так как любой другой постесняется хотя бы одного из нас ввиду отсутствия дипломатических отношений!
«В тихом омуте черти водятся». А омут-то тихий, потому что заброшенный и покинутый теми, кто не потрудился в него заглянуть! Вот и проходилось уповать на чертей ... пока не появились блоги. Не удивлюсь, если многие из популярных блогеров в миру являются робкими необщительными людьми, а вести блог начали лишь от желания быть услышанными, совсем не рассчитывая на успех.
Как ни говорите, а все-таки хорошо, когда нет третьих лишних! Это устраняет клановость и уменьшает (если не полностью ликвидирует) возможность заговора. В таком обществе нет ни фаворитов, ни изгоев, так как все связаны одной нитью.
Решение
Будем рассматривать общий случай, обозначив количество государств через $n$... Для начала неплохо, но что делать дальше? Есть какие-то предложения? Таковых нет. Приходится искать крайнего, то есть того, кто лучше или хуже остальных. В данном случае следует присмотреться к самой дружественной стране, то есть той, где есть наибо́льшее количество посольств.
Итак, пусть $A$ — государство с наибо́льшим количеством посольств (то есть наибо́льшим количеством дипломатических отношений). Обозначим это количество через $m$. Возможно, некоторые другие государства также имеют $m$ посольств, но никакое не может иметь их больше $m$.
Пусть $M$ — множество государств, имеющих дипломатические отношения с $A$. Мы знаем, что в $M$ входит $m$ государств. При этом никакие из них не могут иметь дипломатических отношений между собой, так как если найдутся два государства $B \in M$ и $C \in M$, заключившие между собой дипотношения, то в тройке $A$, $B$, $C$ все государства обожают друг друга, что никак не допустимо.
Опять пауза! Надо использовать максимальность $m$, а это вряд ли у нас получится, если дипломатические отношения на столь низком уровне. Что же делать?..
Выход есть! Обратиться за помощью к другим государствам. Пусть $N$ — множество государств не входящих в $M$ (такое множество называется дополнительным). Множество $N$ содержит $n-m$ государств (включая, между прочим, государство $A$). Поскольку государства из $M$ чуждаются друг друга, то в каждом дипломатическом отношении участвует хотя бы одно государство из $N$. Другими словами, каждое дипломатическое отношение создает хотя бы одно посольство в $N$.
Пусть $r$ — общее количество дипломатических отношений (почему именно буква $r$ выяснится чуть позже), а $E$ — количество посольств в государствах из $N$. Тогда согласно приведенным выше рассуждениям $$ r \leslant E \qquad (1) $$
Опять эта неуловимая максимальность $m$ оказалась не у дела! Как ее использовать? Вот как! Поскольку каждое из $n-m$ государств в $N$ не может иметь более $m$ посольств, общее количество посольств в $N$ не превосходит $m(n-m)$: $$ E \leslant m(n-m) \qquad (2) $$
Сравнивая (1) и (2) получам: $$ r \leslant m(n-m) \qquad (3) $$
Неравенство (3) дает оценку сверху для количества дипломатических отношений, а следовательно для количества посольств, которых ровно в два раза больше, так как каждое дипломатическое отношение создает посольства в обоих странах. Правда, неравенство (3) содержит неизвестное значение $m$, но его можно исключить, оценив максимум $m(n-m)$. Для этого у нас есть палочка-выручалочка: неравенство между средне-арифметическом и средне-геометрическом, согласно которому $\frac{m+(n-m)}{2} \geslant \sqrt{m(n-m)}$. Отсюда $$ m(n-m) \leslant \frac{n^2}{4} \qquad (4) $$Окончательно получаем: $$ r \leslant \frac{n^2}{4} \qquad (5) $$
В частности, при $m=20$, получаем не больше $\frac{20^2}{4}=100$ дипломатических отношений, то есть не более $200$ посольств, что в точности совпадает с оценкой условия задачи.
Фактически была доказана теорема Мантеля, названная по имени голландского математика Вилема Мантела [Willem Mantel], (по непонятным причинам эту фамилию на русском языке принято писать с мягким знаком). Разумеется, настоящая теорема Мантеля ни имеет дело с государствами или дипломатическими отношениями, а относится к теории графов.
Разумеется, речь идет не о дворянском титуле, который по-немецки пишется с буквой "f": Graf. «Наш» граф (в немецком, английском и французском) пишется через "ph": graph, и происходит , от греческого «γράφω» (в латинской транслитерации grapho), что значит «писать». (Между прочим, это греческое слово внесло вклад в такие слова как «автограф», «биограф», «сейсмограф» и т.д.). В страдающем отсутствием суффиксов английском языке слово "graph" означает также «график функции».
Что такое граф понять совсем не сложно. Достаточно на листе бумаги набросать несколько точек, и соединить некоторые из них отрезками. Вот и получился граф! Точки называются вершинами графа, а отрезки ребрами графа. Количество вершин называется порядком графа, а количество ребер — мощностью графа.
Если вершина является концом ребра, то говорят, что вершина инцидентна ребру, а ребро инцидентнo вершине. Два ребра, имеющие общую вершину (говоря «по научному» инцидентные одной вершине) называются смежными. Смежными называются также две вершины, имеющее общее ребро.
В отличие от геометрии, расположение вершин и форма ребер графа не имеет значение: главное знать, сколько вершин в графе и какие из них соединены ребрами. Если два графа содержат одинаковое количество вершин, причем вершины одного графа можно поставить во взаимно-однозначное соответствие с вершинами другого графа, так что каждая пара соединенных вершин остается соединенной в другом графе и наоборот, такие графы считаются практически одинаковыми и называются изоморфными.
Графы изображенные на рисунках 1а и 1б являются изоморфными, несмотря на то, что на рис. 1а AC — отрезок, тогда как на рис. 1б AC — кривая линия. Важно лишь то, что в обоих графах вершины A и C соединены между собой. При этом не должно смущать то, что на рис. 1а линии AC и BD пересекаются. Это пересечение лишь «кажущееся», так как точка пересечения не является вершиной графа. Чтобы сделать это явным, на рис 1б) ребро AC нарисовано «в обход». В случае, когда можно избавиться от всех «неправильных» пересечений, граф называется плоским. Оба графа на рисунках 1а и 1б являются плоскими, поскольку, хотя линии AC и BD на рис 1а пересекаются, мы знаем, что это можно исправить. Примером графа, не являющегося плоским, является пятиугольник в котором проведены все диагонали. Название «плоский» связано с тем, что в графе, не являющемся плоским, от пересекающихся внутри ребер можно избавиться лишь переместив граф из плоскости в трехмерное пространство, где вершины можно подвинуть, или ребра изогнуть.
|
|
| 1а | 1б |
Некоторые публикации допускают петли, то есть ребра, соединяющие вершину с собой, или кратные ребра, то есть несколько ребер, соединяющих одну и ту же пару вершин. Поэтому сразу договоримся, что здесь мы рассматриваем только самые обыкновенные графы, без петель или кратных ребер.
Заметим, что в графах, изображенных на рис 1а и 1б каждая вершина соединена с каждой из оставшихся вершин, то есть проведены все ребра, какие только можно провести. Такой граф называется полным. Противоположностью полного графа можно считать нуль-граф в котором совершенно отсутствуют ребра.
Аналогией подмножества в теории графов является подграф. Как вы наверное догадались, подграф образуется некоторым подмножеством вершин исходного графа, соединенных некоторым подмножеством ребер исходного графа. При этом каждое ребро подграфа не только должно присутствовать в исходном графе, но также соединять вершины из подграфа, иначе один из концов ребра (или оба) «повиснет в воздухе».
Нас будет особенно интересовать максимальные подграфы образованные заданным подмножеством вершин, то есть, когда к выбранному подмножеству вершин добавляются все ребра исходного графа, соединяющие какую-либо пару выбранных вершин. Такой подграф называется порожденным заданным подмножеством вершин. Заметим, что любой порожденный подграф полного графа является полным графом.
Согласно определению, в каждом графе, не являющемся полным, существуют две вершины, не соединенные ребром. Иногда удается найти и бо́льшее количество вершин, ни одна пара из которых не соединена ребром (то есть никакие вершины не являются смежными друг другу). Такое подмножество вершин называется независимым. Как было замечено, в каждом неполном графе существует независимое подмножество вершин. Очевидно, граф, порожденный независимым множеством вершин является нуль-графом.
Степенью вершины называется количество ребер, инцидентных данной вершине (по-простому: количество ребер, выходящих из этой вершины). Степень вершины $A$ обозначается через $deg(А)$ (англ. degree). Так как каждое ребро соединяет две вершины, оно учитывается в степенях двух вершин, следовательно сумма степеней вершин равна удвоенному количеству ребер: $$ deg(A_1) + deg(A_2) +\;...\;+ deg(A_n) = 2r \qquad(6) $$ где $r$ — количество ребер, $n$ — количество вершин.
Равенство (6) называется леммой о рукопожатиях, в честь неопровержимой истины, известной задолго до появления теории графов: если некоторые члены уютной компании обменялись рукопожатиями, количество людей, пожавших нечетное количество рук, четно. (Надеюсь, читателю понятно, откуда это следует. Если нет, прочтите Чет или нечет того же автора.)
Можно заметить, что в графах на рис 1а и 1б степень каждой вершины равна 3. Это не удивительно, так как в полном графе из $n$ вершин каждая вершина обязана соединяться со каждой $n-1$ остальных вершин. В этом случае суммарная степень вершин равна $n(n-1)$ и, согласно лемме о рукопожатиях, полный $n$-вершинный граф содержит $\dfrac{n(n-1)}{2}$ ребер. Отсюда, в частности следует, что никакой граф из $n$ вершин не может иметь более $\frac{n(n-1)}{2}$ ребер
Может ли граф, не являющийся полным иметь полный подграф? Может, если, конечно, идет речь о подграфе меньшего порядка. Например если из графа на рис 1а (или 1б) удалить ребро BC, в нем останутся полные подграфы, порожденные вершинами ABD а также ACD. Полные графы из трех вершин (такие как ABD и ACD нашем примере) я буду для краткости называть треугольниками.
Здесь я прерываю свой затянувшийся экскурс в теорию графов. Очень хотелось рассказать об ориентированных графах, мостах, деревьях (нет, речь идет не о благоустройстве улицы), а также об эйлеровых и гамильтоновых циклах. В наше время достаточно назвать предмет — и за считанные минуты мой собеседник будет знать об этом больше, чем я сам, поэтому не будем забывать о цели нашего повествования.
Как применить графы к упомянутой задаче о посольствах? Понятно, что каждому государству следует поставить в соответствие вершину графа, При этом дипломатически отношения отображаются ребрами графа, которые присутствуют в том случае, если между соответствующими государствами эти отношения установлены.
Что является аналогом количества посольств? Все правильно, количество посольств — это степень соответствующей вершины, а лемма о рукопожатиях иллюстрирует хорошо известный факт, что количество посольств вдвое больше количества дипломатических отношений.
А как перевести на язык графов «друг моего друга мне не друг»? Здесь тоже довольно ясно: в графе не должно быть треугольников, на официальном языке полных 3-вершинных подграфов.
Итак, мы готовы сформулировать теорему Мантеля, как она звучит на самом деле: В $n$-вершинном графе, не содержащем полных 3-вершинных подграфов, количество ребер не превосходит $\dfrac{n^2}{4}$.
Для доказательства достаточно перевести решение задачи о посольствах на язык теории графов.
Теорема Мантеля была опубликована в журнале Wiskundige Opgaven (Математические упражнения), № 10 за 1907 год (задача 28). По-видимому, ввиду простоты доказательства, автор постеснялся его опубликовать в отдельной статье, однако публикация была замечена и породила целое направление, называемое «Экстремальной теорией графов».
Любопытная деталь теории графов состоит в том, что ее можно применить тогда, когда нет даже косвенного упоминания о графах. Вот одна из таких задач.
За круглым столом сидят $n$ участников «безумного чаепития». $(n \geslant 3)$ (по мотивам сказки «Льюиса Кэролла «Алиса в стране чудес».) Каждую минуту одна пара соседей меняется местами. Через какое наименьшее время все участники чаепития могут оказаться сидящими в противоположном порядке (так что левые соседи у всех станут правыми и наоборот)? Задачник Кванта задача М955. Журнал «Квант» №11 1985.
Есть идея, как применить теорему Мантеля? Не знаю, получится у вас читать и думать одновременно. В конце концов, можно либо отложить чтение и подумать, либо понадеяться на то, что нижеследующие рассуждения натолкнут на мысль.
Треугольники ... Они упоминаются в теореме Мантеля, но где их взять?. Постараемся вникнуть в задачу. Занумеруем всех сидящих номерами по порядку по часовой стрелке. Легко видеть, что результате всех перестановок они тоже будут сидеть по порядку, но только против часовой стрелки. Расположение как бы вывернулось наизнанку, поэтому если по-прежнему идти по часовой стрелке, порядок любых трех человек должен измениться. Это значит, что двое из них должны были обязательно пересаживаться. (Кстати, почему подобные рассуждения не работают для двух человек?)
Теперь все понятно. Сопоставим каждому «чаепьющему» вершину графа и будем соединять ребрами тех, кто не(!) пересаживался. На основании вышеприведенных рассуждений в таком графе не будет треугольников, поэтому согласно ... (угадайте чему) в нем будет не более $\frac{n^2}{4}$ ребер.
Нас однако интересуют не присутствующие, а отсутствующие ребра. Их мы оценим исходя из того, что полный граф имеет $\frac{n(n-1)}{2}$ ребер. Таким образом, если $p$ — количество пересаживаний, то $$ p \geslant \frac{n(n-1)}{2} - \frac{n^2}{4} = \frac{n(n-2)}{4} \qquad (7) $$ следовательно потребуется не менее $\frac{n(n-2)}{4}$ минут.
Есть возражения? Должны быть! Ведь в задаче требуется не просто оценить снизу, а дать точную оценку, то есть показать, что существует перестановка занимающая точно $\frac{n(n-2)}{4}$ минут, то есть состоящая из ровно $\frac{n(n-2)}{4}$ пересаживаний.
Скажу по секрету, что на самом деле оценка, даваемая (7) точна далеко не для всех значений $n$, и ее необходимо подправить. Однако для начала, проверим на точность саму теорему Мантеля.
Итак, существует $n$-вершинный граф, для которого неравенство (5) является точным? «Только не для нечетного $n$!» — возразит внимательный читатель. Действительно, при нечетном $n$, выражение $\frac{n^2}{4}$ становится дробным, между тем как количество ребер — целое число. Придется подправить и воспользоваться знаком целой части $\lfloor$…$\rfloor$ ($\lfloor a \rfloor$ — наибольшее целое число, не превосходящее $a$): $$ r_{max} = \left\lfloor\frac{n^2}{4}\right\rfloor \qquad (8) $$ где $r_{max}$ — максимальное количество ребер, возможное для графа порядка $n$ без треугольников.
До чего же неприятно иметь дело с целой частью! Давайте начнем с четного $n$ и покажем, что в этом случае неравенство (5) можно обратить в равенство. Тем самым будет доказана справедливость (8) для четного $n$.
Присмотримся к доказательству теоремы. Неравенство (5) вытекает из неравенств (1), (2) и (4), и для достижения нашей цели все они должны стать равенствами. Рассмотрим эти неравенства по-порядку.
Неравенство (1) вытекает из того, что «в каждом дипломатическом отношении участвует хотя бы одно государство из $N$», или, на языке теории графов, каждое ребро графа инцидентно хотя бы одному ребру из $N$. Для равенства требуется не «хотя бы одному ребру» а «точно одному». Другими словами, в $N$ не должно быть вершин, связанных между собой, то есть $N$ должно быть независимым подмножеством. Вспомним, что в $M$ также отсутствуют внутренние ребра. Таким образом искомый граф состоит из двух независимых множеств, так что каждое ребро соединяет вершину одного множества с вершиной другого множества. Такой граф называется двудольным, а независимые множества, из которых он состоит называются долями.
Обратимся к неравенству (2). Оно основано на том, что степень каждой вершины из $N$ не превышает $m$. Для получения равенства необходимо, чтобы степень каждой вершины была равна $m$, то есть каждая вершина из $N$ должна быть соединена с каждой вершина из $M$. Двудольный граф, в котором каждая вершина одной доли соединена с каждой вершиной другой доли называется полным двудольным графом. Именно такой граф нам нужен.
Наконец, когда неравенство (4) становится равенством? Ответ простой: средне-арифметическое равно средне-геометрическому тогда и только тогда, когда числа равны. В данном случае это означает равенство $n$ и $m-n$, то есть обе доли должны состоять из равного количества вершин.
Итак, для четного $n$ все прояснилось: максимум вершин дает полный двудольный граф, по $\frac{n}{2}$ вершин в каждой доле. Так как каждая из $\frac{n}{2}$ вершин одной доли соединена с каждой из $\frac{n}{2}$ вершин другой доли, получаем всего $\left(\frac{n}{2}\right)^2$ или $\frac{n^2}{4}$ ребер — точно по ответу!
Обратимся к случаю нечетного $n$. Если $n=2k+1$, то $\dfrac{n^2}{4}=k(k+1)+\dfrac{1}{4}$, так что дробная часть от $\dfrac{n^2}{4}$ равна $\dfrac{1}{4}$, следовательно $\left\lfloor\dfrac{n^2}{4}\right\rfloor=\dfrac{n^2-1}{4}$.
Таким образом равенство (8) можно переписать в виде: $$ r_{max} = \begin{cases} \dfrac{n^2}{4}, & \text{ если } n \text{ четно} \\ \dfrac{n^2-1}{4}, & \text{ если } n \text{ нечетно} \end{cases} \qquad (9) $$
Теперь стало понятным, как получить требуемый граф при нечетном $n$. На этот раз доли должны содержать почти равное количество вершин, в одной доле должно быть $\dfrac{n-1}{2}$ вершин, а в другой $\dfrac{n+1}{2}$ вершин, то есть одной вершиной больше. Соединив каждое ребро 1-й доли с каждым ребром 2-й доли получаем как раз $\dfrac{n^2-1}{4}$ вершин. Таким образом равенства (8) и (9) справедливы для любого $n$, как четного, так и нечетного.
Используя термин множества почти равной мощности для множеств, количество элементов которых отличается по абсолютной величине не более чем на единицу, полученный результат можно сформулировать следующим образом:
Максимальное количество ребер среди всех $n$-вершинных графов не обладающих полными $3$-вершинными подграфами дает полный двудольный граф с долями почти равной мощности.
Более того, как следует из вышеприведенных рассуждений, всякий другой граф с тем же количеством вершин и без треугольников дает меньшее количество ребер.
Рисунки 2а и 2б показывают графы, дающие максимальное количества ребер для $n=6$ и $n=7$.
|
|
| 2а | 2б |
Теперь в самый раз приступить к чаепитию!
В начале подправим равенство (7) для нечетного $n$, заменив $\dfrac{n^2}{4}$ на $\dfrac{n^2-1}{4}$. Получим: $$ p \geslant \frac{n(n-1)}{2} - \frac{n^2-1}{4} = \frac{(n-1)^2}{4} \qquad (7') $$ для нечетного $n$.
Объединяя (7) и (7'), можно оценить минимальное количество пересаживаний (то есть минимальное количество отсутствующих ребер графа): $$ p_{min}=\begin{cases} \dfrac{n(n-2)}{4}, & \text{если } n \text{ четно} \\ \dfrac{(n-1)^2}{4}, & \text{если } n \text{ нечетно} \end{cases} \qquad(10) $$
Осталось сообразить (и не только на троих, так как $n=3$ лишь частный случай), как организовать пересаживания, которые я с умным видом буду называть транспозициями.
Понятно, что без деления на два множества почти равной мощности здесь не обойдется. Коме того, поскольку нас интересуют, не существующие, а отсутствующие ребра, пересаживать надо внутри долей, а не между ними. После таких подсказок лишь самые ленивые не смогут докопаться до решения, так что очень советую поупражнять мозг, прежде чем читать дальше.
Решение. Для упрощения выкладок положим $k=\left\lfloor\frac{n}{2}\right\rfloor$. Разобьем стол «почти диагональю» на почти равные группы: в первой группе $k$ участников, во второй группе остальные $n-k$ участников.
В первой группе занумеруем участников по часовой стрелке. 1-го участника пересаживаем (по часовой стрелке) по очереди со всеми остальными членами группы. Это дает $k-1$ транспозиций, в результате которых 1-й окажется на требуемом месте в конце группы, тогда как другие члены группы не изменят своего положения друг относительно друга. После этого пересаживаем 2-го по очереди со всеми членами группы с бо́льшими номерами (то есть кроме первого). В результате этих $k-2$ транспозиций 1-й и 2-й окажутся на требуемом месте, а другие не изменят своего положения друг относительно друга. Продолжаем это делать до тех пор, пока все окажутся на требуемом месте.
Знакомые с программированием конечно заметили, что фактически сделана хорошо известная сортировка «методом пузырька» (англ. bubble sort).
Подсчитаем общее количество транспозиций: $$ (k-1)+(k-2)+\;...+\;1 = \frac{(k-1)k}{2} $$
Аналогично поступаем для второй группы, в результате чего получаем еще $\dfrac{(n-k-1)(n-k)}{2}$ транспозиций.
Если $n$ четно, то $n-k=k=\dfrac{n}{2}$, поэтому в каждой из групп будет сделано по $\dfrac{\left(\dfrac{n}{2}-1\right)\dfrac{n}{2}}{2} = \dfrac{(n-2)n}{8}$ транспозиций, а всего $\dfrac{n(n-2)}{4}$ транспозиций.
В случае нечетного $n$ получаем $k=\dfrac{n-1}{2}$ и $n-k=\dfrac{n+1}{2}$. Поэтому количество транспозиций в первой группе $\dfrac{\left(\dfrac{n-1}{2}-1\right)\dfrac{n-1}{2}}{2}=\dfrac{(n-3)(n-1)}{8}$, а во второй группе $\dfrac{\left(\dfrac{n+1}{2}-1\right)\dfrac{n+1}{2}}{2}=\dfrac{(n-1)(n+1)}{8}$, давая в итоге $\dfrac{(n-1)^2}{4}$ транспозиций.В обоих случаях результат согласуется с (10), так что никаких вопросов больше не остается. Итак, потребуется $\frac{n(n-2)}{4}$ минут в случае четного $n$ и $\frac{(n-1)^2}{4}$ при нечетном n, что в пересчете на одного человека дает $\frac{n-2}{4}$ и $\frac{(n-1)^2}{4n}$ минут соответственно.
Окончание следует
Комментариев нет:
Отправить комментарий