Пути в графах — Задачи на Графы

Задача 001

01.01.2025 от

В стране $n \geq 2$ городов, каждые два из которых соединены прямым автобусным сообщением в обе стороны. Сколькими способами можно попасть из города $A$ в другой город $B$ , проехав на автобусе ровно $k$ раз? Маршрут может проходить через любой город (в том числе $A$ и $B$ ), а также использовать любой рейс между городами более одного раза.

Подсказка

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

Решение

Ответ: $\frac{(n-1)^{k}-(-1)^{k}}{n}$ .

Обозначим через $a_{k}$ количество маршрутов длины $k$ из $A$ в $B$ . Выедем из города $A$ и будем ехать каждый раз в произвольный город. На каждом шаге у нас будет ровно $n-1$ вариант, поэтому всего маршрутов длины $k-1$ выходящих из $A$ , будет ровно $(n-1)^{k-1}$ . Заметим, что каждый такой маршрут либо заканчивается в городе $B$ , либо можно сделать еще один ход в $B$ . Поэтому $(n-1)^{k-1}=a_{k}+a_{k-1}(*)$ . Теперь искомую формулу можно доказать методом математической индукции: базой является $a_{1}=1$ , а переход следует из формулы (*).

Задача 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$ ребро, и утверждение задачи очевидно. Если же нет, выбросим самую дорогую из дорог, входящих в циклы. Поскольку можно считать, что эта дорога не используется (обходной путь по циклу не дороже), стоимости проезда между городами эта процедура не изменит. Будем повторять ее, пока не останется дерево.

Задача 016

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 036

01.01.2025 от

В стране 100 городов и 1000 дорог; каждая дорога соединяет ровно 2 города. Известно, что из любого города можно добраться в другой (возможно, через некоторые другие города) не больше, чем за 8 ч. Мужик на желтой «Калине» хочет объехать все города и вернуться в исходный город. За какое минимальное время он гарантированно может это сделать?

Подсказка

Для построение примеры выделите одну из вершин. А часть рёбер сделайте очень длинными.

Решение

Ответ: 99.8 часов.

Решение: Оценка. Граф городов и дорог не полный, значит, кратчайший путь между какими-то двумя городами проходит через какой-то город. Пусть, например, кратчайший путь от $x_{1}$ до $x_{3}$ проходит через $x_{2}$ . Тогда, цикл $x_{1} \rightarrow x_{2} \rightarrow x_{3} \rightarrow \ldots \rightarrow x_{99} \rightarrow x_{100}$ требует не более $99 \cdot 8$ часов, так как переезд от $x_{1}$ к $x_{3}$ и все остальные переходы требуют не более 8 часов каждый.

Пример. Все города связаны с $x_{2}$ дорогами, требующими 4 часов каждая. Остальные города либо связаны дорогами, либо нет, чтобы общее число дорог равнялось 1000. Все дороги между ними требуют 8 часов. Легко видеть, что оценка достигается.

Задача 037

01.01.2025 от

Каждые два города страны Гельбии соединены односторонним авиарейсом. Региональные бароны превратили страну в федерацию двух республик с общей столицей (каждый город, кроме столицы, принадлежит ровно одной из республик, а столица — обеим). Министерство путей сообщения посчитало количество $N$ маршрутов, проходящих по каждому городу всей страны по одному разу (не возвращающихся в исходный город), а также аналогичные количества $N_{1}$ и $N_{2}$ для каждой из республик. Докажите, что $N \geq N_{1} N_{2}$ .

Подсказка

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

Решение

Построим ориентированный граф, вершины которого соответствуют городам, а рёбра — дорогам. Пусть вершина $w$ соответствует столице, $A$ и $B$ — графы, соответствующие республикам. Сначала сформулируем несложную лемму.

Пусть $P$ и $Q$ — два непересекащихся пути в полном ориентированном графе Т. Тогда существует путь $R$ на вершинах этих двух путей, в котором все вершины пути $P$ следуют в порядке пути $P$ , а все вершины пути $Q$ следуют в порядке пути $Q$ . Этот факт нетрудно доказать индукцией по длине пути $Q$ , вставляя по очереди его вершины в путь $P$ . Отметим, что лемма верна и для случая, когда один из путей $P$ и $Q$ или они оба — пустые (из 0 вершин). Назовём путь $R$ из леммы склейкой путей $P$ и $Q$ .

Рассмотрим любые гамильтоновы пути $P$ графа $A$ и $Q$ графа $B$ . Эти пути, очевидно, имеют вид $P=P_{1} w P_{2}$ и $Q=Q_{1} w Q_{2}$ (возможно, какие-то из участков $P_{1}, P_{2}, Q_{1}$ и $Q_{2}$ — пустые). По лемме существует путь $R_{1}$ — склейка $P_{1}$ и $Q_{1}$ и путь $R_{2}$ — склейка $P_{2}$ и $Q_{2}$ . Отметим, что если путь $R_{1}$ непустой, то он кончается либо последней вершиной пути $P_{1}$ , либо последней вершиной пути $Q_{1}$ , то есть, из последней вершины пути $R_{1}$ выходит ребро в $w$ . Аналогично, либо путь $R_{2}$ — пустой, либо из $w$ выходит стрелка в первую вершину пути $R_{2}$ . Тогда $R=R_{1} w R_{2}$ — гамильтонов путь в графе $T$ , в котором вершины подграфа $A$ следуют в порядке пути $P$ , а вершины подграфа $B$ следуют в порядке пути $Q$ . Каждой паре гамильтоновых путей ( $P, Q$ ) очевидно, соответствует свой путь $R$ .

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

Задача 057

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$ за меньшее число шагов.

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

Задача 059

01.01.2025 от

В стране $N$ городов. Некоторые пары городов соединены двусторонними авиарейсами, каждый рейс имеет цену, большую 1000 рублей, причём из любого города можно добраться до любого другого (возможно, с пересадками). Компания публикует сборник, в котором для каждой из $N(N-1) / 2$ пар городов указана минимальная цена, которую надо заплатить, чтобы добраться от одного из них до другого; в конце сборника указывается сумма всех этих $N(N-1) / 2$ чисел. В некоторый момент компания уменьшила стоимость одного из рейсов на 1000 рублей. Докажите, что итоговая сумма в новом сборнике будет отличаться от старой не более, чем на $250 N^{2}$ .

Подсказка

Обозначим два города, между которыми уменьшили стоимость рейса, через $X$ и $Y$ . Пусть $A$ — множество городов, из которых после уменьшения дешевле добраться до $X$ , чем до $Y$ , в том числе в множество $A$ входит сам город $X$ . Пусть $B$ множество городов, из которых добраться до $Y$ не дороже, чем до $X$ , в том числе в множество $B$ входит сам город $Y$ . Что будеь если при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ .

Решение

Пусть при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ . Тогда, если из $X$ сразу полететь в $V$ по пути наименьшей стоимости, мы заплатим меньшую цену за весь путь: ведь цена перелета между $X$ и $Y$ все равно осталась положительной, и хотя бы эту цену мы сэкономим. Аналогичны рассуждения для двух вершин из множества $B$ . Поэтому путь минимальной стоимости между двумя вершинами одного множества не содержит рейс из $X$ в $Y$ .

Обозначим количество городов в множестве $A$ через $a$ . Тогда в множестве $B$ всего $N-a$ городов. Стоимость самого дешевого пути между городами одного множества, как было показано выше, не уменьшилась. Значит, лишь между $a(N-a)$ парами городов из разных множеств стоимость самого дешевого пути могла уменьшиться. Это количество пар не больше $N^{2} / 4$ , по неравенству между средними арифметическим и геометрическим.

Новый самый дешевый путь между городами из разных множеств проходит по удешевленному ребру $X Y$ не более одного раза, а до удешевления стоимость такого же пути была не ниже стоимости самого дешевого пути между этими городами. Поэтому для каждой пары городов из разных множеств стоимость самого дешевого пути уменьшилась не более, чем на 1000. Значит, итоговая сумма будет отличаться от старой не более, чем на $250 N^{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$ вершин.