Тема КОМБИНАТОРИКА

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Графы и турниры

Индукция в графах и теорема Турана

Турниры в терминах графов и не только (считаем игры и очки)

Лемма о рукопожатиях

Считаем рёбра

Простой путь, Гамильтонов путь, Гамильтонов цикл

Подвешивание, ранжирование, упорядочивание в графах

Эйлеровы графы

Планарные графы

Гуляем по графу

Числа Рамсея

Раскраски графов

Деревья и остовные деревья

Двудольные графы и переформулировки к ним

Связность и связные подграфы (клики)

Паросочетания и лемма Холла

Формула Эйлера для графов и многогранников

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#82623

На чемпионат по игре в шляпу приехало $n$ команд, в каждой из которых по два человека. Все $2n$ участников произвольным образом уселись за круглый стол. После этого все спохватились, что игру можно начать, только когда люди из одной команды будут сидеть напротив. За одно действие разрешается поменять любых двух участников местами. Какое наименьшее число действий придется совершить, чтобы гарантировано можно было начать игру?

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Покажите, что в любом случае число циклов увеличивается, не более чем на один. Каким тогда может быть ответ? А как придумать пример?

Показать ответ и решение

Построим граф, в котором вершинами обозначим места за столом. Две вершины будем соединять ребром, если соответствующие места находятся напротив друг друга, или если на соответствующих местах сидят напарники по команде. В построенном графе степень каждой вершины равна $2$ (если сокомандники уже сидят напротив друг друга, то они соединены двумя рёбрами). По лемме о хороводах этот граф представляет из себя один или несколько непересекающихся циклов. Заметим, что если мы поменяем местами двух напарников, граф не изменится. Допустим, мы меняем местами двух находящихся в одном цикле людей $A$ и $B$ из разных команд. Обозначим их напарников через $a$ и $b.$ Сперва допустим, что $a$ и $b$ находятся на одной и той же из двух дуг, на которые $A$ и $B$ разбивают цикл. В этом случае наш цикл остается циклом:

$PIC$

Допустим теперь, что $a$ и $b$ находятся на разных дугах. В этом случае наш цикл распадается на два:

$PIC$

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

$PIC$

В каждом из случаев число циклов в графе за одну операцию можно увеличить не более чем на один. Если изначально каждый из участников сидит рядом со своим напарником, то граф представляет из себя один цикл. Мы должны получить граф, состоящий из $n$ циклов длины $2.$ Так как на каждом шаге число циклов возрастает не более, чем на $1,$ добиться этого менее чем за $n − 1$ шагов нельзя. Отметим, что любой цикл длины более чем $2$ можно за одну операцию разбить на два меньших, т.е. за $n− 1$ операций можно от любого начального расположения прийти к ситуации с $n$ циклами, т.е. к искомой ситуации.

Ответ:

$n − 1$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#93851

(a) Каждое из рёбер полного графа с 6 вершинами покрашено в один из двух цветов. Докажите, что есть три вершины, все рёбра между которыми — одного цвета.

(b) Каждое из рёбер полного графа с 9 вершинами покрашено в синий или красный цвет. Докажите, что или есть четыре вершины, все рёбра между которыми — синие, или есть три вершины, все рёбра между которыми — красные.

Подсказки к задаче

Подсказка 1

При прочтении условия вам должна приходить на ум одна популярная задача, которая звучит так: Докажите, что в компании из 6 человек либо есть трое попарно знакомых, либо трое попарно незнакомых. Если заменить слово "знакомых" красное ребро, а слово "незнакомых" синее, то становится понятнее, как её применить к нашей задаче.

Подсказка 2

Задача из предыдущей подсказки не совсем вписывается в контекст данной, потому что нас просят либо синий полный граф на 4 вершинах, либо красный на трëх. Подумайте, как дополнить граф из 6 вершин с красными и синими ребрами одной вершиной, чтобы приблизить его к нашей задаче.

Подсказка 3

Давайте предположим, что в графе есть вершина, из которой выходит хотя бы 6 синих рëбер. Что можно сказать про 6 вершин, соединённых с ней синими рëбрами?

Показать доказательство

(a) Рассмотрим вершину $A.$ Из неё исходит $5$ рёбер, притом хотя бы $3$ из них одного цвета. Пусть они соединяют $A$ с вершинами $B,C$ и $D.$ Заметим, что если какие-то две из этих вершин соединены ребром того же цвета, то мы получим нужную тройку вершин. Предположим, что все рёбра между $B,C$ и $D$ покрашены в другой цвет. В этом случае $BCD$ — нужная тройка вершин.

(b) Пусть есть вершина, из которой выходит шесть синих рёбер. Тогда рассмотрим $6$ вершин, соединённых с ней синими рёбрами. Давайте вспомним известную задачу, которая утверждает, что в компании из $6$ человек есть либо трое попарно знакомых, либо трое попарно незнакомых. То есть среди этих вершин есть либо $3,$ попарно соединённых красными рёбрами, либо синими. Оба случая решают задачу.

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

Ошибка.
Попробуйте повторить позже

Задача 3#103477

На доске $100× 100$ отмечены $n$ клеток. Известно, что ладья, начав с любой из отмеченных клеток, может за несколько ходов оказаться в любой строке, а также в любом столбце, причем она может перемещаться только по отмеченным клеткам. Какое наименьшее количество клеток может быть отмечено на доске?

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Популярным является представление доски как двудольного графа, где каждому столбцу поставлена в соответствие вершина левой доли, а каждой строке — правой. Чем будут клетки в данном представлении?

Подсказка 3

Для каждой отмеченной клетки, которая стоит на пересечение i строки и j столбца проведем ребро. Каким является граф, если, начиная в любом столбце (строке), можно перейти в любой столбец (строку)?

Подсказка 4

Связным. Как оценить снизу количество ребер в связном графе?

Подсказка 5

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

Показать ответ и решение

Пример. Отметим все клетки первой строки и первого столбца.

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

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

100+ 100 − 1= 199

Ответ:

$199$

Ошибка.
Попробуйте повторить позже

Задача 4#103481

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

Подсказки к задаче

Подсказка 1

Число 20 выглядит произвольным. Скорее всего, задача имеет будет общее решение для произвольного количества кружков. Сколько вопросов необходимо задать, чтобы узнать списки 2, 3 кружков?

Подсказка 2

Необходимо 2 и 3 вопроса соответственно. Отсюда может появиться предположение, что ответом на задачу является количество кружков, то есть 20. Почему этого количества вопросов будет достаточно?

Подсказка 3

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

Подсказка 4

Потребуем, чтобы весь список каждого кружка был уникален. Например, этого можно добиться, если количество учеников будет равно 2^20, причем каждый будет посещать уникальное множество кружков. Как удобно изображать множество вопросов, заданных в алгоритме?

Подсказка 4

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

Подсказка 5

В нем существует компонента, которая является суть путем. Что теперь нужно для того, чтобы закончить доказательство?

Подсказка 6

Можно доказать, что найдутся множества кружков A и B, для которых найдется школьник, который ходит только в кружки множества A, и школьник, который ходит только в кружки множества B, по ответам неотличимы. Найдите соответствующие множества среди кружков, соответствующих вершинам найденного пути.

Показать ответ и решение

Пример. Спросим про пары $(1,2),$ $(2,3)$ и $(3,1),$ а затем про все пары вида $(1,k),$ где $k= 4,...,20.$ Докажем, что за первые три вопроса мы выясним составы кружков $1,$ $2$ и $3.$ Посмотрим на любого человека. Если он не ходит ни в один из этих кружков, то его имя не будет названо ни разу, и это ни с чем не перепутаешь. Если он входит только в один кружок, то его имя всплывёт в двух вопросах, как посещающего один кружок. При этом по этим двум парам мы восстановим, в какой кружок он ходит. Если он ходит в два кружка, то однажды он появится, как посещающий два кружка, и дважды — как посещающий один из двух. В этой ситуации легко вычисляется, куда он ходит. Если он ходит во все, то во всех парах покажется, как посещающий оба, и тоже получится вычислить, что он во все ходит. То есть про любого человека мы поймём, куда он ходит, а это и значит, что вычислим составы всех кружков. Теперь, зная, кто ходит в первый кружок, после вопроса $(1,k)$ легко вычисляем, кто ходит в кружок $k.$

Оценка. Будем считать, что в школе $220$ учеников. Каждому ученику сопоставим уникальное подмножество кружков и направим его ровно в кружки из его подмножества. Предположим, что после $19$ вопросов удалось выяснить составы всех кружков. Это значит, что мы научились различать всех учеников. Рассмотрим граф, вершины которого — кружки. Соединим вершины ребром, если мы спросили про эту пару кружков. В графе $20$ вершин и $19$ рёбер, значит, хотя бы в одной компоненте связности рёбер меньше, чем вершин, то есть эта компонента связности — дерево. А вершины дерева можно правильным образом покрасить в два цвета. Обозначим множества вершин первого и второго цвета $A$ и $B.$ Тогда школьник, который ходит только в кружки множества $A,$ и школьник, который ходит только в кружки множества $B,$ по ответам не отличимы. Во всех вопросах про эту компоненту связности оба назывались как ходящие в один из двух кружков.

Ответ:

$20$

Ошибка.
Попробуйте повторить позже

Задача 5#105484

Даны $1000$ целых чисел. Докажите, что их можно покрасить в два цвета так, чтобы отношение двух чисел одинакового цвета не было простым числом.

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Верно! Давайте проведем ребра в графе, если отношение двух чисел является простым. Заметим, что теперь достаточно показать двудольность графа. Как это сделать?

Подсказка 3

Можно вспомнить критерий двудольности: в графе не должно быть нечетных циклов. А почему их действительно нет?

Подсказка 4

Если две вершины соединены ребром, то четности сумм вхождений степеней простых у соответствующих чисел различны. Какой вывод можно сделать?

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 6#105486

Есть $2n$ болельщиков: $n$ из них болеют за “Реал”, а остальные $n$ — за “Барселону”. Разрешается спросить у любых двоих, болеют ли они за разные команды, и они честно ответят “да” или “нет”. Требуется посадить болельщиков в два автобуса так, чтобы в каждом были болельщики только одной команды. За какое минимальное количество вопросов это наверняка можно сделать?

Подсказки к задаче

Подсказка 1

Можно ли восстановить рассадку за 2n-1 вопрос?

Подсказка 2

Да, выбрать человека A и для каждого другого человека С задать вопрос про пару (A, C). Как исходя из ответов, рассадить людей по двум автобусам? Можно ли улучшить эту оценку до 2n-2? Обратите внимание, что мы не пользовались тем, что за каждую из команд болеет поровну человек.

Подсказка 3

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

Подсказка 4

Любой вопрос - это отношений двух людей. Отношение между двумя объектами из множества удобно представлять в виде графа. Вершины - люди. Если существует вопрос про пару людей, то между ними можно провести ребро. Сколько компонент связности может быть в графе, если в нем проведено не более 2n-3 рёбер?

Подсказка 5

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

Подсказка 6

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

Показать ответ и решение

Рассмотрим граф из вершин-болельщиков. Ребро проводится между двумя людьми, когда им задают вопрос, и вершина красится в один из двух цветов в зависимости от того, за какую команду они болеют. Выберем человека $A,$ человека $B$ и остальных обозначим $C1,C2,...,C2n−2.$ Спросим $A$ и $Ci$ для $i= 1,2,...,2n− 2.$ Тогда людей $A,C1,...C2n−2$ можно распределить по двум автобусам. Человека $B$ определим в автобус с меньшим числом людей (корректность этого действия следует из того, что число болельщиков за каждую из команд одинаково). Итак, задано $2n − 2.$ Теперь сделаем оценку.

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

Предположим теперь, что задано не более, чем $2n− 3$ вопросов. Тогда в графе хотя бы 3 компоненты связности: если бы их было не более, чем две, но тогда ребер хотя бы $2n − 2$ — противоречие. Предположим, что теперь две из этих компонент четны. Теперь рассмотрим все наши компоненты связности. Среди них четное число нечетных компонент связности (по числу вершин). Пусть внутри каждой компоненты вершины раскрашены в красный и зеленый цвета. Можно считать, что в каждой нечетной компоненте зеленого цвета на 1 больше. Тогда разобьем все нечетные компоненты на пары, вершины зеленого цвета из одной компоненты объединим с красными из второй и наоборот и будем думать, что это болельщики одной команды, тогда пара (зеленые, красные) отправляется в первый автобус, а пара (красные, зеленые) во второй. Для четных компонент достаточно зеленую половину посадить в один автобус, а четную во второй.

Покажем, что теперь можно найти и вторую корректную рассадку. Если есть четная компонента связности, то в ней можно поменять болельщиков красного и зеленого цвета (то есть поменять их местами в автобусах). Противоречия при этом, очевидно, нет. Предположим теперь, что четных компонент нет, при этом у нас хотя бы три компоненты. Тогда на самом деле есть хотя бы 4 компоненты связности. Тогда вспомним, как строилась рассадка: выбирались зеленые вершины из одной компоненты и красные из второй. Таким образом, две компоненты дают два набора вершин. Если теперь для этих наборов вершин поменять автобусы местами, то снова не возникнет противоречия. Таким образом, если задано не более $2n − 3$ вопросов, то существует две подходящих рассадки (рассадка не определяется однозначно) — противоречие.

Ответ:

$2n− 2$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#106843

Рёбра дерева окрашены в два цвета. Если в какую-то вершину приходят рёбра только одного цвета, то их все можно перекрасить в другой цвет. Можно ли все дерево сделать одноцветным?

Подсказки к задаче

Подсказка 1

Попробуем применить индукцию по числу ребер для доказательства положительного ответа. База для n = 2 очевидна. А как уменьшить число ребер в дереве для перехода?

Подсказка 2

Верно! Найдем висячую вершину и удалим ее)вместе с ребром). К меньшему графу индукционное предположение применить можно. А почему нам не помешает удаление одного ребра?

Показать ответ и решение

Да, можно. Будем доказывать это по индукции по количеству ребер. База $n =2$ очевидна. Докажем индукционный переход. Найдем в нашем дереве висячую вершину. Заметим, что ребро, которое соединяет дерево и эту висячую вершину, мы можем в любой момент покрасить в любой цвет (применяя условие для этой висячей вершины), а остальной граф не трогать. Поэтому давайте удалим эту вершину с этим ребром и применим индукционное предположение к оставшемуся графу (оно будет корректно, так как единственное что могло нам помешать это применение условия для второго конца удаленного ребра, но мы поняли, что всегда можем покрасить удалённое ребро в нужный нам цвет и остальной граф не менять). В итоге, мы покрасили весь граф, кроме удаленного ребра в один цвет, а дальше просто вернем ребро и покрасим его в нужный цвет.

Ответ:

Да

Ошибка.
Попробуйте повторить позже

Задача 8#106844

В королевстве Нечетномонголия $n$ городов и полностью отсутствуют дороги. Король решил соединить дорогами хотя бы какие-нибудь города, однако его ограничивает древнее предание, согласно которому юная дева, выехавшая из родного города и вернувшаяся в него, проехав по одному разу через нечётное число других городов, погубит монархию. Какое наибольшее количество дорог сможет провести король так, чтобы не дать шанса юной деве?

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Конечно, можно: нужно просто сделать для них общую вершину! Если n = 2k+1, то треугольников будет k, а если n = 2k, то будет k-1 треугольник и висячая вершинка. Итак, ответ есть, остается проверить его по индукции! Базу надо проверять аккуратно: нам она нужно и при n=1, и при n=2, так как ответ зависит от четности. А как можно осуществить переход?

Подсказка 3

В графе без нечетных циклов, подходящий нашему условию, циклов вообще быть не может! Но тогда ребер в нем не больше, чем n-1. А что делать с нечетным циклом?

Подсказка 4

На самом деле, очевидно, что четных циклов не может быть в нашем графе. Тогда ясно, что две вершины нечетного цикла не могут быть соединены с одной и той же вершиной. Хочется этот цикл убрать, чтобы применить предположение. Для этого его можно стянуть в одну вершину, но сначала нужно проверить посылку индукции! Как это сделать?

Подсказка 5

Предположим, что после стягивания организовался четный цикл. Тогда он проходит через новую вершину V, соответствующую стянутому циклу! Если теперь взять две вершины, связанные с V в новом графе по циклу четной длины, то нетрудно видеть, что и в исходном был такой цикл! Значит, стягивать и применять предположение индукции можно. Как теперь оценить число ребер?

Подсказка 6

Верно! Если после стягивания осталось k вершин, то удалили мы n-k вершин и n-k+1 ребро. И число ребер в графе с k вершинами мы можем оценить! Как теперь получить нужно неравенство для исходного графа?

Показать ответ и решение

Введем граф, вершинами которого будут города, а ребрами — дороги.

Пример. Если $n = 2k +1,$ то $k$ треугольников с общей вершиной, если $n =2k$ , то $k− 1$ треугольников с общей вершиной и висячее ребро из той же вершины.

Оценка. Будем доказывать формулу, данную в ответе, индукцией по количеству вершин. База для $n= 1$ и $n= 2$ очевидна. Проведем переход от всех $k <n$ к $n.$ Рассмотрим в графе произвольный нечетный цикл. Если таких нет, то в графе вообще нет циклов, значит, и ребер в нем не больше $n − 1,$ что меньше нашего ответа. Никакие две вершины этого цикла не могут быть соединены с одной и той же вершиной из оставшихся, иначе образуется четный цикл. Стянем этот цикл в одну вершину $V,$ проведя все ребра, которые соединяли вершины цикла с остальными вершинами графа, из вершины $V.$ Если при такой операции появился четный цикл, то он проходит через новую вершину $V.$ Пусть в старом графе вершины цикла, смежные с $V,$ соединялись с вершинами $A$ и $B$ стянутого цикла. Тогда, пройдя между $A$ и $B$ по циклу путь четной длины, мы получим четный цикл, который был в исходном графе, чего не может быть. Итак, после операции стягивания граф все еще удовлетворяет условиям задачи, поэтому для него верно предположение индукции. Пусть в графе осталось $k$ вершин. Тогда в нем ребер не больше $[3(k− 1)∕2]$ по предположению индукции. Мы удалили $n− k$ вершин и $n− k+ 1$ ребер, так как вершины стянутого цикла не могли быть соединены друг с дружкой ребрами, отличными от ребер цикла, иначе образуется четный цикл. Поэтому в исходном графе на $n$ вершинах ребер не больше, чем $[3(k− 1)∕2]+ n− k+1 ≤[3(n − 1)∕2],$ так как $n> k+ 2,$ что и требовалось доказать.

Ответ:

$[3(n− 1)∕2]$

Ошибка.
Попробуйте повторить позже

Задача 9#110625

В стране $2024$ города, некоторые пары городов соединены дорогами с двусторонним движением. Дороги имеют различную длину, выражающуюся целым числом километров. Известно, что по дорогам можно доехать из любого города в любой. Вне городов дороги не пересекаются. Вася хочет проехаться на машине, проложив маршрут наибольшей длины, не заходящий ни в один город дважды. Разворачиваться посреди дорог запрещено. Какую минимальную длину может иметь такой маршрут?

Подсказки к задаче

Подсказка 1

Сначала попробуем сделать оценку. Ясно, что у любых двух ребер есть два конца, связанные маршрутом. Как из этого следует минимальная оценка?

Подсказка 2

Верно! Тогда наибольший маршрут имеет длину не меньше суммы длин двух наиболее длинных дорог. Все дороги имеют различную длину, а потому мы знаем наименьшую оценку на длину этих двух дорог! Какие тогда выходят оценка и пример, показывающий, что оценка достигается?

Показать ответ и решение

Оценка. Два наибольших ребра в соответствующем графе имеют длины не меньше $2022$ и $2023.$ При этом существует кратчайший путь от одного ребра до другого. Этот путь содержит максимум по одной вершине из каждого ребра, то есть существует и простой путь, содержащий эти ребра.

Пример. Одна вершина соединена с остальными ребрами длины $1,2,...,2023.$

Ответ:

$4045$ километров

Ошибка.
Попробуйте повторить позже

Задача 10#112338

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

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Если доминошки, затрагиваемые при удалениях в переходах к этим потомкам, не пересекаются, то это, очевидно, верно. А что делать с пересекающимися доминошками?

Подсказка 3

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

Показать доказательство

Для произвольной диаграммы Юнга рассмотрим доминошки, которые можно удалить, не потеряв корректности диаграммы. Для такой пары клеток верно, что сверху и справа от нее нет клеток. Заметим, что если две такие доминошки не пересекаются, то мы можем их удалить последовательно и получить одну и ту же диаграмму. А пересекаются они только в угле, как на картинке. Тогда удалим удалим квадрат $2×2$ двумя способами: при помощи удаления двух вертикальных доминошек и при помощи двух горизонтальных доминошек, и получим одну и ту же диаграмму Юнга.

$PIC$

Рассмотрим граф состояний диаграмм Юнга с переходами в виде удаления доминошек, так как клеток конечное число, то все пути конечны, а по доказанному выше он удовлетворяет Diamond-лемме, значит, конечное состояние — единственно.

Ошибка.
Попробуйте повторить позже

Задача 11#112341

Дан конечный граф $G,$ в вершинах которого расставлены вещественные веса (в вершине с номером $i$ вес $r). i$ Каждую минуту выбирается произвольная вершина $V$ с отрицательным весом $r.$ Ее вес заменяется на $− r,$ а к весам всех ее соседей прибаляется $r.$ Процесс заканчивается, когда веса всех вершин неотрицательны. Известно, что из исходной конфигурации процесс заканчивается в любом случае.

(a) Докажите, что результат не зависит от порядка действий;

(b) Докажите, что количество шагов также не зависит от порядка действий.

Подсказки к задаче

Подсказка 1

Пусть состояние графа — пара из графа и количества операций, произведенных на нем. Пути в графе, очевидно, конечны. Попробуем доказать, что применима Diamond-лемма. Что тогда нужно доказать?

Подсказка 2

Верно! Нужно показать, что для пары состояний, полученных операциями над вершинами a, b из состояния t найдется общее состояние t'. Если a и b несмежны, то это очевидно. А что нужно сделать, если они все-таки смежны?

Подсказка 3

Пусть C — все вершины, смежные и с a, и c b, A — смежные только с a и B — смежные только с b. Вес в вершине a обозначим r, а в вершине b — m. С помощью операций из условия задачи легко получить вес в a, равный -m, в b - вес -r, вес 2(r+m) в вершинах C и r+m во всех вершинах A и B, проводя операцию сначала над b, а затем над a. А можно ли добиться того же результата, начиная в другом состоянии?

Показать доказательство

Рассмотрим граф состояний исходного графа. Под состоянием будем иметь в виду пару из получившегося графа $G ′$ и количества операций на нем произведенных. Так как процесс в любом случае заканчивается, то в этом графе пути конечны.

Для применения Diamond-леммы необходимо показать, что для пары состояний $ta,tb$ полученных операциями над вершинами $a,b$ из состояния $t$ найдется общее состояние $′ t.$

— $a$ и $b$ не смежны, тогда преобразования над $a$ и $b$ коммутируют, так как не влияют друг на друга. Результат одинаков при любом порядке.

— $a$ и $b$ смежны, тогда при из $ta$ при помощи последовательности операций на рисунках (сначала провели операцию над вершиной $b$ затем над $a).$

$PIC$

Обозначим $Cab$ — вершины смежные и с $a,$ и с $b.$ $Na$ — смежные только с $a,Nb$ — только с $b.$ Вес в вершине $a$ — $ra,$ в $b$ — $rb.$

Тогда после описанных выше операций получим веса:

в $a: − rb$
в $b: −ra$
в $Cab$ вес изменится на $2(ra +rb)$
в $Na,Nb$ вес изменится на $ra+ rb$

$PIC$

Аналогично при помощи последовательных операций над $a,b$ придем к такому же состоянию из $tb.$ Причем количество операций в обоих случаях одинаково, тогда данное состояние $′ t$ потомок $ta,tb$ в графе состояний, значит, верна Diamond-лемма. Тогда есть единственное конечное состояние $′ G$ с $k$ произведёнными операциями, не зависящее от порядка операций и любой путь до него будет длины $k.$ Получается оба пункта доказаны.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#118955

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

Показать ответ и решение

Оценка. Обозначим через $n$ количество стран, а через $a i$ и $b i$ — количество мужчин и женщин в $i$ -й стране соответственно. По условию

∑ | (aiaj + bibj − aibj − biaj)|≤1

Заметим, что

∑ ∑ 2 ∑ 2 ∑ 2 ∑ 2 2 (aiaj + bibj)= ( ai) + ( bi) − ai − bi

∑ ∑ ∑ ∑ 2 (aibj +biaj)= 2( ai)( bi)− 2aibi

Значит,

∑ ∑ ∑ |( ai− bi)2− (ai− bi)2|≤ 2

По условию $∑ ∑ ( ai− bi)2 ≤ 1,$ поэтому $∑ (ai− bi)2 ≤ 3.$ Заметим, что если из $i$ -й страны приехало нечётное число участников, то $(ai− bi)2 ≥ 1.$ Следовательно, стран с нечётным числом участников не более трёх.

Пример. Пусть стран всего три, из двух приехало по одному мужчине, а из третьей — одна женщина.

Ответ:

$3$

Ошибка.
Попробуйте повторить позже

Задача 13#119311

В однокруговом турнире с $2n$ командами каждый тур команды разбиваются на $n$ пар и играют между собой, при этом никакие две команды не играют между собой дважды. В некоторый момент в турнире был сыгран $n − 1$ тур. Докажите, что можно составить расписание еще двух туров.

Показать доказательство

Теорема Оре: Если в графе $G$ с $n≥ 3$ вершинами для любых двух несмежных вершин $u$ и $v$ выполняется условие

deg(u)+ deg(v)≥n,

то $G$ содержит гамильтонов цикл(проходящий по всем вершинам по разу).

Доказательство. Предположим противное: пусть граф $G$ удовлетворяет условию теоремы, но не является гамильтоновым.

Рассмотрим максимальный по длине путь $P = vv ...v 12 k$ в $G.$ Все соседи $v 1$ и $v k$ лежат на $P,$ так как иначе путь можно было бы продлить. Докажем, что его можно замкнуть в цикл.

Пусть вершины $v 1$ и $v k$ не смежны, иначе мы бы замкнули путь в цикл. Обозначим:

S = {i|v1vi+1 ∈E (G)}, T = {i|vkvi ∈E (G)}.

Заметим, что $|S|= deg(v1),$ $|T|= deg(vk)$ и $S,T ⊆ {1,2,...,k− 1}.$

Из условия теоремы:

deg(v1)+deg(vk)≥ n≥ k.

По принципу Дирихле множества $S$ и $T$ пересекаются: существует $i∈ S∩ T.$ Тогда в графе $G$ существует цикл:

C = vv v ...v vv ...v. 1 i+1i+2 ki i−1 1

Этот цикл содержит все вершины пути $P.$ Если $k= n,$ то $C$ – гамильтонов цикл, что противоречит предположению.

Пусть $k< n,$ из условия на степень, окрестности любых двух несмежных вершин пересекаются, поэтому граф связен. Рассмотрим вершину $w ∕∈C,$ от нее есть путь до $C,$ что позволяет построить путь длины хотя бы $k+ 1,$ получаем противоречие с максимальностью пути $P,$ что доказывает теорему.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к решению задачи, в построенном графе выполняются условия теоремы Оре, поэтому в нём есть гамильтонов цикл. Гамильтонов цикл длины $2n$ можно разбить на два совершенных паросочетания:

Первый тур: рёбра с чётными номерами в цикле,
Второй тур: рёбра с нечётными номерами в цикле.

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

Ошибка.
Попробуйте повторить позже

Задача 14#119515

Степень каждой вершины графа не превосходит $11.$ Докажите, что все вершины этого графа можно раскрасить в четыре цвета так, что количество отрезков с одноцветными концами будет не более, чем количество вершин.

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 15#119856

В турнире по волейболу участвовало $20$ команд. Каждая команда играла со всеми остальными по одному разу, за выигрыш начислялось $3$ очка, за проигрыш очки не начислялись (ничьих в волейболе нет). Очки, набранные командами, образуют убывающую арифметическую прогрессию. Сколько очков набрала команда, занявшая второе место?

Источники: ПВГ - 2025, 11.1(см. pvg.mk.ru)

Подсказки к задаче

Подсказка 1

Давайте оценим разницу между командами, которые заняли соседние места, начиная с самой слабой. Тогда мы сможем оценить число очков для каждой команды.

Подсказка 2

Последняя команда набрала не менее 0 очков. Могла ли 19 команда набрать 1-2 очка? А 18 команда 3-5 очка?

Подсказка 3

Отлично, 19 команда набрала не менее 3 очков! А какая оценка для команды-победителя? А сколько всего она могла набрать за турнир?

Показать ответ и решение

Решим задачу в общем виде. Пусть участвовало $n$ команд, за победу даётся $a$ очков. Пусть $x$ — количество очков, набранных последней командой.

Посчитаем число разыгранных очков двумя способами. С одной стороны, это число равно

n(n− 1) a---2---

С другой стороны, так как очки распределились в арифметической прогрессии, то, обозначив ее разность через $d,$ получим

nx+ dn(n2− 1)

Значит,

nx+ dn(n−-1)-=a n(n-− 1) 2 2

Так как $d= ka,$ где $k$ — натуральное число, то:

nx+ ka n(n−-1)= an(n−-1)- 2 2

nx= (1− k)an(n−-1) ⇒ x = (1− k)n−-1 2 a 2

Значит, для $k$ есть две возможности: $k= 1,k= 0.$ При $k= 0$ получается $d= 0,$ что не годится по условию. Следовательно, $k = 1$ и $x =0.$

Тогда при $a= 3,n =20$ получаем $d =3$ и первая команда наберет $0+ 3⋅19 =57$ очков, а вторая $0+ 3⋅18= 54$ очка.

Другой способ решения.

Последняя команда в таблице набрала не менее 0 очков, 19-я команда — не менее 3 очков, 18-я команда — не менее 6 очков, …, 2-я команда — не менее $0+ 3(19− 1)= 54$ очков, 1-я команда — не менее $0+ 3⋅(20− 1)=57$ очков.

В то же время, 1-я команда не могла набрать более $19⋅3 =57$ очков, так как она сыграла 19 игр. Значит, 1-я команда набрала 57 очков, 2-я команда — 54 очка, 3-я команда — 51 очко, …, 19-я команда — 3 очка, 20-я команда — 0 очков.

Ответ:

$54$

Ошибка.
Попробуйте повторить позже

Задача 16#119886

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

Источники: Иннополис - 2025, 11.3 (см. lk-dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Переформулируем задачу: города и авиамаршруты между ними - это граф К₁₀, принадлежность маршрута авиакомпании можно принять за цвет (красим ребра в 2 цвета, пусть это будут красный и синий). Тогда нам нужно найти 2 непересекающихся цикла нечетной длины, окрашенных в один цвет.

Подсказка 2

А если мы перейдем к какому-то подграфу? Какой длины у нас могут быть циклы, если всего вершин 10? Быть может, в некотором подграфе мы гарантированно сможем найти цикл нечетной длины?

Подсказка 3

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

Подсказка 4

Попробуйте рассмотреть "углы" (например, ребра v₁v₂ и v₁v₃ образуют "угол" v₂v₁v₃) и оценить среди них количество покрашенных в один цвет (оба ребра одного цвета).

Подсказка 5

Отлично, теперь давайте посмотрим на исходный граф. Достаточно ли доказанного факта для решения задачи?

Подсказка 6

Нет, у нас может получиться 2 цикла разных цветов, а они должны быть одноцветны. Давайте рассмотрим граф, который образуют эти 2 цикла, пусть в первом цикле были вершины v₁, v₂ и v₃, а во втором - v₄, v₅ и v₆. Возможно, благодаря новым ребрам мы сможем получить желаемое. Давайте без ограничения общности попробуем оценить количество синих ребер в новом графе.

Подсказка 7

Попробуйте доказать, что мы сможем найти один красный и один синий "угол" в этом графе, образованные ребрами между множествами вершин {v₁, v₂, v₃} и {v₄, v₅, v₆}. Какой вывод мы можем сделать из существования этих "углов"?

Подсказка 8

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

Подсказка 9

Пусть у нас нашлись треугольники v₁-v₂-v₃ и v₃-v₄-v₅. Рассмотрите граф К₁₀ \ {v₁, v₂, v₃, v₄, v₅}. Это будет граф К₅. Чем он может нам помочь?

Подсказка 10

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

Подсказка 11

На самом деле, в графе К5 без одноцветного треугольника всегда найдутся 2 непересекающихся цикла одного цвета и длины 5, теперь надо доказать это в общем виде, и задача будет решена.

Подсказка 12

Посмотрите на какую-нибудь вершину и ребра, которые из нее выходят. Можно ли что-то сказать об их цветах?

Подсказка 13

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

Показать доказательство

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Если каждое ребро полного графа $K6$ (граф с $6$ -ю вершинами, каждая пара из которых соединена ребром) покрасить в один из двух цветов, то найдется треугольник (цикла длины $3),$ все стороны (ребра) которого имеют один цвет.

Доказательство. Пусть $v1,...,v6$ — вершины графа. Если ребра $vivj$ и $vivk$ окрашены в один цвет, то будем считать, что в этот цвет покрашен угол $vjvivk.$ Пусть $ri,bi$ — количества соответственно красных и синих ребер, выходящих из вершины $vi.$ Тогда $ri+ bi = 5$ (для всех $i$ ) и общее число окрашенных углов

6 6 ∑ (C2r+ C2b)≥ ∑ (C22 + C23)= 24 i=1 i i i=1

С другой стороны, в каждом «одноцветном» треугольнике все три угла должны быть окрашены в один цвет, а в каждом «неодноцветном» треугольнике есть только один окрашенный угол. Всего есть $3 C6 = 20$ треугольников и пусть $m$ из них одноцветны, тогда $3m+ (20 − m )≥24,$ откуда $m ≥2 >1,$ что завершает доказательство леммы 1.

___________________________________________________________________________________________________________________________________________________________________

Лемма 2. Если каждое ребро полного графа $K5$ (граф с $5$ -ю вершинами, каждая пара из которых соединена ребром) покрасить в один из двух цветов, и в этом графе нет одноцветного треугольника (цикла длины $3,$ все ребра которого окрашены в один цвет), то в этом графе есть два непересекающихся (не имеющих общих ребер) цикла, каждый из которых окрашен в один цвет и имеет длину $5.$

Доказательство. Пусть $v1,v2,...,v5$ — вершины графа. Рассмотрим ребра $v1v2,v1v3,v1v4,v1v5$ — если три из них имеют один и тот же цвет, то найдется одноцветный треугольник, что противоречит условию: действительно, пусть $v1v2,v1v3,v1v4$ — красные, тогда все ребра $v2v3,v3v4,v4v2$ должны быть синими (иначе получим красный треугольник), но тогда мы имеем синий треугольник. Итак, из каждой вершины выходят по два красных и два синих ребра.

Рассмотрим граф, состоящий из $5$ вершин и только красных ребер — в таком графе степень каждой вершины равна $2,$ а значит, он либо является циклом длины $5,$ либо разбивается на меньшие циклы. Если разбить граф на $5$ вершинах степени $2$ на меньшие циклы, то либо получим цикл из $1$ вершины (в наших условиях это невозможно), либо одноцветный треугольник, что также исключено (см. выше). Итак, граф на красных ребрах — цикл длины $5,$ аналогичный вывод делаем для графа на синих ребрах. Лемма 2 доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к задаче: пусть $v1,v2,...,v10$ — вершины графа $K10$ и пусть $v1v2v3$ — одноцветный треугольник в нем (его существование следует из леммы $1).$ В графе $K10∖{v1,v2,v3}$ также есть одноцветный треугольник, т.к. количество его вершин не меньше $6$ (даже $7)$ — пусть это треугольник $v4v5v6.$ Если эти треугольники окрашены в один цвет, то решение завершено. Если же нет (допустим, $v1v2v3$ — синий, а $v4v5v6$ — красный), то рассмотрим ребра $vivj$ для $i=1,2,3,$ $j = 4,5,6$ — всего $9$ ребер и, согласно принципу Дирихле, среди них найдутся $5$ ребер одного цвета (без ограничения общности будем считать, что синего). Тогда для некоторого $k∈ {4,5,6}$ найдутся два синих ребра из тройки $v1vk,v2vk,v3vk,$ т.е. меем один синий и один красный треугольники с общей вершиной $vk.$

Итак, “угол” $v v v 1 23$ — синий, а “угол” $vv v 3 45$ — красный. Рассмотрим граф $K ∖{v ,v ,v,v,v }= K . 10 1 2 3 4 5 5$ Если в нем есть одноцветный треугольник, то решение завершено: берем его и соответствующий ему по цвету $v vv 12 3$ или $vv v . 34 5$ Если в $K 5$ нет одноцветного треугольника, то, согласно лемме $2,$ в ней найдутся два разноцветных цикла длины $5$ — в этом случае берем нужный из этих циклов в качетсве второго циклического маршрута. Доказательство утверждения задачи завершено.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#120779

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

(b) В ориентированном графе с $n$ вершинами нет ориентированных циклов. Докажите, что его вершины можно пронумеровать числами $1,2,...,n$ так, что любое ребро ведет от вершины с меньшим номером в вершину с большим номером.

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

Показать доказательство

(a) Предположим, что вершина $v$ принадлежит двум различным сильно связным графам $C1$ и $C2.$ Тогда для любых $u ∈C1$ и $w ∈C2$ существуют пути $u→ v,$ $v → w,$ $w → v$ и $v → u.$ Следовательно, $u$ и $w$ достижимы друг из друга, что означает $C1 ∪C2$ — сильно связный. Таким образом, если вершина лежит в нескольких разных компонентах сильной связности, то получаем противоречие с максимальностью.

(b) Докажем утверждение индукцией по числу вершин $n.$

База индукции: Для $n= 1$ утверждение очевидно — вершине присваивается номер $1.$

Индукционный переход: Предположим, что для любого ацикличного графа с $k≤ n$ вершинами утверждение верно. Рассмотрим граф с $n+ 1$ вершиной.

В ацикличном ориентированном графе существует вершина с нулевой входящей степенью (иначе есть цикл). Обозначим её $v.$ Удалим $v$ из графа. Оставшийся граф также ацикличен и содержит $n$ вершин. По предположению индукции, его вершины можно пронумеровать числами $1,2,...,n$ так, что все рёбра сохраняют порядок.

Вернём $v$ в граф и присвоим ей номер $n+ 1.$ Так как $v$ имела нулевую входящую степень, все рёбра из неё ведут к вершинам исходного графа. Но эти вершины уже пронумерованы числами $1,2,...,n,$ а $v$ имеет номер $n+ 1.$ Следовательно, любое ребро $v → u$ удовлетворяет условию $n+ 1> номер(u).$ Для остальных рёбер порядок сохранён по предположению индукции.

Таким образом, нумерация корректна для $n+ 1$ вершин.

(c) Рассмотрим граф компонент сильной связности (КСС), вершины это КСС, ребра это наличие ребра между КСС в исходном графе. Этот граф ацикличен, ведь иначе мы смогли бы увеличить КСС. Применим к нему пункт (b), присвоив КСС номера $1,2,...,k.$ Все рёбра между КСС направлены от меньшего номера к большему, а внутри КСС сохраняются.

Ошибка.
Попробуйте повторить позже

Задача 18#120780

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

Показать доказательство

Рассмотрим полный ориентированный граф. В таком графе для любой пары вершин $u$ и $v$ существует ровно одно направленное ребро: либо $u → v,$ либо $v → u.$

Если граф уже сильно связен, тогда утверждение тривиально выполняется.

Пусть граф не является сильно связным. Разобьём его на компоненты сильной связности (КСС) $C1,C2,...,Ck,$ где $k ≥2.$ Компоненты сильной связности образуют линейный порядок: для любых $Ci$ и $Cj$ либо все рёбра между ними направлены из $Ci$ в $Cj,$ либо из $Cj$ в $Ci.$

Пусть $C1 → C2 → ...→ Ck$ — порядок КСС. Рассмотрим компоненты $C1$ и $Ck.$ В исходном графе все рёбра направлены от $C1$ к $Ck.$ Изменим направление одного ребра $v → u,$ где $v ∈ Ck,$ $u ∈C1.$ Теперь появится путь из $Ck$ в $C1,$ что объединяет компоненты в одну КСС.

Для остальных компонент $C2,...,Ck−1 :$

— Из $C1$ можно достичь их через исходные рёбра.

— Из них можно достичь $Ck$ через изменённое ребро.

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

Ошибка.
Попробуйте повторить позже

Задача 19#120781

В стране $101$ город. Некоторые города соединены дорогами с односторонним движением, причём в каждый город входит $40$ дорог и из каждого города выходит $40$ дорог. Докажите, что из каждого города можно добраться до любого другого, проехав не более чем по трём дорогам.

Показать доказательство

Рассмотрим произвольные города $A$ и $B.$ Разделим все города на три группы: $X$ — $40$ городов, в которые ведут дороги из $A.$ $Y$ — $40$ городов, из которых есть дороги в $B$ (не включая сам $B).$ Если $A$ лежит в $Y$ или $B$ в $X,$ то можно добраться по одной дороге. Если $A$ пересекается с $B,$ то по двум. Если они не пересекаются, то выделим оставшиеся $19$ городов в группу $Z.$ Из $X$ выходит $40⋅40$ стрелок, из них не более $40⋅39 2$ лежат полностью в $X$ и не более $19⋅40$ ведут в $Z.$ Тогда найдется хотя бы

( 39 ) 40⋅ 40− -2 − 19 = 60

стрелок ведущих из $X$ в $Y$ или $B.$

Ошибка.
Попробуйте повторить позже

Задача 20#120783

(a) Докажите, что в полном ориентированном графе есть гамильтонов путь;

(b) Докажите, что в сильно связном полном ориентированном графе любая вершина принадлежит циклу длины $3;$

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

Показать доказательство

(a) Индукция по числу вершин $n.$

База: Для $n =2$ путь существует тривиально.

Переход: Пусть для турнира с $n$ вершинами существует гамильтонов путь $v1 → v2 → ...→ vn.$ Добавим вершину $vn+1.$ Если $vn+1 → v1,$ новый путь: $vn+1 → v1 → ...→ vn.$ Если $vn → vn+1,$ новый путь: $v1 → ...→ vn → vn+1.$ Иначе найдётся первый $k$ такой, что $vk → vn+1,vn+1 → vk+1,.$ Вставим $vn+1$ между $vk$ и $vk+1.$ Получаем гамильтонов путь для $n +1.$

(b) Пусть $v$ — произвольная вершина. Рассмотрим её соседей:

$+ N (v)$ — вершины, в которые ведут рёбра из $v,$
$N −(v)$ — вершины, из которых ведут рёбра в $v.$

Так как граф сильно связен, $N+ (v)⁄= ∅$ и $N −(v)⁄=∅.$ Если существует ребро $u → w$ для $u ∈N −(v),$ $w∈ N+ (v),$ то цикл: $v → w→ u → v.$ Иначе все рёбра между $N −(v)$ и $N+ (v)$ направлены из $N+(v)$ в $N− (v).$ Но тогда граф не сильно связен, так как нельзя добраться из $N+(v)$ в $N −(v).$ Противоречие.

(c) Рассмотрим максимальный цикл $C = v1 → v2 → ...→ v → v1. k$ Если он содержит все вершины, то он гамильтонов, пусть это не так. Рассмотрим вершину $w,$ не лежащую в этом цикле. Если найдется пара стрелок вида $w→ v ,v → w, i i+1modk$ то вершину $w$ можно добавить в цикл, противоречие, цикл $C$ — максимальный. Значит все стрелки направленны, либо от вершины $w$ к $C,$ либо наоборот. Не умаляя общности стрелки идут в $w.$ Но граф сильно связен, значит от $w$ есть путь до $C,$ обозначим его за $P$ и пусть он кончается в вершине $vi+1,$ тогда цикл снова можно удлинить заменив стрелку $vi → vi+1$ на путь из стрелок $P vi → w−→ vi+1,$ противоречие.

(d) Пусть $G$ — сильно связный полный ориентированный граф с гамильтоновым циклом $C = v1 → v2 → ...→ vn → v1.$ Если есть хотя бы одна стрелка вида $vi → vi+2,$ то можно удалить вершину $vi+1.$ Пусть все стрелки такого вида ориентированны $vi+2 → vi.$ Они тогда образуют цикл, проход по которому, эквивалентен проходу по стрелке $vi → vi+2.$

$PIC$

Если цикл нечетный, тогда подойдет путь вида $vi → vi−2 → vi−1 → vi−3 → ...→ vi+2$ (нумерация по модулю $n$ ). Например для пяти: вместо прохода по стрелке $v3 → v5$ пройдем путем: $v3 → v1 → v2 → v5.$

Если цикл четный, то путь выглядит просто $vi → vi−2 → vi−4 → vi−6 → ...→ vi+2.$

В обоих случаях можно удалить вершину $vi$ без потери связности.

Следующая подтема