Графы и турниры

Предположим, что утверждение неверно; скажем, из города нельзя добраться до по городам республики.

Обозначим через множество всех городов республики, до которых можно добраться из по городам республики (включая сам город ), а через — множество всех остальных её городов (оно непусто, так как содержит ). Тогда города республики разбились на две группы так, что все дороги между группами направлены от к

Обозначим количество городов в группах и через и соответственно, Пусть в городов не меньше, чем в то есть В есть город Z, из которого выходит не менее дорог в города из Кроме того, из выходит дорог к городам группы Значит, из выходит не менее дорог. Противоречие.

Случай, когда в больше городов, чем в рассматривается аналогично.

Рассмотрим путь, соединяющий некоторые две вершины возможно включающий в себя выкинутые рёбра. Покажем, что в этом пути любое выкинутое ребро можно заменить последовательностью невыкинутых. Пронумеруем цвета числами от до По условию полностью сохранились рёбра одного цвета: предположим, что в первого. Тогда выкинули по одному ребру каждого из цветов от до Рассмотрим только рёбра первого и второго цветов: до выкидывания из каждой вершины выходило по одному ребру этих цветов. Следовательно, все города разбиваются на циклы. В одном из этих циклов закрыли один рейс. Очевидно, можно пролететь остальными рейсами этого цикла, следовательно, мы можем обойти любой закрытый рейс. Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтись без остальных закрытых рейсов.

Первый вопрос задается про две крайние карты, а второй — про -ю и -ю. Далее задаем вопросы о таких парах карт: -я и -я; -я и -я; -я и -я, -я и -я и т. д. При этом за вопроса удается определить положение трех карт.

Покажем, что меньшим числом вопросов обойтись нельзя. Построим граф: вершинами являются карты, а ребром между парой карт — вопрос. Если вопросов-ребер только то в графе не менее компонент. Отсюда легко следует, что имеется либо две компоненты, состоящие из одной вершины-карты, либо компонента, в которой ровно вершины. В обоих случаях можно эту пару карт поменять местами, не трогая остальных: все ответы не изменятся. Тем самым порядок не восстанавливается однозначно.

Переформулируем условие задачи на язык графов. Каждому племени поставим в соответствие вершину, между любыми двумя соседними проведем ребро. Для каждой вершины определен ее идол, если идол соседней вершины сильнее, то в этот день вершина меняет своего идола на более сильного.

Будем решать задачу индукцией по количеству вершин. База индукции для графа, состоящего из одной вершины, очевидна.

Докажем, что если условие задачи верно для некоторого натурального то оно же верно для Выберем висячую вершину исходного дерева, родителем которой является вершина

Будем говорить, что вершина влияет на вершину если данные вершины являются соседями и идол сильнее идола при этом не имеет соседа с более сильным идолом, отличным от

Если не существует дня, в котором вершина влияло на вершину В графе, полученном из данного удалением вершины по предположению индукции все вершины через несколько дней будут иметь одного и того же идола, в частности его же будет иметь вершина а значит и вершина

Предположим, что существует день, в котором повлияло на После этого дня вершины и имеют одинакового идола. Теперь, если вершина меняет идола на более сильного, то на следующий день так же начинает поклоняться этому идолу, а значит не наступит дня, в котором имело бы более сильного идола, следовательно больше никогда не повлияет на тем самым мы можем применить рассуждения, проделанные ранее, для дня, после которого вершина повлияла на

Сначала покажем, что последовательностей не хватит.

Построим граф, вершины которого это числа от до , а рёбра между вершинами и проводятся, если в одной из последовательностей числа и были подряд идущими членами.

Так как суммарно во всех -x последовательностях каждое число будет соседом не более других чисел, степень каждой вершины в этом графе не превосходит .

Тогда выберем в графе две несмежные вершины Так как степень каждой из них не более , а всего вершин , то найдется хотя бы вершина , которая не соседствует с обеими вершинами . Тогда множество чисел не будет удовлетворять условию задачи (ни в одна последовательности нет двух или трех подряд идущих членов, которые содержатся в )

_________________________________________________________________________________________________________________________________________________________________________________

Пример на последовательностей опишем пример в терминах графа.

Разделим чисел на две равные группы: например, и .

Отдельно расставим первые чисел в последовательностей длиной , чтобы любые числа были соседями в хотя бы одной из последовательностей. (То есть на языке графов: нужно покрыть путями полный граф на вершинах). И аналогично поступим со второй группой чисел, а потом просто “склеим” последовательности. Например, если первая последовательность в первой группе это , а первая последовательность во второй - это , то склеиваем и получаем .

Опишем построение последовательностей длиной . Поместим вершины в правильный многоугольник и покроем полный граф на этом подмножестве вершин последовательностями (то есть путями проходящими по всем вершинам), идущими зигзагом через многоугольник с поворотом каждого пути на кратный угол. На картинке пример построения последовательностей, для чисел:

Теперь поясним, почему после "склейки"полученные последовательностей будут удовлетворять условию. Какие бы числа , мы ни взяли, либо два из них будут среди чисел от до , либо среди чисел от до . Тогда два числа из одно группы соединены ребром, то есть являются соседями в одной из последовательностей. Этого мы и добивались.

Докажем утверждение задачи по индукции. Для двух городов утверждение очевидно. Пусть верно для городов, докажем для Выкинем некоторую вершину и все рёбра, с концом в этой вершине. Для оставшегося графа верно предположение индукции, то есть существует вершина такая, что из него можно добраться до любой другой по не более, чем рёбрам. Пусть из вершины напрямую можно добраться в вершины а только через другую вершину в Если из вершины или из какой-нибудь из вершин ребро ведёт в то вершина по-прежнему подходит. Если же во все эти вершины ведут рёбра из то подойдёт вершина в вершины можно попасть непосредственно, а в вершины — через вершины

Заменим каждую белую улицу города на две, синюю и красную, соединив синим цветом концы синих улиц, соседних с белой, а красным цветом — концы соседних с ней красных улиц (см. рис. ). В соответствии с рисунками рис. будем называть белые улицы улицами типов и а их количества обозначим соответственно и В случаях, изображенных на рис. и рис. будем считать, что красная и синяя улицы, которыми мы заменили белую, пересекаются в точке, отличной от вершин ломаных, которыми являются эти улицы.

Теперь все синие улицы образуют несколько многоугольников. Назовем их синими. Аналогично, красные улицы образуют несколько красных многоугольников. Ясно, что границы двух многоугольников разного цвета либо не пересекаются, либо пересекаются в четном числе точек (если границы пересекаются, то граница одного из многоугольников входит внутрь второго столько же раз, сколько и выходит из него). Но число точек пересечения границ многоугольников разного цвета равно числу белых улиц типов и т. е. Значит, число — четное.

Остается заметить, что разность между числом положительных и числом отрицательных перекрестков равна и, следовательно, кратна четырем.

Лемма. В сильно связном турнире существует гамильтонов цикл.

Доказательство. В сильно связном турнире есть циклы. Рассмотрим в нашем турнире максимальный простой цикл Предположим, что в него вошли не все вершины графа, пусть вершина не вошла в этот цикл. Пусть не все стрелки между и циклом ориентированы одинаково. Тогда существуют последовательные вершины цикла и такие, что В этом случае несложно удлинить максимальный цикл вставив вершину между и противоречие.

Пусть из всех вершин цикла стрелки входят в Ввиду сильной связности турнира существует путь от до цикла Пусть впервые пересекает цикл в вершине Тогда, опять же, несложно удлинить наш максимальный цикл, заменив стрелку на путь Противоречие. Случай, когда из выходят ребра ко всем вершинам цикла аналогичен. _________________________________________________________________________________________

Вернемся к доказательству основной задачи. По лемме в есть гамильтонов цикл . Нумерация вершин — циклическая, то есть Пусть длина диагонали цикла — это остаток от деления на числа

Если количество вершин в равно или то почти транзитивен.

Далее Рассмотрим два случая. Будем говорить, что если в ребро между и направлено к

1. Для каждого выполняется

Тогда пусть состоит из всех вершин с нечётными номерами, — из и всех вершин с чётными номерами. Нетрудно видеть, что а индуцированные турниры и — сильно связные.

2. Существует диагональ

Не умаляя общности будем считать, что Докажем, что при диагональ Пусть это не так, тогда выберем диагональ где и — максимально. Понятно, что выполняется хотя бы одно из условий и Пусть (второй случай аналогичен). Тогда следовательно, для множеств и индуцированные турниры и сильно связны, В этом случае утверждение доказано.

Итак, при и мы имеем Осталось разобраться, как направлены стрелки, инцидентные Если существует такое что то множества

таковы, что турниры и сильно связны и В этом случае утверждение доказано.

Остаётся случай, когда для некоторого в нашем графе стрелки ориентированы таким образом:

При турнир почти транзитивен (с порядком ). При турнир почти транзитивен (с порядком ). Если же то Следовательно, множества и таковы, что и сильно связны и

Переформулируем условие задачи на язык графов. Пусть 30 учеников — это 30 вершин, а когда два человека дежурили вдвоём, то соединим их ребром. Тогда давайте рассмотрим получившиеся компоненты связности(она может быть и одна). Мы утверждаем, что среди них есть дерево. Действительно, если это не так, то, просуммировав по всем компонентам, мы получим хотя бы 30 рёбер. Но по условию дежурств, то есть рёбер, всего 29. Значит, дерево есть, и в нём как раз, чередуя оценки 3 и 5, выставим их всем ученикам. А остальным поставим четвёрки.

Для начала покажем, что поставить не получится. Предположим, что мы смогли это сделать. Рассмотрим граф, в котором короли — это вершины. Рёбрами соединим королей, которые друг друга бьют. Тогда, с одной стороны, мы получили граф, в котором рёбер (потому что все короли бьют всех королей на всех соседних клетках). С другой же стороны, каждый раз добавляя очередного короля (кроме первого), мы добавляли в граф нечётное количество рёбер. В граф нечётное количество раз () было добавлено нечётное количество рёбер. Значит, количество рёбер в графе должно быть нечётным. Пришли к противоречию.

Теперь приведём пример на Нужно ставить королей в следующем порядке на клетки с координатами:

Оценка. Три квадрата при вершине куба образуют цикл соседних квадратов длины Вокруг него образуется ещё один цикл длины из соседних клеток. А вокруг него — цикл длины Взяв вокруг двух противоположных вершин куба по три таких цикла, а вокруг остальных вершин — по два малых цикла, получим непересекающихся нечётных циклов. Поскольку нечётный цикл в два цвета правильно покрасить нельзя, каждый из них содержит чёрную клетку.

Пример. Красим боковые грани куба в шахматном порядке в жёлтый и зелёный. В основаниях красим главные диагонали красным, остальное докрашиваем в шахматном порядке жёлтым и зелёным.

Назовём префиксом какое-то количество первых дней июля. Всего префиксов (может быть префикс из дней). Тогда любой промежуток является разностью двух префиксов. Нетрудно понять, что промежуток будет нечётным, если он является разностью префиксов разной чётности.

Рассмотрим граф, в котором вершинами являются префиксы. Ребром соединим префиксы, у которых разная чётность. Получился двудольный граф, в котором вершин соответствуют чётным префиксам и — нечётным. В двудольном графе не более рёбер. То есть всего не более промежутков. В качестве примера можно сделать все дни дождливыми.

Первое решение. Индукцией покажем, что для городов База очевидна.

Шаг индукции. Пусть для городов стёрто не более записей. Выберем город для которого стёрто хотя бы одно расстояние до другого города, и рассмотрим остальные городов. Между ними стёрто не более расстояний, и по предположению индукции можно восстановить все эти расстояния, а тогда и взаимное расположение этих городов на плоскости. Для города известны расстояния по крайней мере до трёх городов, и это позволяет однозначно восстановить его расположение. Увеличить до нельзя. Пусть неизвестны расстояния от точки до всех точек, кроме и Тогда положение точки определено с точностью до симметрии относительно прямой значит, расстояния от неё до остальных точек не восстанавливаются.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Рассмотрим граф со вершинами и рёбрами, соответствующими стёртым записям. Этот граф содержит не менее четырёх компонент связности. Зафиксируем по вершине ) в каждой из этих четырёх компонент. Все расстояния между этими вершинами известны. Рассмотрим произвольную вершину первой компоненты. Известны её расстояния до точек следовательно, положение соответствующего города на плоскости определено однозначно. Аналогична ситуация с вершинами оставшихся компонент.

Рассмотрим вершину Она соединена с тремя вершинами и Получается, что все остальные вершины должны быть соединены с какой-то из вершин иначе между ними и не будет пути длиной не более Вершины могут быть соединены суммарно не более чем с вершинами помимо Значит, всего не более вершин. Пример на вершин представлен ниже:

1. В полном графе на четырех вершинах есть только 2 вида остовных деревьев: 1) цепь длины 4; 2) три вершины, "висящие"на четвертой.

Каждое дерево первого вида даст в остовный многочлен одночлен , , причем каждый одночлен будет представлен 2 раза.

Каждое дерево второго вида даст в остовный многочлен одночлен , где — "вершина"остова.

В итоге получим многочлен:

________________________________________________________________________________________________________________________________________________________________________________________________________

2. Распишем . Поскольку многочлен линеен по каждой переменной, получаем, что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам не более четырех мономчиков, противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

3. Давайте сначала заметим, что можно последовательно выкидывать вершины по одной с сохранением связности, если связно. (Если несвязно, то просто 0 получится и все).

Для этого нужно подвесить за и поочередно удалять вершины с самого нижнего уровня. Теперь нужно понять, что при удалении только одной вершины граф остается хорошим. Для этого подставим 0 в . Получим, что все слагаемые, в которые входило в хотя бы первой степени, обнулились, а значит остались в точности те, где — висячая вершина. А все такие деревья устроены так: выбрано дерево в графе , и потом одна из вершин из окрестности соединена с . Тогда многочлен после подстановки нуля равен . Подстановка нуля сохраняет раскладываемость на множители, значит тоже раскладываемый, значит, при удалении вершины граф останется хорошим.

_________________________________________________________________________________________________________________________________________________________________________________

4. Сначала докажем вспомогательный факт про такой тип графов.

Лемма о раздвоении без добавления ребра. Пусть дан граф на вершинах. Рассмотрим граф , полученный из добавлением вершины и соединением ее со всеми вершинами из , но не самой . Тогда

Доказательство. Давайте заметим, что любое дерево в графе устройство следующим образом — на всех вершинах, кроме , берется некоторый лес, такой, что в каждой компоненте есть хотя бы одна вершина из , и потом вершина соединяется с ровно одной вершиной из каждой компоненты. Обозначим за множество всех таких лесов, за — число компонент связности в лесу , и назовем пересечения множеств с компонентами связности леса . Тогда из рассуждений выше

Теперь давайте поймём, как устроены деревья в . Там мы тоже берём лес, который содержит все вершины, кроме , , и такой, что каждая его компонента содержит хотя бы одну вершину из , после чего одна из долей соединяется с обеими вершинами из и , а каждая из остальных долей — с ровно одной из этих вершин. Тогда в тех же обозначениях получается, что

Теперь очевидно, что второй сомножитель равен , и лемма доказана.

Лемма 2 (Лемма о раздвоении с добавлением ребра). Пусть дан граф . Рассмотрим граф , получаемый из добавлением вершины и соединением её со всеми вершинами из , а также с самой . Тогда

Доказательство. Пусть — граф из леммы Мы в лемме уже выяснили как устроены деревья в графе поэтому нужно разобраться с тем, как они устроены в . Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем одно из двух — либо не проводим ребро между и , и это слагаемое такое же как в , либо проводим, и тогда каждую из долей соединяем с ровно одной из этих вершин. Стало быть, сумма всех первых слагаемых даст нам , а сумма вторых равна

Тогда получается, что

доказали требуемое.

Пусть в турнире участвовало команд. Заметим, что в каждом матче две команды в сумме получают 2 или 3 очка. Значит, общее количество очков, которые могут набрать все команды в одном круге, не меньше, чем , и не больше, чем . Из условия следует, что все команды вместе набрали в первом круге ровно в полтора раза больше очков, чем во втором ( всех очков в первом круге и во втором). Но это возможно лишь в случае, если в первом круге все матчи закончились победой одной из команд (общая сумма очков ), а во втором - ничьей (общая сумма очков ). Значит, победитель набрал во втором круге очков. По условию, , откуда находим .

Пусть осталось дорог между городами. Заметим, что такой граф является деревом(связность между вершинами не исчезает при выполнении операции), а значит, двудольным. Причём обратная операция к исходной будет такая, что находится три смежных ребра и проводится четвёртое между крайними, чтобы получался цикл из четырёх рёбер. Но в таком случае двудольность будет сохраняться, потому что будут появляться только чётные циклы. Докажем это утверждение по индукции. Будем ввести её по количеству добавленных рёбер при обратной операции. База, когда у нас есть просто дерево, и мы проделываем одну обратную операцию, очевидна. Предположение, пусть на -ой обратной операции у нас получались так же только чётные циклы. Рассмотрим граф с -ой операцией и уберём последнее добавленное ребро. По предположению остался граф только с чётными циклами. Попробуем вернуть ребро. Если мы выбрали три ребра, не входящие ни в какой цикл, то получается чётный цикл. Допустим теперь обратное. Тогда получается, что мы на самом деле заменяем три ребра в цикле чётной длины на одно ребро. Чётность количества рёбер не меняется, а значит, и нечётных циклов появиться не могло. Таким образом, так как двудольность сохраняется на протяжении всего процесса, то и изначальный граф должен быть двудольным, но это не так(он полный). Противоречие.

Рассмотрим ориентированный граф, соответствующий условию задачи. Рассмотрим среди всех ацикличных подграфов нашего графа тот, в котором наибольшее количество рёбер. Пусть ребро не вошло в выбранный подграф. Поскольку его нельзя добавить, то среди выбранных рёбер есть путь, идущий из в Хорошо известно, что в графе нет циклов тогда и только тогда, когда его вершины можно занумеровать числами от до количества вершин так, чтобы рёбра шли только из вершин с меньшими номерами в вершины с большими номерами. Давайте возьмём такую нумерацию нашего подграфа, а все рёбра, не вошедшие в подграф, обратим. Заметим, что в новом графе существует путь наибольшей длины, не проходящий по перевёрнутым рёбрам, ведь каждое из них можно заменить на путь по неперевёрнутым: при это получится простой путь, так как номера вершин в полученном пути возрастает. Кроме того, в нём нет циклов. Значит, полученное обращение подходит.

Рассмотрим граф, в котором города — вершины, а авиалинии — рёбра. Рассмотрим подграф из вершин с наибольшим количеством рёбер и подграф из оставшихся вершин.

Пусть вершина из подграфа соединена с наименьшим количеством вершин в этом подграфе ( вершин). Предположим, что в подграфе имеется вершина , которая соединена с хотя бы вершиной из подграфа . В таком случае вершину можно переместить в подграф вместо вершины и в нём будет больше авиалиний, что противоречит выбору подграфа . Следовательно, любая вершина из подграфа связана не более чем с вершинами из подграфа .

Значит, между этими подграфами не более рёбер. Внутри же каждого из этих подграфов не более рёбер. Значит, всего в графе не более

Как известно, — это наименьшая степень вершины в подграфе . Значит, в не менее рёбер. С другой стороны, в этом подграфе не более рёбер, откуда . Теперь мы можем оценить количество рёбер в графе: .

_________________________________________________________________________________________________________________________________________________________________________________

Приведём пример на рёбер. Разбиваем города на групп по городов. Внутри групп между городами авиалиний нет, а между городами из разных групп — есть.

Пусть выбрано городов так, что из них город из первой группы, из второй, , — из -й. Тогда количество пар, не соединённых авиалиниями, будет не менее

по неравенству между средним квадратическим и средним арифметическим

Мы показали, что для произвольного подграфа в примере выполняется условие задачи.

Представим страну как граф, где вершины — города, а ребра — дороги между городами.

“Подвесим” наш граф за какую-либо вершину. На первом уровне у нас будет только одна вершина, за которую мы подвешиваем. На втором уровне у нас будут все вершины, в которые можно попасть из вершины на первом уровне. На третьем уровне будут все вершины, в которые можно попасть из вершин второго уровня, которых нет на предыдущих двух уровнях. На четвертом уровне будут все вершины, в которые можно попасть из вершин третьего уровня, которых нет на предыдущих трех уровнях.

Докажем, что все вершины лежат на этих уровнях. Пойдем от противного, пусть существует такая вершина, что не принадлежит ни одному из этих уровней. Но тогда путь из вершины, за которую мы подвешивали наш граф, до этой вершины будет иметь более промежуточных городов (потому что, по факту, на наших четырех уровнях лежат все вершины, до которых можно добраться из выбранной не более чем через промежуточных города). Противоречие с условием.

Теперь посчитаем, какое наибольшее количество вершин может быть в нашем подвешенном графе. На первом уровне находится только одна вершина. На втором уровне может находиться не более вершин, т.к. из вершины на первом уровне выходит не более ребер. Из каждой вершины на втором уровне на третий уровень уходит не более ребер, поскольку одно ребро уходит на первый уровень. Т.е. на третьем уровне вершин не более чем в раза больше, чем на втором, или же не более Аналогично вершин на четвертом уровне больше, чем на третьем, не более чем в раза, т.е. не более Тогда в сумме у нас не более вершины в графе. На языке задачи получаем, что в стране не более городов.