Деревья — Задачи на Графы

Задача 004

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 010

01.01.2025 от

В лагере $2012^{2012}$ детей, у каждого не более трех друзей. Всегда ли можно их построить в ряд так, чтобы между любыми двумя друзьями стояло не более чем 2012 человек?

Подсказка

Попробуйте построить контрпример в виде дерева

Решение

Ответ: Не всегда.

Решение: Пусть Петя знаком с двоими, каждый из его знакомых — с двоими новыми, каждый из этих четверых — снова с двоими новыми и т.д., пока не перезнакомим всех $2012^{2012}$ детей. В получившемся «двоичном дереве» знакомств на $k$ -ом от Пети ярусе (кроме, возможно, самого последнего) — $2^{k}$ детей, поэтому ярусов в нем не больше, чем $m$ , где $m$ таково, что $2^{m-1}<2012^{2012}<2^{m}$ . Поскольку $2^{11}=2048>2012, m<11 \cdot 2012$ . Допустим, нам удалось построить детей нужным образом. Возьмем самого левого и самого правого. Между ними в построенном нами дереве есть путь длины не более $2 m<22 \cdot 2012$ . Но между любыми двумя соседями на этом пути в строю стоят не более 2012 человек. Поэтому длина строя должна быть не больше 2013•22•2012, что, очевидно, намного меньше, чем $2012^{2012}$ . Противоречие.

Задача 014

01.01.2025 от

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

Подсказка

Предположите, что в графе есть цикл. Все ли рёбра цикла используются?

Решение

Если граф дорог — дерево, у него $n-1$ ребро, и утверждение задачи очевидно. Если же нет, выбросим самую дорогую из дорог, входящих в циклы. Поскольку можно считать, что эта дорога не используется (обходной путь по циклу не дороже), стоимости проезда между городами эта процедура не изменит. Будем повторять ее, пока не останется дерево.

Задача 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 больше максимального числа на соответствующем пути в первом дереве).

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

Задача 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$ ) четно.

Задача 050

01.01.2025 от

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

Подсказка

Решение

Пусть $M_{1} D_{1}, \ldots, M_{2015} D_{2015}$ — наши пары. Каждую девочку $D_{i}$ соединим с другой девочкой, знакомой с $M_{i}$ . В результате получится граф на вершинах $D_{1}$ , $\ldots, D_{2015}$ с 2015 рёбрами. Нам нужно покрасить этот граф правильным образом в три цвета, это и будет искомая покраска девочек. Рассмотрим компоненту связности построенного графа, пусть в ней $n$ вершин, тогда и рёбер в ней тоже $n$ (Мы провели по одному ребру из каждой вершины этой компоненты связности, из вершин вне компоненты рёбра в нее не входят). Если есть вершина степени 1 , удалим ее, эту вершину можно будет легко докрасить после покраски остальных вершин компоненты. После серии таких операций наша компонента связности будет иметь минимальную степень вершины 2 , а значит, это будет простой цикл, который мы легко покрасим в три цвета.

Задача 051

01.01.2025 от

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

Подсказка

Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл.

Решение

Ответ. Вася.

Решение. Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл. Значит, концы цепи длины 2 соединять с другими точками нельзя. Стратегия Васи: после каждого хода Пети соединять ту же красную точку с какой-то синей, которая ещё не соединена ни с какой другой. Тогда после каждой пары ходов Пети и Васи число не соединённых с другими синих точек будет уменьшаться на 2 , и после 50 -го хода Васи каждая синяя точка будет концом цепи длины 2. Своим 51-м ходом Петя создаст цепь длины 3 и проиграет.

Задача 053

01.01.2025 от

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

Подсказка

Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если $k \geqslant 751$ , то в одном из пауков выбраны все 4 города, что противоречит условию.

Решение

Ответ. $k=750$ . Решение. Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если $k \geqslant 751$ , то в одном из пауков выбраны все 4 города, что противоречит условию.

Оценка. Рассмотрим граф: вершины — города, рёбра — дороги. Если граф не связный, будем проводить по ребру между компонентами связности, пока он не станет связным. Ясно, что такая процедура не увеличит искомое число $k$ и не добавит в граф циклы.

Итак, мы можем считать, что рассматриваемый граф — дерево. Индукцией по $n$ докажем, что в дереве на $n$ вершинах можно выбрать $k \geqslant 3 n / 4$ вершин так, чтобы выполнялось условие задачи. Такое множество вершин будем называть хорошим.

База: $n=1,2,3,4$ очевидна.
Переход: от всех меньших $n$ к $n$ . Подвесим дерево за вершину и рассмотрим вершину $v$ самого нижнего уровня. Если у ее предка $u$ не менее трёх потомков, то выкинем $u$ и всех ее потомков.

В оставшемся дереве выберем хорошее множество и добавим всех потомков $u$ . Полученное множество будет хорошим для исходного дерева, и в нём не менее $\frac{3}{4}(n-4)+3$ вершины.

Если у вершины $u$ ровно 2 потомка $v$ и $w$ , то рассмотрим её предка $t$ . Выкинем вершины $u, v, w$ и $t$ и, если понадобится, добавим рёбра для того, чтобы получилось дерево. В получившемся дереве выберем хорошее множество из не менее $\frac{3}{4}(n-4)$ вершин, после чего добавим к нему вершины $u, v$ и $w$ .

Итак, мы можем считать, что у любой вершины с нижнего уровня предок имеет степень ровно 2. Пусть $v$ — вершина нижнего уровня, $u$ — её предок, $w$ — предок $u$ . У всех потомков (не обязательно прямых) $w$ степень 1 или 2 . Если у $w$ всего $k \geqslant 3$ потомков (не обязательно прямых). Выкинем $w$ и всех её (не обязательно прямых) потомков. В оставшемся графе хорошее множество содержит не менее $3(n-k-1) / 4$ вершин. Добавим к ним всех $k$ потомков $w$ . Получим хорошее множество из не менее $3(n-k-1) / 4+k \geqslant 3 n / 4$ вершин в исходном дереве.

Наконец, если $k \leqslant 2$ , то единственные потомки $w$ — это $u$ и $v$ . Пусть $t$ — предок $w$ . Выкинем вершины $u, v, w$ и $t$ . В получившемся графе выберем хорошее множество из не менее $\frac{3}{4}(n-4)$ вершин, после чего добавим к нему вершины $u, v$ и $w$ .