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

Задача 037

01.01.2025 от

Каждые два города страны Гельбии соединены односторонним авиарейсом. Региональные бароны превратили страну в федерацию двух республик с общей столицей (каждый город, кроме столицы, принадлежит ровно одной из республик, а столица — обеим). Министерство путей сообщения посчитало количество $N$ маршрутов, проходящих по каждому городу всей страны по одному разу (не возвращающихся в исходный город), а также аналогичные количества $N_{1}$ и $N_{2}$ для каждой из республик. Докажите, что $N \geq N_{1} N_{2}$ .

Подсказка

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

Решение

Построим ориентированный граф, вершины которого соответствуют городам, а рёбра — дорогам. Пусть вершина $w$ соответствует столице, $A$ и $B$ — графы, соответствующие республикам. Сначала сформулируем несложную лемму.

Пусть $P$ и $Q$ — два непересекащихся пути в полном ориентированном графе Т. Тогда существует путь $R$ на вершинах этих двух путей, в котором все вершины пути $P$ следуют в порядке пути $P$ , а все вершины пути $Q$ следуют в порядке пути $Q$ . Этот факт нетрудно доказать индукцией по длине пути $Q$ , вставляя по очереди его вершины в путь $P$ . Отметим, что лемма верна и для случая, когда один из путей $P$ и $Q$ или они оба — пустые (из 0 вершин). Назовём путь $R$ из леммы склейкой путей $P$ и $Q$ .

Рассмотрим любые гамильтоновы пути $P$ графа $A$ и $Q$ графа $B$ . Эти пути, очевидно, имеют вид $P=P_{1} w P_{2}$ и $Q=Q_{1} w Q_{2}$ (возможно, какие-то из участков $P_{1}, P_{2}, Q_{1}$ и $Q_{2}$ — пустые). По лемме существует путь $R_{1}$ — склейка $P_{1}$ и $Q_{1}$ и путь $R_{2}$ — склейка $P_{2}$ и $Q_{2}$ . Отметим, что если путь $R_{1}$ непустой, то он кончается либо последней вершиной пути $P_{1}$ , либо последней вершиной пути $Q_{1}$ , то есть, из последней вершины пути $R_{1}$ выходит ребро в $w$ . Аналогично, либо путь $R_{2}$ — пустой, либо из $w$ выходит стрелка в первую вершину пути $R_{2}$ . Тогда $R=R_{1} w R_{2}$ — гамильтонов путь в графе $T$ , в котором вершины подграфа $A$ следуют в порядке пути $P$ , а вершины подграфа $B$ следуют в порядке пути $Q$ . Каждой паре гамильтоновых путей ( $P, Q$ ) очевидно, соответствует свой путь $R$ .

Задача 038

01.01.2025 от

Город Сугробск представляет собой квадрат со стороной $100 n$ метров, разбитый прямыми улицами на $n^{2}$ одинаковых кварталов ( $n$ — чётное натуральное число, большее 2). На каждой из $2 n+2$ улиц, идущих по сторонам кварталов от края до края города, введено одностороннее движение. На соседних параллельных улицах движение направлено в разные стороны. В одном из углов города находится автопарк; обе выходящие из этого угла улицы направлены от автопарка. Снегоуборочная машина выезжает из автопарка и начинает убирать снег. Чтобы не портить дорожное покрытие, по уже убранным участкам (кроме перекрестков) машина не ездит. В конце смены машина должна прибыть в противоположный угол города. Какое наибольшее расстояние она может проехать?

Подсказка

Докажите, что наименьшее количество не пройденных отрезков есть $4 n-4$ .

Решение

Ответ. $100\left(2 n^{2}-2 n+4\right)$ .

Решение: Будем считать, что машина едет из левого нижнего в правый верхний угол, а все стороны маленьких квадратов равны 1 . Всего горизонтальных единичных отрезков $n(n+1)$ , тогда всего единичных отрезков $2 n(n+1)$ . Докажем, что наименьшее количество не пройденных отрезков есть $4 n-4$ . Тогда наибольшее количество пройденных отрезков не более $2 n(n+1)-(4 n-4)=2 n^{2}-2 n+4$ . Введем прямоугольную систему координат: левый нижний угол будет иметь координату $(0,0)$ , а верхний правый — ( $n, n$ ). Рассмотрим прямые вида $x+y=k+1 / 2$ , где $k$ целое число от 0 до $2 n-1$ . Очевидно, что ее пересекает поровну вертикальных и горизонтальных отрезков, ввиду симметрии относительно $x=y$ . Так как начальная и конечная точка нашего маршрута находятся по разные стороны от этой прямой, то маршрут пересечет ее нечетное число раз, а, следовательно, один из отрезков будет не пройденным. Итого уже не пройденных отрезков будет 2n. Рассмотрим прямую $x+y=k+1 / 2$ где $k-$ четное дислот че ниных отрезка, пескащих ра сли ренлу. По условию, если аетно, то оба дин ных отрезка ориентированы из ооласти старта в ооласть финиша, а если $a$ — нечетно, то наооорот. Всего отрезков первого типа $-k+2$ , а отрезков второго типа $-k$ . Заметим, что пройденных отрезков первого типа должно быть ровно на один больше, чем пройденных отрезков второго типа. Однако, точки $(k, 0)$ и $(0, k)$ лежат на границе, поэтому в них входит ровно один отрезок, следовательно, для каждой этой точки, один из выходящих отрезков будет не пройденным. Остается не более $k$ отрезков первого типа, и не более $k-1$ отрезков второго типа. Т.е. эта прямая пересекает хотя бы три не пройденных отрезка. Таких прямых $(n-2) / 2$ , и они дают еще $n-2$ не пройденных отрезков. Аналогично, рассматривая прямую $x+y=k-1 / 2$ , где $k$ — четное число от $n+1$ до $2 n-2$ , найдем еще $n-2$ не пройденных отрезков. Всего не пройденных отрезков будет хотя бы $2 n+2(n-2)=4 n-4$ . Оценка доказана.

Приведем пример. Удалим все ребра вида ( $n, 2 k-1)-(n, 2 k)$ при $1 \leq k \leq n / 2$ и вида ( $2 k, 0)-(2 k+1,0)$ при $1 \leq k \leq(n-2) / 2$ . Всего удалено $n-1$ ребро. Далее удалим пути ( $2 k, n)-(2 k, n-1)-(2 k+1, n-1)-(2 k+1, n)$ при $1 \leq k \leq(n-2) / 2$ , а также пути $(0,2 k-1)-(1,2 k-1)-(1,2 k)-(0,2 k)$ при $2 \leq k \leq(n-2) / 2$ . Итого в этих путях $3 n-9$ ребер. Наконец, удалим пути $(0,0)-(0,1),(1,0)-(1,2)-(0,2)$ и $(0, n-1)-(1, n-1)-(1, n)$ . Всего удалено $4 n-4$ ребра. Все не граничные вершины имели степень входяших и исходяших ребер ровно по два, поэтому после удаления они остались равными. Легко проверить, что у всех вершин, лежащих строго на стороне квалрата стапо по одному входнему и исхолящему ребру У начальной и конечной вершины стало по одному исходящему и одному входящему ребру. Пример построен.

Задача 039

01.01.2025 от

Пусть $G$ — связный граф, имеющий хотя бы три вершины. Определим $G^{3}$ как граф на тех же вершинах, в котором соединены ребрами вершины, находящиеся в $G$ на расстоянии не более трех. Докажите, что в графе $G^{3}$ есть гамильтонов цикл.

Подсказка

Для начала рассмотрите вершины, у которых много соседних висячих вершин.

Решение

Разумеется, достаточно доказать теорему для случая, когда $G$ — дерево. Длиной ребра в графе $G^{3}$ мы назовем расстояние между его концами в исходном графе $G$ . Так, у графа $G^{3}$ бывают рёбра длин 1,2 и 3 . Доказательство будет индукцией по количеству вершин. База для дерева из трех вершин очевидна. Пусть для всех деревьев, имеющих меньше вершин, чем $G$ (и хотя бы три вершины), теорема уже доказана. Рассмотрим два случая.
а) В дереве существует вершина w, смежная хотя бы с двумя висячими вершинами. Пусть $v_{1}$ и $v_{2}$ — две висячие вершины, смежные с $w$ и $T=G-v_{2}$ . Можно считать, что $v(T) \geq 3$ , иначе утверждение для графа $G$ доказано в базе. В гамильтоновом цикле $Z$ графа $T^{3}$ есть участок $u v_{1} u^{\prime}$ , который, очевидно, можно заменить на $u v_{1} v_{2} u^{\prime}$ и получить гамильтонов цикл графа $G^{3}$ .
б) Любая невисячая вершина смежна не более, чем с одной висячей.

Рассмотрим вершину $w$ степени хотя бы 3 , к которой присоединён путь $v_{1} \ldots v_{k}$ , заканчивающийся висячей вершиной $v_{k}$ (возможно, $k=1$ ) и дерево $T=G-\left\{v_{1}, \ldots, v_{k}\right\}$ . Понятно, что $v(T) \geq 3$ , в графе $T^{3}$ существует гамильтонов цикл $Z$ , а в цикле $Z$ есть ребро $u u^{\prime}$ , соединяющее две разных компоненты связности графа $T-w$ . Так как длина ребра $u u^{\prime}$ не более трёх а единственный $u u^{\prime}-$ путь в дереве $T$ проходит через $w$ , то хотя бы одна из вершин $u$ и $u^{\prime}$ смежна в $T$ с вершиной $w$ . Пусть $u w \in E(T)$ . При $k=1$ заменим ребро $u u^{\prime}$ на $u v_{1} u^{\prime}$ . Если $k \geq 2$ , заменим $u u^{\prime}$ на $u v_{2} \ldots v_{1} u^{\prime}$ (вставим между $u$ и $u^{\prime}$ сначала $v_{2}$ , затем все вершины с четными номерами, большими двух в порядке возрастания номеров, затем все вершины с нечетными номерами, большими одного в порядке убывания номеров, затем $v_{1}$ ). Легко видеть, что в полученном гамильтоновом цикле графа $G^{3}$ длины всех рёбер не более трёх.

Задача 047

01.01.2025 от

Вершины графа разбиты на три множества $A, B, C$ так, что вершины из $A$ не связаны рёбрами с вершинами из $C$ . Известно, что $A \cup B$ можно правильно раскрасить в $k$ цветов, а $B \cup C$ — в $n$ цветов. В какое минимальное количество цветов можно с гарантией правильно раскрасить все вершины этого графа?

Подсказка

Покажите, что в $k+n-1$ цвет правильно раскрасить все вершины можно всегда.

Решение

Ответ. В $k+n-1$ цвет.

Решение: Покажем, что в $k+n-1$ цвет правильно раскрасить все вершины можно всегда. Раскрасим $B \cup C$ в $n$ цветов, назовём один из этих цветов первым, и пусть $D$ — совокупность всех вершин из $B$ , покрашенных в первый цвет. Теперь раскрасим $A \cup D$ в $k$ цветов, использовав в качестве одного из них первый цвет (а остальные $k-1$ цветов взяв отличными от уже использованных $n$ цветов). У вершин, не входящих в $A \cup D$ , сохраним прежнюю раскраску. Поскольку никакие вершины из $A \cup D$ не связаны рёбрами с вершинами из $C$ , покрашенными в первый цвет (из $D$ — в силу правильности раскраски $B \cup C$ в $n$ цветов, из $A$ — по условию), получится правильная раскраска графа в $k+n-1$ цвет.

Теперь покажем, что меньшего числа цветов может и не хватить. Расположим $k n$ точек в виде прямоугольника из $n$ строк и $k$ столбцов. Примем это множество за $B$ . Снизу добавим нулевую строку из $k$ точек, примем ее за $A$ , слева нулевой столбец, примем его за $C$ . Ребрами в $B$ соединим любые две точки, не лежащие ни в одной строке, ни в одном столбце. В $A$ соединим рёбрами каждые две точки, в $C$ — тоже. Кроме того, соединим рёбрами каждую точку из $A$ со всеми точками из $B$ , не лежащими с ней в одном столбце, и каждую точку из $C$ со всеми точками из $B$ , не лежащими с ней в одной строке. Очевидны правильные раскраски $A \cup B$ в $k$ цветов (по столбцам) и $C \cup B$ в $n$ цветов (по строкам). Покажем, что полученный граф нельзя раскрасить меньше, чем в $k+n-1$ цвет. Допустим, есть правильная раскраска $A \cup B \cup C$ в $k+n-2$ цвета. Поскольку точки множества $A$ раскрашены в $k$ различных цветов, а точки множества $C$ — в $n$ различных цветов, то есть $m \geq 2$ цветов (назовём их общими), в которые покрашены точки обоих этих множеств. Отметим строки и столбцы, в которых находятся такие точки; на их пересечении находится $m^{2}$ точек множества $B$ . Заметим, что в каждый из $m$ общих цветов может быть покрашено не больше одной из этих $m^{2}$ точек, а именно, точка, стоящая на пересечении соответствующих столбца и строки. Стало быть, среди этих $m^{2}$ точек есть $m^{2}-m$ точек, раскрашенных в другие цвета. Это не могут быть общие цвета, но не могут быть и другие цвета, использованные при раскраске точек множеств $A$ и $C$ , потому что со всеми точками таких цветов точки из отмеченных строк и столбцов связаны рёбрами. Всего при раскраске точек из $A$ и $C$ было использовано $k+n-m$ цветов. Из упомянутых выше $m^{2}-m$ точек можно выбрать $m$ точек, никакие две из которых не лежат в одной строке или одном столбце. Каждые две из этих $m$ точек связаны ребром, поэтому они раскрашены не менее, чем в $m$ цветов. Получается, что всего использовано не менее, чем $k+n$ цветов. Противоречие.

Задача 059

01.01.2025 от

В стране $N$ городов. Некоторые пары городов соединены двусторонними авиарейсами, каждый рейс имеет цену, большую 1000 рублей, причём из любого города можно добраться до любого другого (возможно, с пересадками). Компания публикует сборник, в котором для каждой из $N(N-1) / 2$ пар городов указана минимальная цена, которую надо заплатить, чтобы добраться от одного из них до другого; в конце сборника указывается сумма всех этих $N(N-1) / 2$ чисел. В некоторый момент компания уменьшила стоимость одного из рейсов на 1000 рублей. Докажите, что итоговая сумма в новом сборнике будет отличаться от старой не более, чем на $250 N^{2}$ .

Подсказка

Обозначим два города, между которыми уменьшили стоимость рейса, через $X$ и $Y$ . Пусть $A$ — множество городов, из которых после уменьшения дешевле добраться до $X$ , чем до $Y$ , в том числе в множество $A$ входит сам город $X$ . Пусть $B$ множество городов, из которых добраться до $Y$ не дороже, чем до $X$ , в том числе в множество $B$ входит сам город $Y$ . Что будеь если при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ .

Решение

Пусть при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ . Тогда, если из $X$ сразу полететь в $V$ по пути наименьшей стоимости, мы заплатим меньшую цену за весь путь: ведь цена перелета между $X$ и $Y$ все равно осталась положительной, и хотя бы эту цену мы сэкономим. Аналогичны рассуждения для двух вершин из множества $B$ . Поэтому путь минимальной стоимости между двумя вершинами одного множества не содержит рейс из $X$ в $Y$ .

Обозначим количество городов в множестве $A$ через $a$ . Тогда в множестве $B$ всего $N-a$ городов. Стоимость самого дешевого пути между городами одного множества, как было показано выше, не уменьшилась. Значит, лишь между $a(N-a)$ парами городов из разных множеств стоимость самого дешевого пути могла уменьшиться. Это количество пар не больше $N^{2} / 4$ , по неравенству между средними арифметическим и геометрическим.

Новый самый дешевый путь между городами из разных множеств проходит по удешевленному ребру $X Y$ не более одного раза, а до удешевления стоимость такого же пути была не ниже стоимости самого дешевого пути между этими городами. Поэтому для каждой пары городов из разных множеств стоимость самого дешевого пути уменьшилась не более, чем на 1000. Значит, итоговая сумма будет отличаться от старой не более, чем на $250 N^{2}$ рублей.

Задача 060

01.01.2025 от

В стране несколько городов, один из которых — Москва. Некоторые пары городов соединены двусторонними дорогами. Мэр хочет обгединить Москву ещё с п городами в большую Москву так, чтобы (1) между любыми двумя городами большой Москвы можно было проехать по дорогам, не попадая в города вне неё, и (2) было ровно $k$ городов вне большой Москвы, соединённых хотя бы одной дорогой с большой Москвой. Докажите, что есть не более $C_{n+k}^{k}$ способов совершить такое обгединение.

Подсказка

Пронумеруем вершины, кроме Москвы, произвольным образом.
Будем красить города из большой Москвы в красный цвет, а их соседей в зелёный цвет. То есть мэру нужно покрасить $n$ городов в красный, а $k$ других городов в зелёный.

Теперь построим соответствие способу покраски способ расставить в ряд $k$ зелёных и $n$ красных символов (способов сделать это $C_{n+k}^{k}$ ). Для удобства сначала будем писать не просто символы, а номера городов, после чего забудем сами номера, оставив только строчку цветных символов.

Решение

На первом этапе алгоритма выпишем в возрастающем порядке номера городов, соседних с Москвой (все они покрашены!). При этом мы покрасим красные в розовый, а зелёные так и оставим зелёными. На очередном шаге будем брать строчку, брать в ней самый левый розовый номер $x$ , и записывать в конец строки номера всех его ещё не выписанных соседей (все они покрашены!) в порядке возрастания номеров, причём номера красных городов запишем розовым, а зелёных — зелёным. После чего поменяем цвет номера $x$ на красный.

Так как на каждом шаге количество красных номеров увеличивалось на 1 , то процесс закончится.
Докажем, что полученное отображение инъективно. Предположим, есть две покраски городов, дающие одну и ту же последовательность. Тогда существует символ, который соответствует разным номерам в раскрасках; рассмотрим самый левый такой символ. Пусть до него последовательности имели вид $a_{1} a_{2} \ldots a_{t} x$ и $a_{1} a_{2} \ldots a_{t} y$ . В каждой из раскрасок номера $x$ и $y$ появились как соседи красных вершин с выписанными ранее номерами. Но поскольку предыдущие символы совпадали, то должен был совпасть и номер на месте $t+1$ .

Задача 065

01.01.2025 от

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

Подсказка

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

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

Рассмотрим две вершины $A$ и $B$ , путь между которыми содержит наибольшее количество рёбер.

Решение

Ответ. При $k=1344$ . Решение. Введём граф городов и авиарейсов. Для начала приведём пример графа, в котором меньше чем 1344 стратегически значимыми вершинами не обойтись. Пусть в графе имеются вершины $A$ , а также $B_{k}, C_{k}$ и $D_{k}, k=1,2, \ldots, 672$ ; для каждого $k$ проведём рёбра между вершиной $A$ и $B_{k}, B_{k}$ и $C_{k}$ , $C_{k}$ и $D_{k}$ . Легко видеть, что этот граф связен. Поскольку вершина $D_{1}$ связана только с вершиной $C_{1}$ , то вершина $C_{1}$ должна быть объявлена стратегически значимой. Кроме того, применяя условие задачи для вершины $C_{1}$ получаем, что либо вершина $B_{1}$ , либо вершина $D_{1}$ должна быть объявлена стратегически значимой. Итак, из вершин $B_{1}, C_{1}, D_{1}$ хотя бы две вершины должны быть стратегически значимыми. Рассуждая аналогично для каждой тройки $B_{k}, C_{k}, D_{k}$ , получаем требуемое.

Докажем теперь, что 1344 стратегически значимыми вершинами можно обойтись. Очевидно, достаточно разобрать случай, когда граф — дерево (в произвольном связном графе можно выделить дерево, содержащее все его вершины; если $k$ стратегически значимых вершин будет достаточно для этого дерева, их будет достаточно и для исходного графа).

Рассмотрим две вершины $A$ и $B$ , путь между которыми содержит наибольшее количество рёбер. Пусть $X$ — последняя перед $B$ вершина на пути из $A$ в $B$ . Очевидно, $B$ соединена только с $X$ . Если $X$ соединена с какимито висячими вершинами, кроме $B$ , выделим $X$ и все смежные с ней висячие вершины, а стратегически значимыми среди них объявим $X$ и $B$ . Очевидно, удаление этих вершин не нарушит связности графа, и стратегически значимые составляют среди них не более $2 / 3$ .

Пусть $B$ — единственная висячая вершина, соединённая с $X$ . Рассмотрим последнюю вершину $Y$ на пути из $A$ в $X$ . Если все отличные от $B$ вершины, путь из которых в $A$ проходит через $Y$ , смежны с $Y$ , можно выделить эти вершины, $Y, X$ и $B$ , а стратегическими среди них объявить $X$ и $Y$ .

Наконец, разберём случай, когда путь из $A$ в $Y$ можно продолжить несколькими путями $Y X_{i} B_{i}$ длины 2 (путями большей длины продолжить не удастся в силу максимальности выбранного выше пути из $A$ в $B$ ). Пусть таких путей $k$ . Тогда нужно выделить все вершины этих путей и все висячие вершины, смежные с $Y$ , а стратегически значимыми объявить $Y$ и все $X_{i}$ . При этом из графа будет удалено не менее $2 k+1$ вершин, из которых $k+1$ стратегически значимых, а $\frac{k+1}{2 k+1} \leq \frac{2}{3}$ .

Будем продолжать эту деятельность, пока от графа не останется огрызок, содержащий не более двух вершин. Если вершин не осталось вообще, то мы объявили стратегически значимыми не более $[2 \cdot 2017 / 3]=1344$ вершин, и процесс завершился. Если осталась одна вершина, то на предыдущем шаге нашего алгоритма она называлась $A$ и была соединена с вершиной $X$ или $Y$ , которую объявили стратегически значимой, значит, для нее условие выполнено, и стратегически значимыми было объявлено не более $[2 \cdot 2016 / 3]=1344$ вершин. Если же осталось две вершины, то, во-первых, они смежны, так как граф связности не теряет; во-вторых, одна из этих двух вершин была соединена с вершиной $X$ или $Y$ , объявленной стратегически значимой на предыдущем шаге. Поэтому достаточно объявить стратегически значимой лишь одну из этих двух вершин, чтобы условие выполнялось. Значит, и в этом случае стратегически значимыми будет объявлено не более $[2 \cdot 2015 / 3]+1=1344$ вершин.

Задача 067

01.01.2025 от

Дано натуральное число п. Назовём словом последовательность из $n$ нулей и единиц, а маской — последовательность из п нулей, единии, и звёздочек. Слово соответствует маске, если оно получено из неё заменой звёздочек на нули и единицы. Рассмотрим набор масок $\mathcal{M}$ , удовлетворяющий следующим двум условиям:

(1) каждое слово соответствует ровно одной маске, и

(2) для каждой из п позиций найдётся маска из $\mathcal{M}$ , в которой в этой позиции стоит не звездочка.

Найдите наименьшее возможное количество масок в таком наборе $\mathcal{M}$ .

Подсказка

Рассмотрим двудольный граф $G$ , в котором вершинами одной из долей будут номера позиций в слове длины $n$ , вершинами второй из долей будут маски, а рёбрами соединим каждую маску с теми позициями, на которых стоит не звездочка. Пусть доля $V_{1}$ это вершины $\{1,2 \ldots, n\}$ , соответствующие номерам позиций, а доля $V_{2}$ это вершины $\left\{u_{1}, u_{2} \ldots, u_{k}\right\}$ , соответствующие маскам.

Решение

Докажем, что в графе $G$ для доли $V_{1}$ выполнено условие леммы Холла. Предположим противное. Рассмотрим в $V_{1}$ минимальное по включению множество $A$ , для которого условие леммы Холла не выполнено. То есть у вершин из $A$ количество соседей меньше, чем $|A|$ , а для любого подмножества $B$ множества $A$ количество соседей у вершин из $B$ хотя бы $|B|$ . Отсюда следует, что у $A$ ровно $|A|-1$ соседних вершин. Без ограничения общности будем считать, что $A=\{1, \ldots, s+1\}$ , а $\left\{u_{1}, \ldots, u_{s}\right\}$ это соседние вершины множества $A$ . Тогда для множества $\{1, \ldots, s\}$ выполнена лемма Холла. Пусть без ограничения общности существует паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(s, u_{s}\right)$ . Значит, в словах $u_{1}$ , $u_{2}, \ldots, u_{s}$ на $1,2, \ldots, s$ местах соответственно стоят не звёздочки (пусть без ограничения общности там стоят нули). Рассмотрим маски $u_{s+1}, \ldots, u_{k}$ . По построению в этих масках на местах с 1 по $s$ стоят звёздочки. Так как каждое слово можно получить из масок ровно одним способом, то из масок $u_{s+1}, \ldots, u_{k}$ получаются не все слова. Значит, существует множество слов $\underbrace{* * \ldots * *}_{s} \alpha$ (на первых $s$ позициях стоит что угодно, а затем идёт слово $\alpha$ длины $n-s$ ), которое нельзя получить из масок $u_{s+1}, \ldots, u_{k}$ . Тогда слово $\underbrace{1 \ldots 1}_{s} \alpha$ нельзя получить ни из какой маски. Противоречие.

Следовательно, для доли $V_{1}$ выполнено условие леммы Холла. Рассмотрим любое паросочетание, покрывающее долю $V_{1}$ . Пусть это паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(n, u_{n}\right)$ , а в словах $u_{1}, u_{2}, \ldots, u_{n}$ на $1,2, \ldots, n$ местах соответственно стоят нули. Тогда чтобы получить слово $11 \ldots 11$ нам нужна ещё хотя бы одна маска. Откуда и получаем оценку на $n+1$ .

Задача 073

01.01.2025 от

В дереве T 80 вершин. Набор из 39 независимых ребер (не имеющих общих вершин) будем называть толстым паросочетанием. Известно, что дерево $T$ имеет 820 различных толстых паросочетаний. Докажите, что $T$ — путь.

Подсказка

Будем доказывать индукцией по $n$ , что дерево на $2 n$ вершинах имеет не более $C_{n+1}^{2}$ (толстых) паросочетаний с $n-1$ независимыми рёбрами. Как выглядит дерево, если $n \geqslant 3$ и толстых паросочетаний ровно $C_{n+1}^{2}$ ? А при $n=2$ ?

Решение

Решение. Будем доказывать индукцией по $n$ , что дерево на $2 n$ вершинах имеет не более $C_{n+1}^{2}$ (толстых) паросочетаний с $n-1$ независимыми рёбрами. Причём если $n \geqslant 3$ и толстых паросочетаний ровно $C_{n+1}^{2}$ , то дерево является путем. А при $n=2$ граф является или путем, или «графом-ёжиком».

При $n=2$ существуют только такие деревья. Докажем переход. Пусть $T$ — дерево на $2 n$ вершинах, $n \geqslant 3$ . Так как дерево — это двудольный граф, его вершины можно разбить на две доли $V_{1}$ и $V_{2}$ . Заметим, что любое толстое паросочетание содержит по $n-1$ вершин из долей $V_{1}$ и $V_{2}$ . Следовательно, раз уж толстые паросочетния вообще существуют, возможны три случая, два из которых симметричны.
1. $\left|V_{1}\right|=n+1,\left|V_{2}\right|=n-1$ или $\left|V_{1}\right|=n-1,\left|V_{2}\right|=n+1$ . Разберём первый случай, второй доказывается аналогично. Заметим, что в любом толстом паросочетании не участвуют 2 вершины из доли $V_{1}$ . Количество способов выбрать две вершины из $V_{1}$ равно $C_{n+1}^{2}$ . Значит, толстых паросочетаний не более $C_{n+1}^{2}$ . Предположим, что их ровно $C_{n+1}^{2}$ . Тогда для любых двух вершин $u, v \in V_{1}$ существует толстое паросочетание, не содержащее вершины $u$ и $v$ . Но такого не может быть. Действительно, количество рёбер в дереве равно $2 n-1$ , а $\left|V_{2}\right|=n-1$ . Так как $n \geqslant 3$ , в доле $V_{2}$ есть вершина $x$ степени не более 2. Тогда без вершин из $V_{1}$ , среди которых есть все соседи $x$ , толстое паросочетания построить невозможно, противоречие.
2. $\left|V_{1}\right|=n,\left|V_{2}\right|=n$ . Подвесим граф за вершину. Пусть $v$ — висячая вершина последнего уровня, а $u$ — её сосед на предыдущем уровне. Без ограничения общности будем считать, что $v \in V_{1}$ . Если у вершины $u$ есть ещё одна соседняя висячая вершина $w$ , то любое толстое паросочетание не содержит одну из вершин $w$ или $v$ , и одну из вершин $V_{2}$ . Тогда толстых паросочетаний не больше $2 n<C_{n+1}^{2}$ при $n \geqslant 3$ .

Пусть у вершины $u$ нет соседних висячих вершин, кроме $v$ . Разобьём толстые паросочетания $T$ на два типа, первый тип — не содержащие $v$ , второй тип — содержащие ребро $u v$ . Паросочетаний первого типа не более $n$ , так как они не содержат $v$ и одну из вершин $V_{2}$ , коих $n$ . Все паросочетания второго типа образуют толстое паросочетание дерева $T^{\prime}=T-u-v$ , причём в $T^{\prime}$ поровну вершин в долях. По предположению индукции в дереве $T^{\prime}$ не более $C_{n}^{2}$ толстых паросочетаний. Значит, в $T$ не более $C_{n}^{2}+n=C_{n+1}^{2}$ толстых паросочетаний. Более того, если в дереве $T$ ровно $C_{n+1}^{2}$ толстых паросочетаний, то паросочетаний первого типа ровно $n$ , второго — ровно $C_{n}^{2}$ , а дерево $T^{\prime}$ — это путь $a_{1} a_{2} \ldots a_{2 n-2}$ . Если сосед $u$ — это $a_{1}$ или $a_{2 n-2}$ , то $T$ — путь. Иначе из соображения чётности одна из вершин $a_{2}$ и $a_{2 n-3}$ лежит в доле $V_{2}$ дерева $T$ (пусть $a_{2}$ ). Но тогда при удалении вершин $v$ и $a_{2}$ дерево не имеет паросочетания. Следовательно, паросочетаний первого типа меньше $n$ , противоречие. Индукционный переход доказан.

Задача 075

01.01.2025 от

В некоторой компании любые двое знакомых имеют ровно $x$ общих знакомых, любые двое незнакомых имеют ровно у общих знакомых, Дима и Саша имеют не поровну знакомых ( $x, y$ — натуральные числа). Найдите все пары ( $x, y$ ), при которых так может быть.

Подсказка

Рассмотрим пару знакомых человек: назовем их $u$ и $v$ . В множестве членов компании, отличных от $u$ и $v$ , выделим три множества: $A$ — множество общих знакомых $u$ и $v ; B$ — множество знакомых с $v$ , но не с $u ; C$ множество знакомых с $u$ , но не с $v$ .

Решение

Ответ. ( $x, 1$ ) для любого $x$ .

Решение. Рассмотрим пару знакомых человек: назовем их $u$ и $v$ . В множестве членов компании, отличных от $u$ и $v$ , выделим три множества: $A$ — множество общих знакомых $u$ и $v ; B$ — множество знакомых с $v$ , но не с $u ; C$ множество знакомых с $u$ , но не с $v$ .

Если $V_{1}, V_{2}$ — два непересекающихся множества членов компании, то через $e\left(V_{1}\right)$ обозначаем количество пар знакомых в $V_{1}$ , через $e\left(V_{1}, V_{2}\right)$ — количество пар знакомых, один из которых в $V_{1}$ , а второй — в $V_{2}$ . Количество элементов множества $M$ обозначаем через $|M|$ .
$У$ каждого человека $w \in A$ имеется ровно $x-1$ знакомых в множестве $A \cup C$ (это его общие знакомые с $u$ , отличные от $v$ ). Просуммируем эти количества по всем $w \in A$ . Получаем $|A| \cdot(x-1)=2 e(A)+e(A, C)$ (здесь каждая пара знакомств внутри $A$ посчитана дважды, а каждое знакомство между $A$ и $C$ — один раз). Аналогично, $|A| \cdot(x-1)=2 e(A)+e(A, B)$ . Поэтому $e(A, B)=e(A, C)$ .

Далее, каждый человек в $B$ имеет $y-1$ соседей в $A \cup C$ (это его общие знакомые с $u$ , кроме $v$ ); Суммируя эти количества, получаем $(y-1)|B|=e(A, B)+e(B, C)$ . Аналогично, $(y-1)|C|=e(A, C)+e(C, B)$ . Поскольку $e(A, B)=e(A, C)$ и $e(B, C)= e(C, B)$ , мы приходим к выводу, что $(y-1)|B|=(y-1)|C|$ , а тогда $|B|=|C|$ или $y=1$ .

Если $y>1$ , то мы получили, что любые два знакомых человека имеют одинаковое число знакомых. А поскольку любые два либо знакомы, либо имеют общего знакомого, то такое невозможно, так как Дима и Саша имеют разное число знакомых.

Значит $y=1$ . Осталось показать, что такое действительно бывает. Рассмотрим компанию из $2 x+3$ человек, выделим в ней две группы по $x+1$ человеку и пусть оставшийся — Дима. Пусть Дима знаком со всеми, и внутри каждой из групп также все знакомы со всеми. Тогда для любых двух незнакомых людей (это люди из разных групп) у них есть единственный общий знакомый — Дима. У Димы с человеком из группы ровно $x$ общих знакомых — это остальные люди этой группы. У любых двух людей из одной группы $x$ общих знакомых — остальные люди этой группы и Дима. Также, Дима единственный, кто знаком со всеми, значит у них с Сашей разное число знакомых.