Высокая сложность — Страница 3 — Задачи на Графы

Задача 078

01.01.2025 от

В государстве 2018 городов, каждые два соединены либо автобусным, либо железнодорожным маршрутом. Регион — это любое непустое множество, состоящее не более, чем из 1009 городов. Автобусная мобильность региона определяется как отношение числа автобусных маршрутов, идущих из городов региона в города вне региона, к количеству городов в регионе. Железнодорожная мобильность региона определяется аналогично. Пусть $A$ — наименьшая из автобусных мобильностей регионов государства, а $B$ — наименьшая из их железнодорожных мобильностей. Какое наименьшее значение может принимать число $A+B$ ?

Подсказка

Пусть минимум автобусной мобильности дает регион $M$ , а железнодорожной — регион $N$ . Пусть $X=M \cap N, Y=M \backslash X, Z=N \backslash X$ , а $T$ — совокупность всех городов, не входящих ни в $M$ , ни в $N$ .

Пусть количества городов в $X, Y, Z$ и $T$ равны соответственно $a, b, c$ и $d$ . Все дороги, ведущие из $T$ в $X$ и из $Y$ в $Z$ , учитываются при подсчете либо числа автобусных маршрутов, ведущих из $M$ наружу, либо числа железнодорожных маршрутов, ведущих из $N$ наружу. Поэтому в совокупности таких маршрутов не меньше, чем $a d+b c$ , откуда $A+B \geq(a d+b c) / 1009$ , так как по условию в $M$ и $N$ не больше, чем по 1009 городов.

Решение

Ответ. 1.

Решение: Оченка. Пусть минимум автобусной мобильности дает регион $M$ , а железнодорожной — регион $N$ . Пусть $X=M \cap N, Y=M \backslash X, Z=N \backslash X$ , а $T$ — совокупность всех городов, не входящих ни в $M$ , ни в $N$ .

Если ни один из сомножителей $a, b, c$ и $d$ не равен 0 , то $a d+b c \geq(a+d-1)+(b+c-1)=2016$ , откуда $A+B \geq 2016 / 1009>1$ .

Пусть $c=0$ . Тогда во множестве $N$ а элементов, откуда $a \neq 0$ . При этом $a+b+d=2018$ , откуда $d \geq 1009$ и $A+B \geq(a d+b c) / 1009 \geq 1$ . Случай $b=0$ аналогичен.

Пусть, наконец, $b c \neq 0$ , но $a d=0$ . Если $a \neq 0$ , то $d=0$ , откуда $2018=a+b+c<2 a+b+c=(a+b)+(a+c) \leq 2018$ , противоречие. Итак, $a=0$ . Значит, любой из $b c$ маршрутов между $Y$ и $Z$ учитывается в одной из мобильностей с коэффициентом, не меньшим $\frac{1}{\max (b, c)}$ , поэтому $A+B \geq \frac{b c}{\max (b, c)}=\min (b, c) \geq 1$ .

Пример. Пусть город $X$ связан с остальными только железнодорожными маршрутами, а город $Y$ со всеми остальными, кроме $X$ , связан только автобусными маршрутами. Тогда автобусная мобильность города $X$ равна 0 , а железнодорожная мобильность города $Y$ равна 1.

Задача 083

01.01.2025 от

Степени всех вершин графа $G$ меньше $\frac{3 n}{2}-1$ (где $n>2$ ), причем среди любых $n+1$ вершин есть две несмежных. Назовем блоком множество из $n$ попарно смежных вершин графа $G$ . Известно, что любые два блока имеют общую вершину. Докажите, что все блоки имеют общую вершину.

Подсказка

Лемма 1. (В.Л. Дольников). В графе $2 n-1$ вершин. Оказалось, что после выкидывания любой вершины графа найдется полный подграф с $n$ вершинами. Тогда в исходном графе найдется полный подграф с $n+1$ вершиной.

Лемма 2. Пусть $L$ — пересечение нескольких блоков графа $G$ , причем $L$ непусто. Тогда $L$ содержит не менее $n-k-1$ вершин.

Решение

Доказательство. Пусть утверждение леммы неверно. Будем считать $n$ наименьшим натуральным числом, для которого существует граф, не удовлетворяющий условию задачи. Рассмотрим граф $H$ , дополнительный к графу из условия. Рассмотрим любой пустой подграф графа $H$ с $n$ вершинами, множество его вершин обозначим через $X$ , а множество остальных вершин через $Y$ . Назовем подмножество $Y$ плохим, если количество вершин в нем больше количества вершин в $X$ , смежных хотя бы с одной вершиной из этого подмножества. Обозначим через $A$ максимальное плохое подмножество (оно может быть и пустым), пусть оно содержит $k$ вершин, тогда в $Y A$ нет плохих подмножеств, поэтому, в силу леммы Холла, каждой вершине $Y A$ можно сопоставить смежную с ней вершину $X$ таким образом, чтобы все эти вершины были различны и не смежны с вершинами из Y $\backslash$ A. Множество не сопоставленных вершин $X$ обозначим через $B$ . Рассмотрим граф $H^{\prime}$ , образованный вершинами $A \cup B$ и ребрами графа $H$ , соединяющими эти вершины. Заметим, что при выкидывании любой вершины $H^{\prime}$ в графе $H$ должен был найтись пустой подграф с $n$ вершинами, но в него могло входить не более, чем $n-k-1$ вершина из ( $X \cup Y$ ) $\backslash(A \cup B)$ , следовательно, остальные $k+1$ вершин должны быть из $A \cup B$ , поэтому в $H^{\prime}$ после выкидывания любой вершины найдется пустой подграф с $k+1$ вершинами, но тогда, в силу минимальности $n$ либо в $H^{\prime}$ найдется пустой подграф с $k+2$ вершинами, либо $k=n$ . В первом случае, добавляя к вершинам этого подграфа вершины из $X \backslash B$ , получим пустой подграф с $n+1$ вершинами, во втором — выкинем вершину из $X$ , несмежную ни с одной вершиной $Y$ , найдем пустой подграф $H$ с $n$ вершинами и добавим к нему эту вершину, получим пустой подграф $H$ с $n+1$ вершинами. Полученное противоречие доказывает утверждение леммы.

Обозначим через $k$ разность максимальной степени графа и $n$ . Из условия следует, что $2 k+2 \leq n$ .

Доказательство. Пусть $T$ — объединение всех блоков, содержащих $L$ . Тогда $|T| \leq n+k+1$ , поскольку любая вершина из $L$ смежна с любой вершиной из $T$ . Ясно, что любой блок, содержащий $L$ , имеет не менее $n-|L|$ вершин в $T L L$ . Пусть $|L|<n-k-1$ . Заметим, что при выкидывании любой вершины из $T L$ найдется блок, содержащий $L$ , но не содержащий выкинутой вершины (поскольку $L$ — пересечение всех блоков, содержащих $L$ ). Но в $T \backslash L$ нет подграфов, содержащих более $n-|L|$ вершин (иначе объединение такого подграфа с $L$ будет полным подграфом графа $G$ , содержащим более $n$ вершин). Тогда $T L$ содержит не менее $2(n-|L|)$ вершин в силу леммы 1 . Следовательно, $2(n-|L|) \leq|\mathrm{T} \backslash \mathrm{L}| \leq n+k+1-|L|$ , откуда $|L| \geq n-k-1$ . Лемма доказана.

Завершение доказательства. Рассмотрим любой блок. Назовем его Н. Рассмотрим пересечение всех блоков, имеющих непустое пересечение с $H$ (включая $H$ ). Будем добавлять эти блоки по одному и следить за пересечением. До тех пор, пока оно непусто, оно содержит не менее $n-k-1$ вершин, в силу леммы 2 . Но тогда следующий добавляемый подграф должен иметь не менее $n-k-1$ общих вершин с $H$ (в силу леммы 2 ), но $2(n-k-1)>n$ (по условию $n>2(k+1)$ ), следовательно новый блок имеет непустое пересечение с пересечением старых.

Задача 084

01.01.2025 от

Ребра полного графа с $n$ вершинами покрашены в несколько цветов таким образом, что каждый цвет встречается не более $n-2$ раз. Докажите, что есть три вершины, все ребра между которыми покрашены в различные цвета.

Подсказка

Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина $A$ , и она соединена ребрами цвета 1 с вершинами $B_{1}, \ldots B_{k}$ . Поскольку $k \leq n-1$ , то остались еще вершины $C_{k+1}, \ldots C_{n-1}$ , каждая из которых соединена с вершиной $A$ ребром какого-то другого цвета.

Решение

Решение 1. Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина $A$ , и она соединена ребрами цвета 1 с вершинами $B_{1}, \ldots B_{k}$ . Поскольку $k \leq n-1$ , то остались еще вершины $C_{k+1}, \ldots C_{n-1}$ , каждая из которых соединена с вершиной $A$ ребром какого-то другого цвета. Рассмотрим вершину $C_{i}$ , пусть она соединена с $A$ ребром цвета $i$ . Тогда $C_{i}$ должна быть соединена с каждой из вершин $B_{1}, \ldots B_{k}$ либо ребром цвета 1 , либо ребром цвета $i$ (иначе будет треугольник с разноцветными сторонами). Если все эти $k$ ребер окрашены в цвет $i$ , то всего из вершины $C_{i}$ выходит $k+1$ ребро цвета $i$ , что противоречит выбору вершины $A$ и цвета 1 . Следовательно, хотя бы одно из этих ребер окрашено в цвет 1. Таким образом, из каждой вершины $C_{k+1}, \ldots C_{n-1}$ выходит хотя бы одно ребро цвета 1 , и всего мы имеем $n-1$ ребро цвета 1 , что противоречит условию. Следовательно, обязательно найдутся три вершины, все три ребра между которыми покрашены в разные цвета.

Решение 2. Пусть в любом треугольнике есть два одноцветных ребра. Так как ребер любого цвета не более $n-2$ , то они образуют несвязный граф на данных нам $n$ вершинах. Для каждого цвета такой граф распадается хотя бы на две компоненты связности. Среди всех таких компонент связности (для всех цветов) найдем наибольшую по количеству вершин компоненты связности $F$ (пусть ее ребра окрашены в цвет 1). Очевидно, существует вершина $A$ , не вошедшая в $F$ . Рассмотрим любую вершину $B_{1}$ из $F$ , она соединена с $B$ ребром не цвета 1 , пусть это ребро цвета 2 . Если вершина $B_{2}$ из $F$ соединена с $B_{1}$ ребром цвета 1 , то $A$ также соединена с $B$ ребром цвета 2 (иначе будет треугольник $A B_{1} B_{2}$ будет иметь разноцветными ребрами). Такими же рассуждениями мы получим, что $A$ соединена со всеми вершинами компоненты связности $F$ ребрами цвета 2 , но тогда существует компонента связности цвета 2 , содержащая все вершины из $F$ и вершину $A$ . Противоречие с максимальностью компоненты связности $F$ .

Задача 086

01.01.2025 от

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

Подсказка

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

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

Решение

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

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

База — простые циклы. Пусть в простом цикле $A_{1} A_{2} \ldots A_{n}$ как-то расставлены стрелки на рёбрах и турист смог сделать ход, пойдя из $A_{1}$ в $A_{2}$ . Вася будет разворачивать стрелки перед ним. Поэтому турист не сможет идти в обратную сторону. Допустим, турист смог дойти до $A_{1}$ . Тогда перед ним разворачивают стрелку, и ему некуда идти. Петя проиграл.

Шаг индукции. Граф не является простым циклом. Выберем в нём цикл С минимальной длины. Ясно, что $C$ — простой и не содержит ребёр внутри себя. Поэтому есть вершины вне $C$ . Выберем из них вершину $V$ с максимальным расстоянием до $C$ . Обозначим граф без $V$ буквой $G$ . Ясно, что $G$ связен и содержит цикл.

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

Задача 088

01.01.2025 от

У Пети есть колода из 36 карт ( 4 масти по 9 карт в каждой). Он выбирает из неё половину карт (какие хочет) и отдаёт Васе, а вторую половину оставляет себе. Далее каждым ходом игроки по очереди выкладывают на стол по одной карте (по своему выбору, в открытом виде); начинает Петя. Если в ответ на ход Пети Вася смог выложить карту той же масти или того же достоинства, Вася зарабатывает 1 очко. Какое наибольшее количество очков он может гарантированно заработать?

Подсказка

Мы воспользуемся известной леммой Холла о сватовстве.
Лемма. Пусть есть $n$ юношей. Известно, что для каждой группы из $k$ юношей ( $k=1,2$ , $\ldots, n$ ) имеется по крайней мере $k$ девушек, имеющих знакомых среди этой группы юношей. Тогда каждого юношу можно женить на знакомой девушке.

Решение

Доказательство и обсуждение см., например, в статьях: М. Большаков, «Паросочетания и транспортные сети («Квант» №4 за 1970 год); А. Романов, «Задачи и теоремы о представителях» («Квант» №1 за 2015 год); М. Шевцова, «Многократная лемма Холла в задачах про мудрецов» («Квант» № 7 за 2019 год)

В терминах решения 1 объявим чёрные клетки юношами (при этом $n=18$ ), белые девушками, а знакомыми — клетки, находящиеся в одном ряду. Мы докажем, что для каждой группы из $k$ юношей ( $k=4,2, \ldots, 18$ ) имеется по крайней мере $k-3$ девушки, имеющих знакомых среди этой группы юношей. Добавив трёх виртуальных девушек, знакомых со всеми юношами, мы окажемся в условиях леммы Холла. Переженив всех юношей и отбросив не более чем троих, которым достались виртуальные девушки, получим не менее 15 хороших пар.

Пусть есть группа $X$ из $k$ юношей (чёрных клеток). Переставим столбцы, их содержащие, влево, а строки — вниз. Пересечение этих строк и столбцов — прямоугольник площади $S_{1}$ — содержит $X$ , а дополнение к их объединению — прямоугольник площади $S_{2}-$ содержит всех незнакомых с ними девушек. Значит, $k \leq \min \left(S_{1}, 18\right)$ , а количество знакомых с ними девушек не меньше $18-\min \left(S_{2}, 18\right)$ .

Нам достаточно доказать, что $18-\min \left(S_{2}, 18\right) \geq \min \left(S_{1}, 18\right)-3$ , т.е. что $\min \left(S_{1}, 18\right)+\min \left(S_{2}, 18\right) \leq 21$ .

Выражение $F=\min \left(S_{1}, 18\right)+\min \left(S_{2}, 18\right)$ симметрично, поэтому достаточно рассмотреть случай, когда общая вершина $A$ построенных прямоугольников лежит в верхней половине доски. Тогда $S_{2} \leq 18$ .

Отбросим очевидный случай, когда $A$ лежит на границе доски (тогда $S_{1}=0$ или $S_{2}=0$ ). Если $S_{1}<S_{2}$ , то можно сдвинуть $A$ вправо, чтобы стало $S_{1}=18$ (поскольку 18 делится как на 2 , так и на 3 ), при этом $F=S_{1}+S_{2}$ не уменьшится. Если $S_{1}>S_{2}$ , то можно сдвинуть $A$ влево, чтобы стало $S_{1}=18$ , при этом $F=18+S_{2}$ увеличится.

Остался единственный случай $S_{1}=18, S_{2}=3$ , а в нём неравенство выполнено.

Задача 098

01.01.2025 от

В графе на 20 вершинах степень каждой вершины не более 3 . Какое наибольшее количество циклов длины 4 может быть в этом графе?

Подсказка

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

Решение

Ответ: 27. Решение. Напомним, что через $K_{3,3}$ обозначается полный двудольный граф на 6 вершинах, то есть граф, три вершины которого можно покрасить в один цвет, а три — в другой так, что любые две одноцветные вершины будут соединены ребром, а любые две разноцветные — нет. В графе $K_{3,3} 9$ циклов длины 4, потому что цвета вершин в цикле чередуются, и по две вершины каждого цвета в $K_{3,3}$ можно выбрать $3 \times 3=9$ способами. Отсюда получается пример на 27 циклов: достаточно взять три графа $K_{3,3}$ , а из двух оставшихся вершин рёбер не проводить.

Покажем, что больше 27 циклов длины 4 в нашем графе не бывает Возьмём любое его ребро. Пусть оно входит в какой-либо цикл длины 4. Выбросим из этого цикла ребро, не имеющее с нашим общих вершин. Получится маршрут длины 3, где взятое нами ребро является средним из трёх, и цикл по этому маршруту восстанавливается однозначно. Но каждый из двух концов взятого нами ребра принадлежит, кроме него, максимум ещё двум рёбрам. Поэтому в нашем графе есть максимум $2 \times 2=4$ маршрута длины 3 , где взятое нами ребро является средним из трёх. Таким образом, через каждое ребро нашего графа проходит не более 4 циклов длины 4.

Назовём ребро хорошим, если оно входит ровно в 4 цикла длины 4 . Покажем, что если в компоненте связности нашего графа есть хотя бы одно хорошее ребро, то эта компонента имеет вид $K_{3,3}$ . В самом деле, в этом случае из каждой вершины нашего ребра должно выходить ещё 2 ребра, и каждый из вторых концов рёбер, выходящих из одной вершины, должен соединяться с каждым из вторых концов рёбер, выходящих из другой вершины. Получается $K_{3,3}$ , а наружу рёбра из него не ведут, потому что степень каждой вершины $K_{3,3}$ и так уже равна 3.

Пусть в нашем графе ровно $k \leq 2$ компонент связности вида $K_{3,3}$ . Тогда в нём $20-6 k$ вершин, входящих в «плохие» компоненты, где через каждое ребро проходит не более 3 циклов длины 4. В этих компонентах не более $3 \times(20-6 k) / 2=30-9 k$ рёбер и, стало быть, не более $3 \times(30-9 k) / 4=(90-27 k) / 4$ циклов длины 4, а всего в графе этих циклов не больше, чем $9 k+(90-27 k) / 4=22,5+9 k / 4 \leq 22,5+18 / 4=27$ . Если же в графе 3 компоненты связности вида $K_{3,3}$ , то в этих компонентах 27 циклов длины 4 , а две оставшиеся вершины, не будучи связанными с остальными 18 -ю, новых циклов длины 4 добавить не могут. Итак, циклов длины 4 у нас всегда не более 27.