Двудольные графы — Задачи на Графы

Задача 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$ вершине, что не так. Следовательно, нечетный цикл есть.

Задача 011

01.01.2025 от

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

Подсказка

Обозначьте число городов в республике за х.

Решение

Ответ: 67.

Решение: Пусть в отделившейся республике $x$ городов. Тогда количество дорог, соединяющих ее города, равно $x(x-1) / 2$ (из каждого из $x$ городов выходит по $x-1$ дороге, и каждая дорога при этом считается дважды), а количество дорог, ведущих из республики в остальные города страны, равно $x(100-x)$ . По условию $x(x-1) / 2=x(100-x)$ . Сократив на $x$ и решив получившееся уравнение, находим ответ.

Задача 017

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 018

01.01.2025 от

На танцах было $2 n$ мальчиков и $2 n$ девочек. Боря танцевал со всеми девочками, Аня танцевала со всеми мальчиками, и для любых двух девочек есть ровно n мальчиков, танцевавших ровно с одной из них. Докажите, что каждый мальчик, кроме Бори, танцевал ровно с $n$ девочками.

Подсказка

Рассмотрите вместе с Аней ещё одну (любую) девочку. Что следует их условия?

Решение

Возьмём Аню и любую другую девочку Д. По условию, ровно с одной девочкой из этих двух танцевало ровно $n$ мальчиков. Так как с Аней танцевали все мальчики, то эти $n$ мальчиков танцевали именно с ней, а остальные $n$ мальчиков танцевали и с ней, и с Д. Итак, с каждой девочкой, кроме Ани, танцевали ровно $n$ мальчиков. Возьмём любых двух таких девочек. Пусть с обеими танцевали $m$ мальчиков. Тогда ровно с одной танцевали $n=2(n-m)$ мальчиков, откуда $m=n / 2$ .

Забудем про Аню и Борю. Тогда каждая из девочек танцевала с $n-1$ мальчиком, а с каждыми двумя девочками танцевали $n / 2-1$ мальчиков. Занумеруем мальчиков и пусть $i$ -ый мальчик танцевал с $d_{i}$ девочками. Тогда троек, состоящих из мальчика и двух девочек, с которыми он танцевал, будет $d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2$ . С другой стороны, число таких троек равно $n / 2-1$ , умноженному на количество пар девочек, то есть $(n / 2-1)(2 n-1)(n-1)$ .
Заметим, что

$d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2=\left(d_{1}^{2}+\ldots+d_{2 n-1}^{2}\right) / 2-\left(d_{1}+\ldots+d_{2 n-1}\right) / 2 \text {. }$

Так как $d_{1}+\ldots+d_{2 k-1}=(n-1)(2 n-1)$ (считаем ту же сумму «со стороны девочек»), то получаем, что

$d_{1}^{2}+\ldots+d_{2 n-1}^{2}=2(n / 2-1)(2 n-1)(n-1)+(n-1)(2 n-1)=(n-1)^{2}(2 n-1) .$

С другой стороны, по неравенству между средним арифметическим и средним квадратическим

$d_{1}^{2}+\ldots+d_{2 n-1}^{2} \geq\left(d_{1}+\ldots+d_{2 n-1}\right)^{2} /(2 n-1)=(n-1)^{2}(2 n-1)$

причём равенство достигается только при $d_{1}=\ldots=d_{2 k-1}$ . Итак, все $d_{i}$ равны между собой, откуда $d_{i}=n-1$ , что и (вспомним про Аню!) требовалось доказать.

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

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

Задача 025

01.01.2025 от

2016 мальчиков выбирают девочек. Каждый мальчик выбирает ровно двух девочек: одну блондинку и одну брюнетку. Оказалось, что для любого натурального числа $k, 1 \leq k \leq 80$ , найдется девочка (блондинка или брюнетка), которую выбрали ровно $k$ мальчиков. Докажите, что какие-то два мальчика выбрали одних и тех же девочек.

Подсказка

Зафиксируйте 80 вершин со степенями $1,2, \ldots, 80$ соответственно.

Решение

Рассмотрим двудольный (мульти)граф, где вершины — блондинки и брюнетки, а рёбра — выборы мальчиков. В нем 2016 рёбер. Надо доказать, что есть два ребра с общими концами.

Зафиксируем 80 вершин со степенями $1,2, \ldots, 80$ соответственно; назовём их выбранными. Пусть имеется $k$ рёбер, оба конца которых выбраны; также назовём их выбранными. Тогда рёбер, один конец которых выбран, будет $1+2+\ldots+80-2 k$ . С другой стороны, их не больше, чем 2016- $k$ , откуда $k \geq 1+2+\ldots+80-2016=1224$ .

Рассмотрим выбранные вершины со степенями $1,2, \ldots, 26$ . Из них исходит не более $1+2+\ldots+26=351$ выбранного ребра. Значит, остальные 54 вершины связывают не менее $1224-351=873$ рёбер. С другой стороны, пусть среди этих 54 вершин $x$ блондинок и $54-x$ брюнеток, и между любыми двумя вершинами — не более одного ребра. Тогда всего между этими вершинами не более $x(54-x) \leq(x+54-x)^{2} / 2^{2}=27^{2}=729$ рёбер. Противоречие.

Задача 027

01.01.2025 от

В кружке занимаются $2 n$ человек. Кружок называется однородным, если у каждого кружковца одно и то же количество друзей в кружке. Докажите, что кружок однороден тогда и только тогда, когда при любом его разбиении на две команды по $n$ учеников количества пар друзей в командах равны.

Подсказка

Разделите вершины на две равные группы $A$ и $B$ .

Решение

Рассмотрим граф знакомств. Разделим вершины на две равные группы $A$ и $B$ . Пусть $S_{A}\left(S_{B}\right)$ — сумма степеней вершин, входящих в $A(B)$ , а $R$ — количество знакомств между учениками из $A$ и $B$ . Тогда количество знакомств $N_{A}$ внутри $A$ равно $\left(S_{A}-R\right) / 2$ . 1) Пусть у всех одинаковое число друзей. Тогда при разбиении на равные группы $A$ и $B, S_{A}=S_{B}$ , следовательно, $N_{A}=N_{B}$ . 2) Пусть не у всех одинаковое число друзей. Составим $A$ из $n$ вершин с наименьшими степенями. Тогда $S_{A}<S_{B}$ , и, следовательно, $N_{A}<N_{B}$ .

Задача 028

01.01.2025 от

В стране 300 городов. Некоторые пары городов соединены дорогами. Оказалось, что из каждого города выходит ровно 10 дорог. Страна распалась на две республики Иксия и Игрекия. В Иксии оказалось 200 городов, а в Игрекии — 100 городов. Оказалось, что число дорог, соединяющих города Иксии, равно $x$ , а дорог, соединяющих города Игрекии, равно $y$ . Чему может быть равно $x-y$ ?

Подсказка

Пусть из Иксии в Игрекию ведёт $z$ дорог. Сколько ещё дорог в республиках?

Решение

Ответ. 500. Решение. Пусть из Иксии в Игрекию ведёт $z$ дорог. Тогда из городов Иксии в совокупности выходит $10 \cdot 200=2 x+z$ дорог, а из городов Игрекии — $10 \cdot 100=2 y+z$ дорог ( $x$ и $y$ умножаются на 2 , так как каждая дорога, соединяющая города одной республики, считается тут дважды). Вычитая два полученных равенства и деля результат пополам, получаем ответ.

Задача 040

01.01.2025 от

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

Подсказка

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

Решение

Ответ: 5.

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