Кубок Колмогорова — Страница 2 — Задачи на Графы

Задача 036

01.01.2025 от

В стране 100 городов и 1000 дорог; каждая дорога соединяет ровно 2 города. Известно, что из любого города можно добраться в другой (возможно, через некоторые другие города) не больше, чем за 8 ч. Мужик на желтой «Калине» хочет объехать все города и вернуться в исходный город. За какое минимальное время он гарантированно может это сделать?

Подсказка

Для построение примеры выделите одну из вершин. А часть рёбер сделайте очень длинными.

Решение

Ответ: 99.8 часов.

Решение: Оценка. Граф городов и дорог не полный, значит, кратчайший путь между какими-то двумя городами проходит через какой-то город. Пусть, например, кратчайший путь от $x_{1}$ до $x_{3}$ проходит через $x_{2}$ . Тогда, цикл $x_{1} \rightarrow x_{2} \rightarrow x_{3} \rightarrow \ldots \rightarrow x_{99} \rightarrow x_{100}$ требует не более $99 \cdot 8$ часов, так как переезд от $x_{1}$ к $x_{3}$ и все остальные переходы требуют не более 8 часов каждый.

Пример. Все города связаны с $x_{2}$ дорогами, требующими 4 часов каждая. Остальные города либо связаны дорогами, либо нет, чтобы общее число дорог равнялось 1000. Все дороги между ними требуют 8 часов. Легко видеть, что оценка достигается.

Задача 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}$ длины всех рёбер не более трёх.

Задача 040

01.01.2025 от

30 кружковцев Дмитрия Андреевича $k$ раз делились на две команды и проводили тренировочный матбой. На каждом матбое Дмитрий Андреевич называл одну из команд хорошей. При каком наименьшем $k$ он, как бы кружковиы ни делились, гарантированно мог сделать так, чтобы каждый ребенок хоть раз побывал в хорошей команде?

Подсказка

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

Решение

Ответ: 5.

Решение. Назовем невезучими детей, которые ни разу еще не побывали в хорошей команде. Стратегия Дмитрия Андреевича состоит в том, чтобы каждый раз называть хорошей команду, куда попала большая часть невезучих. Так ему после первого боя удастся сделать так, чтобы невезучих было не более 15, после второго — не более 7 , после третьего — не более 3 , после четвертого — не более одного. С другой стороны, если дети каждый раз будут делиться так, чтобы количества невезучих в двух командах отличались не более, чем на 1 , Дмитрию Андреевичу не удастся сделать всех везучими за 4 боя.

Задача 042

01.01.2025 от

Каждые два из 21 города соединены прямым рейсом одной из четырёх авиакомпаний. Докажите, что существует замкнутый маршрут из четырех рейсов одной авиакомпании.

Подсказка

Решение

Все маршруты образуют полный граф на 21 вершине, рёбра которого раскрашены в 4 цвета. Если искомого замкнутого маршрута нет, любые две вершины этого графа связаны не более чем одним одноцветным маршрутом длины 2. Стало быть, всего таких маршрутов не более, чем $4 C_{21}^{2}=840$ . С другой стороны, пусть из данной вершины выходит $a, b, c$ и $d$ рёбер первого, второго, третьего и четвёртого цветов соответственно. Тогда число одноцветных маршрутов длины 2 , для которых эта вершина — средняя, равно $(a(a-1)+b(b-1)+c(c- 1)+d(d-1)) / 2=\left(a^{2}+b^{2}+c^{2}+d^{2}-(a+b+c+d)\right) / 2=\left(a^{2}+b^{2}+c^{2}+d^{2}\right) / 2-10$ . По неравенству между средним арифметическим и средним квадратическим имеем: $a^{2}+b^{2}+c^{2}+d^{2} \geq(a+b+c+d)^{2} / 4=100$ . Таким образом, каждая вершина нашего графа является средней минимум для $100 / 2-10=40$ одноцветных маршрутов, причём минимум достигается только в случае, когда из вершины выходит ровно по 5 маршрутов каждого цвета. И только в этом случае сумма количеств одноцветных маршрутов длины 2 по всем вершинам равна 840, в остальных — больше. Но такой случай невозможен, потому что тогда, оставив в нашем графе только рёбра одного какого-то цвета, мы получили бы граф с нечётным числом нечётных вершин.

Задача 043

01.01.2025 от

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

Подсказка

Допустим, утверждение задачи неверно для какого-либо графа на 2008 вершинах. Будем говорить, что вершина $A$ портит вершину $B$ , если вершину $A$ можно перекрасить так, чтобы вершина $B$ , которая не была плохой, стала плохой. Заметим, что если степень вершины не равна 2 , её можно испортить не более чем одним способом.

Решение

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

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

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

Задача 044

01.01.2025 от

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

Подсказка

Всего из дерева получается нечётное число графов, в которых добавлено ещё одно ребро.

Решение

Пусть $G$ — наш граф, $\mathrm{T}(G)$ — множество всех остовных деревьев графа $G$ , а М( $G$ ) — множество всех остовных подграфов графа $G$ , имеющих ровно один цикл. Рассмотрим произвольное дерево $T \subset \mathrm{~T}(G)$ . В нем нечетное число ребер, следовательно, количество не вошедших в $T$ ребер графа $G$ также нечетно. Если к дереву $T \subset \mathrm{~T}(G)$ добавить любое не вошедшее в него ребро графа $G$ , то получится граф из $\mathrm{M}(G)$ . Всего таким образом из дерева $T$ получается нечетное число графов из $\mathrm{M}(G)$ . Наоборот, рассмотрим любой граф $H \subset \mathrm{M}(G)$ и его единственный цикл $Z$ . Граф $H$ может быть получен добавлением ребра к тем деревьям, которые получаются из $H$ удалением одного из ребер цикла $Z$ . Так как граф $G$ двудольный, то в цикле $Z$ — четное число ребер, следовательно, у графа $H$ — четное число остовных деревьев-«»предков»». Отсюда следует, что в множестве $\mathrm{T}(G)$ четное число остовных деревьев.

Задача 045

01.01.2025 от

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

Подсказка

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

Решение

Пусть $G$ — наш граф, обозначим через $2 k$ количество его вершин. Построим новый граф $H$ , вершинами которого будут остовные деревья графа $G$ . Вершины, соответствующие деревьям $T_{1}$ и $T_{2}$ соединим ребром тогда и только тогда, когда в деревьях $T_{1}$ и $T_{2}$ совпадают $2 k-2$ ребра (то есть одно дерево получается из другого заменой одного ребра). Рассмотрим любое остовное дерево $T$ графа $G$ и рассмотрим любое его ребро $e$ . Уберем ребро $e$ , вершины дерева $T$ распадутся на две компоненты связности $V$ и $U$ . Так как степень каждой вершины графа $G$ четна, то в графе $G$ четное число ребер с одним концом в $V$ и другим концом в $V$ . Заменив ребро $e$ на любое другое ребро между $V$ и $U$ , мы получим все остовные деревья, получающиеся из $T$ заменой ребра $e$ на какое-то другое ребро. Количество таких деревьев нечетно. То же самое верно для любого ребра дерева $T$ . Так как в $T$ нечетное число ребер, то из соответствующей дереву $T$ вершины графа $H$ выходит нечетное число ребер. Это означает, что количество вершин графа $H$ (то есть, остовных деревьев графа $G$ ) четно.

Задача 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$ цветов. Противоречие.