Циклы в графах — Задачи на Графы

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

Задача 004

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 009

01.01.2025 от

В день Св. Валентина $n$ влюбленных пар провели два однокруговых турнира по пинг-понгу — один для юношей, другой для девушек. Юноша и девушка из каждой пары вместе выиграли $n-1$ игру. Докажите, что количество троек юношей ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ , равно количеству таких троек девушек.

Подсказка

Попробуйте сравнить не количество циклических троек, а количество оставшихся троек.

Решение

Занумеруем все пары числами от 1 до $n$ . Пусть в паре с номером $k$ юноша выиграл $a_{k}$ , а девушка $-n-1-a_{k}$ партий. Заметим, что тогда девушка из этой пары проиграла $a_{k}$ партий.

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

Рассмотрим теперь пару номер $k$ . Легко видеть, что количество троек юношей, в которых юноша из $k$ -й пары выиграл обе партии равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ . Поскольку в каждой нециклической тройке юношей есть ровно один юноша, одержавший две победы, количество таких троек равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ . Аналогично, количество троек девушек, в которых девушка из $k$ -й пары обе партии проиграла, также равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ и, следовательно, количество нециклических троек девушек также равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ .

Задача 013

01.01.2025 от

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

Подсказка

Попробуйте доказать лемму. Если в связном ориентированном графе $k$ вершин и хотя бы $2 k-1$ ребро (причем некоторые пары вершин могут быть соединены ребрами в обоих направлениях), то одно из ребер можно удалить без потери связности.

Решение

Ответ. 197.
Решение: Построим ориентированный граф, вершины которого соответствуют городам, а ребра — дорогам (направление ребра будет соответствовать направлению дороги). Любые две вершины соединены не более, чем одним ориентированным ребром. Полученный граф будет связным (из любой вершины можно попасть в любую другую), но при удалении любого ребра связность теряется.

Построим пример такого графа со 197 ребрами. Он будет состоять из вершин $A, B, \mathrm{C}_{1}, \ldots, \mathrm{C}_{98}$ , и ребер $A \rightarrow C$ , а также $C \rightarrow B_{i}$ и $B_{i} \rightarrow A$ для всех $i$ . Нетрудно проверить, что этот граф подходит.

Докажем лемму: если в связном ориентированном графе $k$ вершин и хотя бы $2 k-1$ ребро (причем некоторые пары вершин могут быть соединены ребрами в обоих направлениях), то одно из ребер можно удалить без потери связности.

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

Перейдем к доказательству утверждения задачи. Из связности графа следует, что в нем есть (ориентированный) цикл $C_{1} \rightarrow C_{2} \rightarrow \ldots \rightarrow C_{m} \rightarrow C_{1}$ . Понятно, что $m \geq 3$ и нет никаких ребер между входящими в цикл вершинами, кроме ребер самого цикла (иначе такое ребро можно удалить без потери связности). Также отметим, что из любой не входящей в цикл вершины А существует не более одного ребра, выходящего к вершинам цикла (если таких ребер хотя бы два, то одно из них можно удалить без потери связности). Аналогично, существует не более одного ребра, выходящего из вершин цикла в А.

Заменим все вершины цикла на одну вершину $C$ и для любой другой вершины $A$ проведем ребро $A \rightarrow C$ , если существует одно из ребер $A \rightarrow C_{i}$ и ребро $C \rightarrow A$ , если существует одно из ребер $C_{i} \rightarrow \mathrm{~A}$ . Получится новый связный ориентированный графG’, в котором ровно на $m$ ребер меньше, чем в исходном графе и удаление любого ребра нарушает связность. (Однако, в этом графе возможно наличие двух ребер разного направления между двумя вершинами.) В графе G’ ровно $100-m+1$ вершина и, по доказанному выше утверждению, не более $2(100-m+1)-2=200-2 m$ ребер. Следовательно, в исходном графе было не более, чем $200-m \leq 200-3=197$ ребер.

Задача 014

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 017

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 019

01.01.2025 от

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

Подсказка

Предположите противное. Докажите, что нет встречных рёбер. Затем попробуйте стягивать рёбра.

Решение

Будем доказывать индукцией по числу $n$ вершин. База для $n=3$ и $n=4$ проверяется без труда. Пусть для всех графов с менее чем $n$ вершинами условие выполнено, а в графе $G$ с $n$ вершинами и исходящими степенями 3 не нашлось двух непересекающихся циклов.

Предположим, что в $G$ есть встречные ребра между вершинами $v$ и $w$ . Тогда в $G$ есть цикл $v w$ , и в $G-\{v, w\}$ есть цикл, так как в нем из каждой вершины выходит хотя бы одно ребро. Следовательно, в $G$ нет встречных ребер.

Предположим, что в $G$ есть ребро $u v$ такое, что ни из какой вершины $x \in V(G)$ не выходят ребра в обе вершины $u$ и $v$ . Тогда стянем ребро $u v$ : удалим в $G$ вершины $u$ и $v$ и добавим новую вершину $w$ , в которую входят ребра из тех вершин, из которых входили ребра в $u$ и $v$ , и выходят ребра в те вершины, в которые выходили ребра из $v$ . Обозначим полученный граф через $G^{\prime}$ . В $G^{\prime} n-1$ вершина и степень каждой вершины равна 3 , поэтому для него выполнено индукционное предположение. Но тогда и в $G$ есть два непересекающихся цикла, так как если цикл в $G^{\prime}$ проходил через $w$ , то в $G$ этот проход можно заменить на проход через $v$ или $u v$ .

Осталось разобрать случай, когда каждое ребро имеет «предка», то есть вершину, из которой выходят ребра в оба конца этого ребра. Пусть $v$ — вершина наименьшей входящей степени (обозначим эту степень $d^{-}(v)$ ). Очевидно, $d^{-}(v) \leq 3$ .

(1) $d^{-}(v)=0$ . Тогда ребро, исходящее из $v$ , не имеет предка.
(2) $d^{-}(v)=1$ . Тогда ребро, входящее в $v$ , не имеет предка.
(3) $d^{-}(v)=2$ . Пусть есть ребра $u v$ и $w v$ . Тогда $u$ должно быть предком для $w v$ , а $w$ — для $u v$ , но тогда есть ребра $v w$ и $w v$ , а этот случай мы уже разобрали.
(4) $d^{-}(v)=3$ . Тогда все вершины имеют входящую степень 3. Пусть в вершину $x$ входят ребра $u x, v x, w x$ . Предком каждого из этих ребер должна быть $u, v$ или $w$ . Тогда в индуцированном подграфе на вершинах $u, v, w$ в каждую вершину входит хотя бы одно ребро, а так как в $G$ нет встречных ребер, вершины $u, v, w$ образуют цикл длины 3. Заметим, что вершины, в которые ведут ребра из $x$ , также образуют цикл длины 3 (так как мы можем обратить все ребра и повторить те же рассуждения). $B G$ нет встречных ребер, поэтому мы нашли два непересекающихся цикла.

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

Задача 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 часов. Легко видеть, что оценка достигается.

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