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

Задача 065

01.01.2025 от

Некоторые из 2017 городов страны соединены прямыми двусторонними авиарейсами так, что из каждого города можно добраться до любого другого. Правительство хочет объявить $k$ городов стратегически значимыми так, чтобы из любого города (включая стратегически значимые), совершив ровно один перелет, можно было попасть в стратегически значимый город. При каком наименьшем $k$ это наверняка можно будет сделать?

Подсказка

Очевидно, достаточно разобрать случай, когда граф — дерево (в произвольном связном графе можно выделить дерево, содержащее все его вершины; если $k$ стратегически значимых вершин будет достаточно для этого дерева, их будет достаточно и для исходного графа).

Докажем, что в графе с $n \geq 3$ вершинами можно указать несколько вершин и выделить из них несколько стратегически значимых так, что каждая выделенная вершина будет смежна с выделенной стратегически значимой, доля стратегически значимых среди выделенных будет не больше $2 / 3$ и после удаления выделенных вершин граф останется связным.

Рассмотрим две вершины $A$ и $B$ , путь между которыми содержит наибольшее количество рёбер.

Решение

Ответ. При $k=1344$ . Решение. Введём граф городов и авиарейсов. Для начала приведём пример графа, в котором меньше чем 1344 стратегически значимыми вершинами не обойтись. Пусть в графе имеются вершины $A$ , а также $B_{k}, C_{k}$ и $D_{k}, k=1,2, \ldots, 672$ ; для каждого $k$ проведём рёбра между вершиной $A$ и $B_{k}, B_{k}$ и $C_{k}$ , $C_{k}$ и $D_{k}$ . Легко видеть, что этот граф связен. Поскольку вершина $D_{1}$ связана только с вершиной $C_{1}$ , то вершина $C_{1}$ должна быть объявлена стратегически значимой. Кроме того, применяя условие задачи для вершины $C_{1}$ получаем, что либо вершина $B_{1}$ , либо вершина $D_{1}$ должна быть объявлена стратегически значимой. Итак, из вершин $B_{1}, C_{1}, D_{1}$ хотя бы две вершины должны быть стратегически значимыми. Рассуждая аналогично для каждой тройки $B_{k}, C_{k}, D_{k}$ , получаем требуемое.

Докажем теперь, что 1344 стратегически значимыми вершинами можно обойтись. Очевидно, достаточно разобрать случай, когда граф — дерево (в произвольном связном графе можно выделить дерево, содержащее все его вершины; если $k$ стратегически значимых вершин будет достаточно для этого дерева, их будет достаточно и для исходного графа).

Рассмотрим две вершины $A$ и $B$ , путь между которыми содержит наибольшее количество рёбер. Пусть $X$ — последняя перед $B$ вершина на пути из $A$ в $B$ . Очевидно, $B$ соединена только с $X$ . Если $X$ соединена с какимито висячими вершинами, кроме $B$ , выделим $X$ и все смежные с ней висячие вершины, а стратегически значимыми среди них объявим $X$ и $B$ . Очевидно, удаление этих вершин не нарушит связности графа, и стратегически значимые составляют среди них не более $2 / 3$ .

Пусть $B$ — единственная висячая вершина, соединённая с $X$ . Рассмотрим последнюю вершину $Y$ на пути из $A$ в $X$ . Если все отличные от $B$ вершины, путь из которых в $A$ проходит через $Y$ , смежны с $Y$ , можно выделить эти вершины, $Y, X$ и $B$ , а стратегическими среди них объявить $X$ и $Y$ .

Наконец, разберём случай, когда путь из $A$ в $Y$ можно продолжить несколькими путями $Y X_{i} B_{i}$ длины 2 (путями большей длины продолжить не удастся в силу максимальности выбранного выше пути из $A$ в $B$ ). Пусть таких путей $k$ . Тогда нужно выделить все вершины этих путей и все висячие вершины, смежные с $Y$ , а стратегически значимыми объявить $Y$ и все $X_{i}$ . При этом из графа будет удалено не менее $2 k+1$ вершин, из которых $k+1$ стратегически значимых, а $\frac{k+1}{2 k+1} \leq \frac{2}{3}$ .

Будем продолжать эту деятельность, пока от графа не останется огрызок, содержащий не более двух вершин. Если вершин не осталось вообще, то мы объявили стратегически значимыми не более $[2 \cdot 2017 / 3]=1344$ вершин, и процесс завершился. Если осталась одна вершина, то на предыдущем шаге нашего алгоритма она называлась $A$ и была соединена с вершиной $X$ или $Y$ , которую объявили стратегически значимой, значит, для нее условие выполнено, и стратегически значимыми было объявлено не более $[2 \cdot 2016 / 3]=1344$ вершин. Если же осталось две вершины, то, во-первых, они смежны, так как граф связности не теряет; во-вторых, одна из этих двух вершин была соединена с вершиной $X$ или $Y$ , объявленной стратегически значимой на предыдущем шаге. Поэтому достаточно объявить стратегически значимой лишь одну из этих двух вершин, чтобы условие выполнялось. Значит, и в этом случае стратегически значимыми будет объявлено не более $[2 \cdot 2015 / 3]+1=1344$ вершин.

Задача 070

01.01.2025 от

B стране $n$ городов, некоторые пары из них соединены дорогами с двухсторонним движением. В некоторых городах построены школы, назовём такие города важными. Оказалось, что 1) из каждого города можно добраться до любого другого; 2) каждый не важный город соединён дорогой с важным городом. Для какого наименьшего $k$ всегда можно закрыть все дороги, кроме некоторых $k$ , на ремонт так, чтобы эти два условия сохранились?

Подсказка

Можно оставить только остовное дерево.

Решение

Ответ: $n-1$ . Решение. Рассмотрим граф, вершинами которого являются города, ребрами — дороги. Понятно, что $k \geqslant n-1$ , в противном случае граф на оставшихся ребрах не будет связным. Докажем, что в этом графе всегда можно выделить остовное дерево, удовлетворяющее условиям. Будем последовательно удалять ребра из графа. Пусть в графе к текущему моменту есть цикл, проходящий по вершинам $C_{1} C_{2} \ldots C_{m} C_{1}$ . Предположим, что мы не можем удалить ребро $C_{i} C_{i+1}$ (считаем, что $C_{m+1}=C_{1}$ ) с сохранением всех условий. Тогда один из городов $C_{i}$ и $C_{i+1}$ должен быть важным, а другой — не важным. Поэтому если мы не можем удалить ни одно из ребер цикла, то в нем чередуются важные и не важные города. В этом случае удалим любое ребро из нашего цикла. Каждый не важный город будет по-прежнему соединен с важным. В какой-то момент в графе не останется циклов, а все условия будут выполнены. Поэтому оставшийся граф дерево, и ребер в нем ровно $n-1$ .

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

Задача 086

01.01.2025 от

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

Подсказка

a) Условие означает, что граф — дерево. Петя выбирает произвольную вершину. От каждой вершины существует ровно один путь в выбранную. Все рёбра на этом пути он ориентирует в сторону выбранной вершины.

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

Решение

Рассмотрим граф, вершинами которого являются города, а рёбрами — дороги.
a) Условие означает, что граф — дерево. Петя выбирает произвольную вершину. От каждой вершины существует ровно один путь в выбранную. Все рёбра на этом пути он ориентирует в сторону выбранной вершины.

Первым ходом Петя перемещает туриста в выбранную вершину. Все ориентированные пути ведут к туристу. Вася разворачивает одно ребро. Турист идёт по нему. Ясно, что все пути снова ведут к нему. Вася снова разворачивает одно ребро и так далее. Поэтому у Пети всегда есть ход и он не проиграет.
б) По условию граф связен и содержит цикл. Будем доказывать индукцией по количеству вершин, что Вася может гарантировать себе победу, причём для любой изначальной расстановки стрелок перед его ходом (включая «невозможный» случай, когда все стрелки ведут из вершины, где стоит фишка перед первым ходом Васи).

База — простые циклы. Пусть в простом цикле $A_{1} A_{2} \ldots A_{n}$ как-то расставлены стрелки на рёбрах и турист смог сделать ход, пойдя из $A_{1}$ в $A_{2}$ . Вася будет разворачивать стрелки перед ним. Поэтому турист не сможет идти в обратную сторону. Допустим, турист смог дойти до $A_{1}$ . Тогда перед ним разворачивают стрелку, и ему некуда идти. Петя проиграл.

Шаг индукции. Граф не является простым циклом. Выберем в нём цикл С минимальной длины. Ясно, что $C$ — простой и не содержит ребёр внутри себя. Поэтому есть вершины вне $C$ . Выберем из них вершину $V$ с максимальным расстоянием до $C$ . Обозначим граф без $V$ буквой $G$ . Ясно, что $G$ связен и содержит цикл.

По предположению индукции в $G$ есть выигрышная стратегия для Васи при любой ориентации рёбер. Внутри $G$ Вася будет следовать ей. Так как в $G$ Петя проигрывает, то турист вынужден будет когда-то пойти в $V$ . Тогда Вася развернёт эту стрелку. Турист выйдет из $V$ , а Вася сделает любой допустимый ход в $G$ . Турист пойдёт внутри $G$ . Сейчас у Васи опять есть выигрышная стратегия в $G$ , которой он и будет следовать. Турист снова будет вынужден зайти в $V$ , уменьшив количество стрелок, идущих из $G$ в $V$ . В конце концов они кончатся, и Петя проиграет в $G$ , если он не проиграл раньше.

Задача 092

01.01.2025 от

В стране 20 городов, причем между любыми двумя городами проложена дорога. Министерство путей сообщения может закрыть на ремонт любую дорогу из четырех, образующих циклический маршрут. Может ли после нескольких таких операций остаться только 19 дорог?

Подсказка

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

Решение

Ответ: Нет.

Решение. Понятно, что после каждой из указанных операций остается связный граф, а в конце должно получиться дерево. Вершины дерева можно раскрасить в два цвета так, чтобы у всех его ребер были концы разных цветов. Если мы будем по очереди добавлять убранные ребра (сначала — убранное последним, потом — предпоследним и т.д.), то это свойство не нарушится (т.к. 4 — четное число). Но вершины полного графа, который по условию был в начале, так раскрасить нельзя.

Задача 095

01.01.2025 от

На турнир приехало 100 человек. Из любых пяти из них можно по крайней мере двумя способами выбрать трех попарно знакомых. Докажите, что среди них есть по крайней мере 4850 пар знакомых.

Подсказка

Решение

Рассмотрим граф, вершинами которого являются участники турнира, а ребрами — пары участников, незнакомых между собой. Если в этом графе есть треугольник $A B C$ , то в любой пятерке $A B C D E$ участники $D$ и $E$ должны быть знакомы между собой, и каждый из них должен быть знаком с двоими из тройки $A B C$ . Тогда пар знакомых получается не меньше, чем $97 \times 96 / 2+2 \times 97=97 \times 50=4850$ . Дальше будем считать, что треугольников нет. Пусть есть цикл $A B C D$ длины 4. Добавляя сюда произвольного участника $E$ , находим, что он дружит со всеми участниками из этого цикла, $A$ дружит с $C$ и $B$ дружить с $D$ . Таким образом, каждый цикл длины 4 в нашем графе является компонентой связности. Заметим далее, что в нашем графе нет незамкнутых путей длины 4: если есть такой путь $A B C D E$ , то в пятерке $A B C D E$ нет двух троек попарно знакомых. Поэтому нет и циклов длины больше 4 , то есть каждая компонента связности нашего графа — либо цикл длины 4, либо дерево. Но в такой ситуации ребер у этого графа не больше, чем вершин, то есть не больше 100. Соответственно, пар знакомых не меньше, чем $100 \times 99 / 2-100=4850$ .

Задача 099

01.01.2025 от

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

Подсказка

Отметим в нашем графе $G$ любую вершину $a$ и построим дерево поиска в глубину $T$ с корнем $a$ .

Решение

Отметим в нашем графе $G$ любую вершину $a$ и построим дерево поиска в глубину $T$ с корнем $a$ .

Пронумеруем вершину $a$ числом 0 и будем добавлять в дерево и нумеровать вершины по следующему принципу: если в дереве есть вершины с номерами от 1 до $k$ , то рассмотрим вершину с наибольшим номером, из которой выходит хотя бы одно ребро в вершину, не принадлежащую уже построенному дереву, добавим любое из таких рёбер в дерево, и новой вершине присвоим номер $k+1$ . Все ребра дерева $T$ ориентируем от меньшего номера к большему.

Пусть $t(x)$ — номер вершины $x$ при построении дерева $T$ . Докажем, что все требования задачи выполняются. Очевидно, в остовном дереве графа на 2009 вершинах как раз 2008 ребер, так что мы поставили 2008 стрелочек. Пусть $u v$ — ребро исходного графа $G$ , причем $t(u)<t(v)$ . Если $u v$ входит в $T$ , всё в порядке. В противном случае вершина $v$ подвешена в $T$ к вершине $v_{1} \neq u$ . Так как в графе $G$ вершина $v$ смежна с $u$ , то по построению дерева $t\left(v_{1}\right)>t(u)$ , и $t(v)>t\left(v_{1}\right)$ . Рассмотрим момент, когда добавлялась вершина $v_{1}$ . Так как в этот момент в дереве еще нет смежной с $u$ вершины $v$ , то по построению вершина $v_{1}$ подвешена в $T$ к вершине $v_{2}$ , где $t\left(v_{1}\right)>t\left(v_{2}\right) \geq t(u)$ . И так далее, пока очередная вершина $v_{m}$ не окажется совпадающей с $u$ (это случится, потому что номера $t\left(v_{i}\right)$ монотонно убывают, и все они не меньше, чем $t(u)$ ). Искомый путь $u=v_{m} \rightarrow v_{m-1} \rightarrow \ldots \rightarrow v_{1} \rightarrow v$ построен.