Все задачи — Страница 8 — Задачи на Графы

Задача 071

01.01.2025 от

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

Подсказка

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

Решение

Ответ: $\frac{1}{2} \cdot 100 \cdot 98=4900$ .
Решение. Оценка. Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами. Значит, по крайней мере из 99 селений выходит хотя бы один телеграфный провод. Тогда имеется не менее 50 проводов, и количество дорог не больше разности чисел $\frac{1}{2} \cdot 100 \cdot 99=4950$ (число дорог в полном графе) и 50 (число проводов, которые заменяют собой некоторые «несостоявшиеся» дороги). Пример. Разобьем селения произвольным образом на пары, каждое селение соединим дорогами со всеми остальными, кроме парного ему.

Задача 072

01.01.2025 от

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

Подсказка

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

Решение

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

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

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

Задача 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$ , противоречие. Индукционный переход доказан.

Задача 074

01.01.2025 от

B стране $n$ городов, один из которых является столицей. Между некоторыми парами городов налажено авиасообщение. Расстоянием между городами называется минимальное количество перелетов, которые необходимо совершить, чтобы добраться от одного города до другого. Правительство хочет закрыть авиасообщение между некоторыми парами городов, чтобы расстояние от столицы до любого другого города не изменилось. Известно, что существует нечетное количество способов, которыми правительство может это сделать. В том числе, считается способ, в котором не закрывается ничего.

Докажите, что нельзя, стартовав в некотором городе и совершив нечетное число перелетов, вернуться обратно в него.

Подсказка

Для каждой вершины посчитаем расстояние от неё до столицы. Очевидно, что для двух вершин, соединенных ребром, эти расстояния отличаются не более чем на 1.

Решение

Рассмотрим граф, в котором вершины — города, ребра — наличие сообщения. Для каждой вершины посчитаем расстояние от неё до столицы. Очевидно, что для двух вершин, соединенных ребром, эти расстояния отличаются не более чем на 1. Предположим, что в графе нашелся нечетный цикл. Пройдем по этому циклу и будем следить за изменением расстояния при переходе по каждому ребру. Так как цикл нечетный, то если каждый раз расстояние менялось ровно на 1 , то придя в исходную вершину мы бы получили расстояние другой четности, чего быть не может. Следовательно, хотя бы один раз при проходе по ребру цикла расстояние не изменилось. То есть существует ребро $e$ , что оба конца этого ребра находятся на одинаковом расстоянии от столицы.

Назовем набор ребер хорошим, если при удалении из графа всех ребер, кроме ребер этого набора, расстояние до столицы не изменятся. Докажем, что хорошие наборы можно разбить на пары следующим образом: если в наборе есть $e$ , то уберем $e$ из набора, а если нет $e$ , то добавим. То есть надо доказать, что если мы удалили несколько рёбер и расстояния не изменились, то при удалении/добавлении ребра $e$ расстояния также не изменятся. Про добавление ребра $e$ утверждение очевидно, так как от добавления ребра расстояния не могут уменьшиться, а увеличиться не могут, так как они равны расстояниям в графе, в котором никакие ребра не удалены. Предположим, что при удалении $e$ расстояние от какого-то города $X$ до столицы $M$ увеличилось. Тогда кратчайший путь от $X$ до $M$ проходил через $e$ . Но такого не может быть, ведь расстояния от концов $e$ до $M$ одинаковы, и мы могли, не проходя по ребру $e$ , добраться от $X$ до $M$ за меньшее число шагов.

Таким образом, все наборы разбились на пары, то есть их четное число. Противоречие.

Задача 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$ общих знакомых — остальные люди этой группы и Дима. Также, Дима единственный, кто знаком со всеми, значит у них с Сашей разное число знакомых.

Задача 076

01.01.2025 от

Архипелаг состоит из 1000 островов, некоторые пары которых соединены мостами, причём от любого острова можно добраться по мостам до любого другого. Оказалось, что для любых четырёх островов $A, B, C, D$ таких, что есть мост между $A$ и $B$ , между $B$ и $C$ , между $C$ и $D$ , также есть мост между $A$ и $C$ или между $B$ и $D$ . Докажите, что есть остров, соединённый мостами со всеми остальными.

Подсказка

Решение

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

Задача 077

01.01.2025 от

В кружке $n$ ребят, причём любые двое ребят либо дружат, либо враждуют. Оказалось, что у каждого из ребят ровно 10 врагов в этом же кружке, причём если $A$ дружит с $B$ , но враждует с $C$ , то $B$ и $C$ враждуют. Найдите все возможные значения $n$ .

Подсказка

Если все враги одного из двух друзей являются врагами другого, то у любых двух друзей одни и те же враги. При этом друг моего друга — мой друг, иначе у меня был бы враг, который не враждует с моим другом.

Решение

Ответ. 11, 12, 15, 20.

Решение. Если все враги одного из двух друзей являются врагами другого, то у любых двух друзей одни и те же враги. При этом друг моего друга — мой друг, иначе у меня был бы враг, который не враждует с моим другом. Поэтому все кружковцы разбиваются на группы, где каждый дружит с каждым, причём в каждой группе на 10 человек меньше, чем во всём кружке. Пусть в каждой группе $k$ человек. Тогда 10 должно делиться на $k$ , а всего ребят в кружке — $10+k$ . С другой стороны, если $m$ — делитель числа 10 , то кружок, состоящий из $m+1$ группы размера $k=10 / m$ , где любые двое из одной группы дружат, а из разных групп — враждуют, удовлетворяет условию задачи Перебирая теперь делители числа 10, получаем ответ.

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

Задача 079

01.01.2025 от

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

Подсказка

Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека $A, B, C$ .

Решение

Ответ: 3.

Решение. Оценка. Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека $A, B, C$ . Пусть $A$ тот, у кого больше всех знакомых. Если у $A$ один знакомый, то у кого-то из $B$ и $C$ тоже есть один знакомый (сам $A$ ), но тогда у $A$ не больше всех знакомых. Следовательно, у $A$ два знакомых и он знаком с $B$ и $C$ . Пусть $D$ — человек, который ушел перед $A$ . Так как у $A$ хотя бы два знакомых из $B, C$ и $D$ , то у $D$ их должно быть не менее 3 . Значит, $D$ знаком с $A, B$ и $C$ . Но тогда и у $A$ три знакомых. Противоречие.

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

Задача 080

01.01.2025 от

В классе учится $n$ человек. Некоторые из них образуют кружки по интересам, наборы учащихся ни в каких двух кружках не совпадают. Известно, что каждый школьник ходит хотя бы в два кружка, но также есть два кружка, в которые он не ходит. Докажите, что можно выбрать пару школьников $A$ и $B$ такую, что найдутся кружок, в который ходят оба школьника, кружок, в который ходит только $A$ , кружок, в который ходит только $B$ , и кружок, в который не ходят ни $A$ , ни $B$ .

Подсказка

Решение

Пусть всего школьники образовали $n$ кружков. Обозначим максимальное число кружков, в которые ходит один школьник, через $k$ , а минимальное — через $s$ . Без ограничения общности можно считать, что $k \leq n-s$ . В самом деле, пусть $k>n-s$ . Тогда запишем каждого школьника во все кружки, в которые он не ходит, и исключим его из всех кружков, в которые он ходит. Пара искомых школьников при этом останется той же самой, но $s$ превратится в $n-k, k$ превратится в $n-s$ , и неравенство $n-s \leq n-(n-k)$ , равносильное неравенству $k \geq n-s$ , будет выполнено.

Пусть Петя — школьник, который ходит в $k$ кружков. Посмотрим на два какие-то кружка, в которые он не ходит. Они состоят из разных наборов участников, значит, найдется школьник Вася, который ходит в один из этих кружков, а в другой не ходит.

Теперь посмотрим на все кружки, в которые Петя ходит. Вася не может ходить во все эти кружки, иначе бы он ходил в большее число кружков, чем Петя. Вася должен ходить хотя бы в один из этих кружков, иначе Вася не ходит в большее число кружков, чем количество кружков, в которые ходит Петя, что противоречит предположению $k \leq n-s$ . Значит, Петя и Вася подходят под условие.