Раскраска графов — Задачи на Графы

Задача 004

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 016

01.01.2025 от

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

Подсказка

Разделите числа на 10 групп.

Решение

Разобьём числа на десять десятков: $1-10,11-20, \ldots, 91-100$ , и числа из одного десятка будем соединять синей стрелкой, а из разных десятков — красной. Понятно, что по синим стрелкам мы не выйдем за пределы десятка, и потому пройдем не больше 9 стрелок, а идя по красным стрелкам, мы каждый раз будем попадать в новый десяток и также пройдем не больше 9 стрелок.

Задача 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$ в раскраске полного графа. Очевидно, нечетных циклов в графе ребер любого цвета не будет.

Задача 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 не делится.

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

Задача 055

01.01.2025 от

На каждом ребре полного графа с 2019 вершинами написано число 1,2 или 3 так, что сумма чисел на рёбрах каждого треугольника не меньше 5. Какова наименьшая возможная сумма всех чисел на рёбрах?

Подсказка

Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2.

Решение

Ответ. 2019.2018-1009 = 4073333.

Решение. Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2. Сумма написанных чисел будет как раз 2•(2019•2018/2) $1009=4073333$ . Оценка. Назовём вершину плохой, если из неё выходит больше одного ребра, помеченного единицей. Если в графе нет плохих вершин, то всё в порядке: ребер с единицами не больше 1009, и сумма написанных не ребрах чисел не меньше $2 \cdot(2019 \cdot 2018 / 2)-1009$ . Пусть плохая вершина $A$ есть. Возьмём ребро $A B$ , на котором написана единица, и рассмотрим все треугольники вида $A B C$ . Если на одной из сторон $A C$ или $B C$ такого треугольника написана единица, то на другой должна быть тройка. Во всех таких случаях заменим эти единицу и тройку на две двойки. Сумма написанных на ребрах чисел при этом не изменится, сумма чисел на сторонах любого треугольника останется не меньше 5, а число плохих вершин уменьшится. Повторяя описанную процедуру, мы можем уничтожить все плохие вершины, а для графа без плохих вершин всё уже было доказано.

Задача 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$ .

Задача 072

01.01.2025 от

Нечётная раскраска графа — это такая раскраска множества его вершин в несколько иветов, что любые две соседние вершины покрашены в разный цвет и при этом для каждой вершины можно указать цвет, в который покрашено нечётное число её соседей. Барон Мюнхгаузен нарисовал граф и создал нечётную раскраску его вершин в 1022 ивета. «Вы можете мне не поверить, друзья, — говорит барон, — но на этом графе не существует нечётных раскрасок с меньшим числом цветов. Однако после того как я добавил всего одну вершину и соединил её с некоторыми вершинами этого графа, для нечётной раскраски мне понадобилось всего три цвета». Не обманывает ли нас барон?

Подсказка

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

Решение

Ответ: не обманывает.

Решение. Возьмем полный граф на 1022 вершинах, которые условно будем называть «толстыми». В середине каждого ребра поставим новую вершину (иными словами, мы заменяем каждое ребро этого графа на двузвенный путь). Новые вершины будем считать «тощими». Возьмём произвольную нечётную раскраску полученного графа. Для любых двух толстых вершин $A$ и $B$ рассмотрим тощую вершину $C$ , соединенную с ними. Так как у вершины $C$ в этом графе всего две соседние вершины (это как раз $A$ и $B$ ), эти вершины должны быть окрашены в разный цвет. Итак, любые две толстые вершины должны быть разного цвета, следовательно, в раскраске используется не меньше 1022 цветов.

Теперь добавим к нашему графу одну новую вершину и соединим её со всеми тощими. На полученном графе нам хватит трёх цветов: все толстые вершины красим в красный цвет, тощие — в зелёный, новую — в синий. Эта раскраска удовлетворяет требованию нечётности, поскольку у каждой красной вершины 1021 зелёный сосед, у каждой зелёной имеется один синий сосед, а у синей вершины имеется $\frac{1}{2} \cdot 1022 \cdot 1021$ , т.е. нечётное число зелёных соседей.

Задача 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.