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

Задача 003

01.01.2025 от

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

Подсказка

Предположите, что нечётного цикла нет. Что следует из двудольности?

Решение

Пусть данные важные ребра — $a b$ и $a c$ , а максимальный размер пустого подграфа — $k$ . Тогда есть такие множества вершин $B$ и $C$ мощности $k+1$ каждое, что $a b$ и $a c$ соответственно являются в них единственными ребрами. Выкинем из графа все вершины, кроме $B \cup C$ , от этого условие не изменится. После этого все вершины множества $B \cap C$ , кроме вершины $a$ , ни с какой вершиной не соединены. Поэтому их тоже можно выбросить, после чего как $k$ , так и количества элементов в $B$ и $C$ уменьшатся на одну и ту же величину. После этого у нас остался граф на $2 k+1$ вершине; если в нем нет нечетного цикла, то он двудольный, тогда в нем есть пустой подграф на $k+1$ вершине, что не так. Следовательно, нечетный цикл есть.

Задача 004

01.01.2025 от

Дано дерево $T$ с $n>2$ вершинами, в котором степени всех вершин меньше $n-1$ . Пусть $A$ — множество его висячих вершин. Добавим к дереву $T$ рёбра некоторого цикла, проходящего по всем вершинам множества $A$ ровно по одному разу и не проходящего через остальные вершины. Докажите, что вершины полученного графа можно правильно раскрасить в три цвета.

Подсказка

Рассмотрите в графе висячую вершину и вершины на расстоянии 2 от неё.

Решение

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

Задача 007

01.01.2025 от

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

Подсказка

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

Решение

Скажем, что пара мальчиков и пара девочек сопряжены, если каждый мальчик из первой пары танцевал с каждой девочкой из второй. Из условия следует, что каждая пара мальчиков сопряжена ровно с тремя парами девочек, а каждая пара девочек — ровно с тремя парами мальчиков. Отсюда следует, что пар мальчиков столько же, сколько пар девочек, а именно — втрое меньше общего числа сопряжённых пар. Таким образом, если мальчиков на вечеринке было $m$ , а девочек — $d$ , то $m(m-1)=d(d-1)$ , откуда $m=d$ .

Задача 013

01.01.2025 от

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

Подсказка

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

Решение

Ответ. 197.
Решение: Построим ориентированный граф, вершины которого соответствуют городам, а ребра — дорогам (направление ребра будет соответствовать направлению дороги). Любые две вершины соединены не более, чем одним ориентированным ребром. Полученный граф будет связным (из любой вершины можно попасть в любую другую), но при удалении любого ребра связность теряется.

Построим пример такого графа со 197 ребрами. Он будет состоять из вершин $A, B, \mathrm{C}_{1}, \ldots, \mathrm{C}_{98}$ , и ребер $A \rightarrow C$ , а также $C \rightarrow B_{i}$ и $B_{i} \rightarrow A$ для всех $i$ . Нетрудно проверить, что этот граф подходит.

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

Доказательство: Рассмотрим в нашем графе произвольную вершину $A$ . Нетрудно понять, что достаточно отметить в графе $k-1$ ребро, чтобы только по отмеченным вершинам можно было бы добраться из $A$ до любой другой вершины. Аналогично, можно отметить в графе еще $k-1$ ребро так, чтобы по отмеченным вершинам можно было бы добраться из любой другой вершины до $A$ . В графе должны остаться неотмеченные ребра — любое из них можно удалить без потери связности. Лемма доказана.

Перейдем к доказательству утверждения задачи. Из связности графа следует, что в нем есть (ориентированный) цикл $C_{1} \rightarrow C_{2} \rightarrow \ldots \rightarrow C_{m} \rightarrow C_{1}$ . Понятно, что $m \geq 3$ и нет никаких ребер между входящими в цикл вершинами, кроме ребер самого цикла (иначе такое ребро можно удалить без потери связности). Также отметим, что из любой не входящей в цикл вершины А существует не более одного ребра, выходящего к вершинам цикла (если таких ребер хотя бы два, то одно из них можно удалить без потери связности). Аналогично, существует не более одного ребра, выходящего из вершин цикла в А.

Заменим все вершины цикла на одну вершину $C$ и для любой другой вершины $A$ проведем ребро $A \rightarrow C$ , если существует одно из ребер $A \rightarrow C_{i}$ и ребро $C \rightarrow A$ , если существует одно из ребер $C_{i} \rightarrow \mathrm{~A}$ . Получится новый связный ориентированный графG’, в котором ровно на $m$ ребер меньше, чем в исходном графе и удаление любого ребра нарушает связность. (Однако, в этом графе возможно наличие двух ребер разного направления между двумя вершинами.) В графе G’ ровно $100-m+1$ вершина и, по доказанному выше утверждению, не более $2(100-m+1)-2=200-2 m$ ребер. Следовательно, в исходном графе было не более, чем $200-m \leq 200-3=197$ ребер.

Задача 017

01.01.2025 от

Известно, что некоторые сенаторы между собой в ссоре. Проверено, однако, что как бы мы не посадили их всех или любую группу (3 или более) из них по кругу, найдется пара соседей не в ссоре. Весь сенат усадили за круглый стол. Если два соседа не в ссоре, они могут поменяться местами. Докажите, что сенаторы могут расположиться в любом круговом порядке (порядки, полученные поворотом, не различаются).

Подсказка

Попробуйте доказать индукцией по количеству сенаторов.

Решение

Докажем индукцией по числу сенаторов. База. Для трех сенаторов есть только два круговых порядка. Они получаются друг из друга пересадкой двух соседей, которые не в ссоре. Шаг индукции. Найдется сенатор А, который в ссоре не более чем с одним сенатором (иначе часть сенаторов можно будет рассадить по кругу так, что у каждого соседями будут враги). Пусть Б в ссоре с А (а если А дружит со всеми, то Б — любой другой). По предположению индукции, если А уйдет из-за стола, то есть способ рассадить оставшихся в нужном круговом порядке. Однако это можно сделать и при наличии А. Придвинем А к Б (это можно сделать) и попросим А и Б взяться за руки. Считая эту пару сенатором Б, рассадим всех в нужном порядке вышеуказанным способом. Теперь можно А посадить на нужное место, последовательно «отодвигая» его от Б.

Задача 019

01.01.2025 от

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

Подсказка

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

Решение

Будем доказывать индукцией по числу $n$ вершин. База для $n=3$ и $n=4$ проверяется без труда. Пусть для всех графов с менее чем $n$ вершинами условие выполнено, а в графе $G$ с $n$ вершинами и исходящими степенями 3 не нашлось двух непересекающихся циклов.

Предположим, что в $G$ есть встречные ребра между вершинами $v$ и $w$ . Тогда в $G$ есть цикл $v w$ , и в $G-\{v, w\}$ есть цикл, так как в нем из каждой вершины выходит хотя бы одно ребро. Следовательно, в $G$ нет встречных ребер.

Предположим, что в $G$ есть ребро $u v$ такое, что ни из какой вершины $x \in V(G)$ не выходят ребра в обе вершины $u$ и $v$ . Тогда стянем ребро $u v$ : удалим в $G$ вершины $u$ и $v$ и добавим новую вершину $w$ , в которую входят ребра из тех вершин, из которых входили ребра в $u$ и $v$ , и выходят ребра в те вершины, в которые выходили ребра из $v$ . Обозначим полученный граф через $G^{\prime}$ . В $G^{\prime} n-1$ вершина и степень каждой вершины равна 3 , поэтому для него выполнено индукционное предположение. Но тогда и в $G$ есть два непересекающихся цикла, так как если цикл в $G^{\prime}$ проходил через $w$ , то в $G$ этот проход можно заменить на проход через $v$ или $u v$ .

Осталось разобрать случай, когда каждое ребро имеет «предка», то есть вершину, из которой выходят ребра в оба конца этого ребра. Пусть $v$ — вершина наименьшей входящей степени (обозначим эту степень $d^{-}(v)$ ). Очевидно, $d^{-}(v) \leq 3$ .

(1) $d^{-}(v)=0$ . Тогда ребро, исходящее из $v$ , не имеет предка.
(2) $d^{-}(v)=1$ . Тогда ребро, входящее в $v$ , не имеет предка.
(3) $d^{-}(v)=2$ . Пусть есть ребра $u v$ и $w v$ . Тогда $u$ должно быть предком для $w v$ , а $w$ — для $u v$ , но тогда есть ребра $v w$ и $w v$ , а этот случай мы уже разобрали.
(4) $d^{-}(v)=3$ . Тогда все вершины имеют входящую степень 3. Пусть в вершину $x$ входят ребра $u x, v x, w x$ . Предком каждого из этих ребер должна быть $u, v$ или $w$ . Тогда в индуцированном подграфе на вершинах $u, v, w$ в каждую вершину входит хотя бы одно ребро, а так как в $G$ нет встречных ребер, вершины $u, v, w$ образуют цикл длины 3. Заметим, что вершины, в которые ведут ребра из $x$ , также образуют цикл длины 3 (так как мы можем обратить все ребра и повторить те же рассуждения). $B G$ нет встречных ребер, поэтому мы нашли два непересекающихся цикла.

Задача 020

01.01.2025 от

В классе поровну мальчиков и девочек, и все ученики разного роста. Оказалось, что если мальчик дружит с девочкой, то он дружит и со всеми девочками выше неё; и наоборот — если девочка дружит с мальчиком, то она дружит и со всеми мальчиками выше него. Учитель физкультуры хочет выстроить детей в ряд, начиная с мальчика, так, чтобы любые двое соседей в ряду были друзьями разного пола. Оказалось, что количество способов это сделать — натуральное число $N$ , делящееся на 101. Каким наименьшим количеством нулей может оканчиваться десятичная запись числа $N$ ?

Подсказка

Для начала докажите лемму.

Лемма. $N=\left(a_{1} a_{2} \ldots a_{k}\right)^{2}$ , где $a_{1}, \ldots, a_{k}$ — некоторая последовательность неотрицательных целых чисел такая, что $i \geq a_{i} \geq a_{i+1}-1$ при всех $i=1,2, \ldots, k-1$ .

Решение

Ответ. 48.
Решение: Назовём исследуемые расстановки легальными. Пусть $k$ количество мальчиков. Пример получается при $k=101$ , когда все дружат. Действительно, тогда $N=(101!)^{2}$ , причём 2 входит в 101 ! хотя бы в 50 степени, а 5 — в степени $[101 / 5]+\left[101 / 5^{2}\right]=24$ , ибо $101<5^{3}$ . Значит, $N$ оканчивается ровно 48 нулями.

Сначала выведем оценку из леммы. Поскольку $N$ натурально, $a_{1} \geq 1$ , то есть $a_{1}=1$ . Если $N$ делится на 101 , то одно из чисел $a_{1}, \ldots, a_{k}$ делится на $101-$ скажем, это $a_{j}$ . Из условий $a_{i-1} \geq a_{i}-1$ следует, что среди чисел $a_{1}, \ldots, a_{j-1}$ встретятся все числа от 1 до 100 , то есть $N$ делится на ( $100!)^{2}$ и, следовательно, на $10^{48}$ .

Осталось доказать лемму. Числа $a_{k-i}$ будут определяться так. Выкинем из компании $i$ самых маленьких девочек и $i$ самых больших мальчиков. Тогда $a_{k-i}$ — это количество оставшихся мальчиков, знакомых со всеми оставшимися девочками. Из этого описания немедленно следуют условия на $a_{i}$ , указанные в лемме.

Индукция по $k$ . При $k=1$ имеем $N=1=a_{1}$ . Пусть теперь $k>1$ . Рассмотрим самую маленькую девочку $d$ ; пусть $M$ — множество мальчиков, которые с ней дружат, $|M|=a_{k}$ . Заметим, что $M$ состоит из $a_{k}$ самых высоких мальчиков.

В любой легальной расстановке перед $d$ стоит мальчик $m$ из $M$ , а после неё — либо мальчик $m^{\prime}$ из $M$ , либо никто. Так как $m^{\prime}$ , если он существует, знаком со всеми девочками, то после выбрасывания пары ( $m, d$ ) из расстановки получится легальная расстановка оставшихся детей. Наоборот, в любую легальную расстановку $2(k-1)$ детей, отличных от $m$ и $d$ , пару ( $m, d$ ) можно вставить либо перед произвольным $m^{\prime} \in M\{m\}$ , либо в конец, то есть $a_{k}$ способами.

Далее, поскольку $m$ дружит со всеми, для всех $m \in M$ после выкидывания пары ( $m, d$ ) останутся «одинаковые» компании детей (научным языком, графы их дружб изоморфны). Поэтому в них будет поровну легальных расстановок, и эти количества будут по предположению индукции иметь вид $N^{\prime}=\left(a_{1} a_{2} \ldots a_{k-1}\right)^{2}$ . Итак, для каждого из $a_{k}$ мальчиков из $M$ в каждую из $N^{\prime}$ перестановок можно вставить пару ( $m, d$ ) ровно $a_{k}$ способами. Значит, $N=N^{\prime} a_{k}^{2}$ , что и требовалось.

Задача 022

01.01.2025 от

Пусть $A$ — количество способов, которыми можно разбить множество натуральных чисел от 1 до $n$ на непустые подмножества. Пусть $B$ — количество способов разбить множество натуральных чисел от 1 до $n+1$ на непустые подмножества так, чтобы соседние числа были в разных подмножествах. Разбиения, отличающиеся только порядком подмножеств, считаются одинаковыми. Докажите, что $A=B$ .

Подсказка

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

Решение

Для каждого разбиения чисел от 1 до $n$ занумеруем составляющие его подмножества в порядке, в котором идут их наименьшие числа. Построим дерево с вершинами, помеченными числами от 1 до $n$ , маршруты из корня которого в его висячие вершины будут находиться во взаимнооднозначном соответствии с разбиениями чисел от 1 до $n$ на непустые подмножества. Корень занумеруем цифрой 1 : единица всегда в первом подмножестве. Двойка может лежать либо в подмножестве 1 , либо в подмножестве 2 , поэтому на следующем ярусе расположим соответствующие этим двум случаям вершины, помеченные цифрами 1 и 2 . Далее дерево строится по индукции: если уже построены $k$ ярусов, то с каждой вершиной $C k$ -го яруса связано $m+1$ вершин ( $k+1$ )-го яруса, помеченных числами от 1 до $m+1$ , где $m$ — наибольшее число на маршруте из $C$ в корень дерева.

Теперь построим аналогичное дерево для разбиений чисел от 1 до $n+1$ , где соседние числа находятся в разных подмножествах. Из его корня, помеченного единицей, ведет ребро в единственную вершину второго яруса, помеченную двойкой, а из неё — в две вершины третьего яруса, помеченные единицей и тройкой (двойка невозможна, поскольку тогда числа 2 и 3 попадут в одно подмножество). Далее дерево строится по индукции: если уже построены $k$ ярусов, то с каждой вершиной $C k$ -го яруса связано $m$ вершин ( $k+1$ )-го яруса, помеченных числами от 1 до $m+1$ , исключая число, которым помечена вершина $C$ , где $m$ — наибольшее число на маршруте из $C$ в корень дерева.

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

Задача 024

01.01.2025 от

В некотором графе степень каждой вершины не превосходит 1000. Докажите, что рёбра графа можно так покрасить в 10 цветов, что не найдется нечетного одноцветного цикла.

Подсказка

Лемма: Ребра полного графа на $2^{n}$ вершинах можно раскрасить в $n$ цветов так, чтобы граф с ребрами любого цвета был двудольным.

Решение

Доказательство: Лемма легко доказывается индукцией по $n$ , база для $n=1$ очевидна. Переход тоже несложен: разобьем вершины на две группы по $2^{n-1}$ вершине, все ребра между группами покрасим в цвет $n$ , граф из ребер этого цвета будет очевидно двудольным. Теперь для каждой из половинок покрасим ребра в цвета $1,2, \ldots, n-1$ (это можно по индукционному предположению). Графы этих цветов также будут двудольными, так как состоят из двух несвязанных двудольных частей каждый.

Теперь перейдем к решению задачи. Легко покрасить вершины данного графа $G$ степени не более 1000 правильным образом в $1024=2^{10}$ цветов (и даже в 1001 цвет). Теперь, рассмотрим раскраску в 10 цветов ребер полного графа на 1024 вершинах (вершины которого занумерованы цветами вершин графа $G$ ), в которой граф каждого цвета двудолен. Покрасим все ребра графа $G$ между вершинами цветов $i$ и $j$ также, как и ребро между вершинами $i$ и $j$ в раскраске полного графа. Очевидно, нечетных циклов в графе ребер любого цвета не будет.

Задача 034

01.01.2025 от

$m$ и $n$ — натуральные числа, причём $1<m<n-1$ . В компании из $n$ человек некоторые знакомы друг с другом, причём среди любых $m$ человек из этой компании одно и тоже количество пар знакомых. Сколько пар знакомых может быть среди всех $n$ человек?

Подсказка

Надо показать, что в данной компании каждый знаком с каждым.

Решение

Ответ: $n(n-1) / 2$ .
Решение: Надо показать, что в данной компании каждый знаком с каждым. Заметим для начала, что если взять любую группу из $m+1$ человека, у каждого из её членов будет одно и то число же знакомых среди остальных членов этой группы (назовём это число cmeпенью группы). В самом деле, кого бы ни убрать из группы, общее число знакомств среди $m$ оставшихся по условию будет одним и тем же.

Допустим, в компании есть люди, не знакомые между собой. Тогда, поскольку по условию в компании есть и знакомые, найдётся группа $L$ из $m+1$ человека, среди которых есть как не знакомые между собой люди $A$ и $B$ , так и хотя бы двое знакомых между собой. Поскольку $m<n-1$ , найдется человек $C$ , не входящий в $L$ . Заменим в группе $L$ человека $A$ на $C$ . Получится новая группа $M$ . При замене $L$ на $M$ число знакомых человека $B$ среди членов группы не уменьшилось, поэтому степень у $M$ не меньше, чем у $L$ . С другой стороны, после удаления $A$ и добавления $C$ число знакомых у тех, кто был знаком с $A$ , не увеличилось. Поэтому степень у $M$ не больше, чем у $L$ . Стало быть, степени у $M$ и $L$ равны. Поэтому $C$ знаком в $L$ точности с теми же людьми, что и $A$ : ведь при переходе от $L$ к $M$ им надо восполнить потерю знакомства с $A$ .

Пусть $D$ — один из этих людей. Заменим в $L$ человека $D$ на $C$ . Получим некоторую группу $N$ . Поскольку $D$ знаком в $L$ не со всеми (так как не со всеми знаком в ней $A$ ), рассуждая так же, как выше, убеждаемся, что степени групп $L$ и $N$ равны. Но это невозможно, так как при перехо-

де от $L$ к $N$ мы теряем все знакомства человека $D$ , а восполнить можем только на одно меньше, ибо теряем также знакомство $C$ с $D$ . Полученное противоречие показывает, что незнакомых в данной компании быть не может.