Ориентированные графы — Задачи на Графы

Задача 006

01.01.2025 от

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

Подсказка

Рассмотрите вершину с наибольшей степенью.

Решение

Рассмотрим город $A$ , из которого можно попасть в наибольшее число городов. Если есть город $B$ , в который нельзя попасть из $A$ , то из $B$ можно попасть в $A$ , а, значит, и во все города, в которые можно попасть из $A$ . Получается противоречие: из $B$ можно попасть в большее число городов, чем из $A$ . Значит из города $A$ можно попасть во все города.

Задача 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$ ребер.

Задача 016

01.01.2025 от

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

Подсказка

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

Решение

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

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

Задача 020

01.01.2025 от

В классе поровну мальчиков и девочек, и все ученики разного роста. Оказалось, что если мальчик дружит с девочкой, то он дружит и со всеми девочками выше неё; и наоборот — если девочка дружит с мальчиком, то она дружит и со всеми мальчиками выше него. Учитель физкультуры хочет выстроить детей в ряд, начиная с мальчика, так, чтобы любые двое соседей в ряду были друзьями разного пола. Оказалось, что количество способов это сделать — натуральное число $N$ , делящееся на 101. Каким наименьшим количеством нулей может оканчиваться десятичная запись числа $N$ ?

Подсказка

Для начала докажите лемму.

Лемма. $N=\left(a_{1} a_{2} \ldots a_{k}\right)^{2}$ , где $a_{1}, \ldots, a_{k}$ — некоторая последовательность неотрицательных целых чисел такая, что $i \geq a_{i} \geq a_{i+1}-1$ при всех $i=1,2, \ldots, k-1$ .

Решение

Ответ. 48.
Решение: Назовём исследуемые расстановки легальными. Пусть $k$ количество мальчиков. Пример получается при $k=101$ , когда все дружат. Действительно, тогда $N=(101!)^{2}$ , причём 2 входит в 101 ! хотя бы в 50 степени, а 5 — в степени $[101 / 5]+\left[101 / 5^{2}\right]=24$ , ибо $101<5^{3}$ . Значит, $N$ оканчивается ровно 48 нулями.

Сначала выведем оценку из леммы. Поскольку $N$ натурально, $a_{1} \geq 1$ , то есть $a_{1}=1$ . Если $N$ делится на 101 , то одно из чисел $a_{1}, \ldots, a_{k}$ делится на $101-$ скажем, это $a_{j}$ . Из условий $a_{i-1} \geq a_{i}-1$ следует, что среди чисел $a_{1}, \ldots, a_{j-1}$ встретятся все числа от 1 до 100 , то есть $N$ делится на ( $100!)^{2}$ и, следовательно, на $10^{48}$ .

Осталось доказать лемму. Числа $a_{k-i}$ будут определяться так. Выкинем из компании $i$ самых маленьких девочек и $i$ самых больших мальчиков. Тогда $a_{k-i}$ — это количество оставшихся мальчиков, знакомых со всеми оставшимися девочками. Из этого описания немедленно следуют условия на $a_{i}$ , указанные в лемме.

Индукция по $k$ . При $k=1$ имеем $N=1=a_{1}$ . Пусть теперь $k>1$ . Рассмотрим самую маленькую девочку $d$ ; пусть $M$ — множество мальчиков, которые с ней дружат, $|M|=a_{k}$ . Заметим, что $M$ состоит из $a_{k}$ самых высоких мальчиков.

В любой легальной расстановке перед $d$ стоит мальчик $m$ из $M$ , а после неё — либо мальчик $m^{\prime}$ из $M$ , либо никто. Так как $m^{\prime}$ , если он существует, знаком со всеми девочками, то после выбрасывания пары ( $m, d$ ) из расстановки получится легальная расстановка оставшихся детей. Наоборот, в любую легальную расстановку $2(k-1)$ детей, отличных от $m$ и $d$ , пару ( $m, d$ ) можно вставить либо перед произвольным $m^{\prime} \in M\{m\}$ , либо в конец, то есть $a_{k}$ способами.

Далее, поскольку $m$ дружит со всеми, для всех $m \in M$ после выкидывания пары ( $m, d$ ) останутся «одинаковые» компании детей (научным языком, графы их дружб изоморфны). Поэтому в них будет поровну легальных расстановок, и эти количества будут по предположению индукции иметь вид $N^{\prime}=\left(a_{1} a_{2} \ldots a_{k-1}\right)^{2}$ . Итак, для каждого из $a_{k}$ мальчиков из $M$ в каждую из $N^{\prime}$ перестановок можно вставить пару ( $m, d$ ) ровно $a_{k}$ способами. Значит, $N=N^{\prime} a_{k}^{2}$ , что и требовалось.

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

Задача 038

01.01.2025 от

Город Сугробск представляет собой квадрат со стороной $100 n$ метров, разбитый прямыми улицами на $n^{2}$ одинаковых кварталов ( $n$ — чётное натуральное число, большее 2). На каждой из $2 n+2$ улиц, идущих по сторонам кварталов от края до края города, введено одностороннее движение. На соседних параллельных улицах движение направлено в разные стороны. В одном из углов города находится автопарк; обе выходящие из этого угла улицы направлены от автопарка. Снегоуборочная машина выезжает из автопарка и начинает убирать снег. Чтобы не портить дорожное покрытие, по уже убранным участкам (кроме перекрестков) машина не ездит. В конце смены машина должна прибыть в противоположный угол города. Какое наибольшее расстояние она может проехать?

Подсказка

Докажите, что наименьшее количество не пройденных отрезков есть $4 n-4$ .

Решение

Ответ. $100\left(2 n^{2}-2 n+4\right)$ .

Решение: Будем считать, что машина едет из левого нижнего в правый верхний угол, а все стороны маленьких квадратов равны 1 . Всего горизонтальных единичных отрезков $n(n+1)$ , тогда всего единичных отрезков $2 n(n+1)$ . Докажем, что наименьшее количество не пройденных отрезков есть $4 n-4$ . Тогда наибольшее количество пройденных отрезков не более $2 n(n+1)-(4 n-4)=2 n^{2}-2 n+4$ . Введем прямоугольную систему координат: левый нижний угол будет иметь координату $(0,0)$ , а верхний правый — ( $n, n$ ). Рассмотрим прямые вида $x+y=k+1 / 2$ , где $k$ целое число от 0 до $2 n-1$ . Очевидно, что ее пересекает поровну вертикальных и горизонтальных отрезков, ввиду симметрии относительно $x=y$ . Так как начальная и конечная точка нашего маршрута находятся по разные стороны от этой прямой, то маршрут пересечет ее нечетное число раз, а, следовательно, один из отрезков будет не пройденным. Итого уже не пройденных отрезков будет 2n. Рассмотрим прямую $x+y=k+1 / 2$ где $k-$ четное дислот че ниных отрезка, пескащих ра сли ренлу. По условию, если аетно, то оба дин ных отрезка ориентированы из ооласти старта в ооласть финиша, а если $a$ — нечетно, то наооорот. Всего отрезков первого типа $-k+2$ , а отрезков второго типа $-k$ . Заметим, что пройденных отрезков первого типа должно быть ровно на один больше, чем пройденных отрезков второго типа. Однако, точки $(k, 0)$ и $(0, k)$ лежат на границе, поэтому в них входит ровно один отрезок, следовательно, для каждой этой точки, один из выходящих отрезков будет не пройденным. Остается не более $k$ отрезков первого типа, и не более $k-1$ отрезков второго типа. Т.е. эта прямая пересекает хотя бы три не пройденных отрезка. Таких прямых $(n-2) / 2$ , и они дают еще $n-2$ не пройденных отрезков. Аналогично, рассматривая прямую $x+y=k-1 / 2$ , где $k$ — четное число от $n+1$ до $2 n-2$ , найдем еще $n-2$ не пройденных отрезков. Всего не пройденных отрезков будет хотя бы $2 n+2(n-2)=4 n-4$ . Оценка доказана.

Приведем пример. Удалим все ребра вида ( $n, 2 k-1)-(n, 2 k)$ при $1 \leq k \leq n / 2$ и вида ( $2 k, 0)-(2 k+1,0)$ при $1 \leq k \leq(n-2) / 2$ . Всего удалено $n-1$ ребро. Далее удалим пути ( $2 k, n)-(2 k, n-1)-(2 k+1, n-1)-(2 k+1, n)$ при $1 \leq k \leq(n-2) / 2$ , а также пути $(0,2 k-1)-(1,2 k-1)-(1,2 k)-(0,2 k)$ при $2 \leq k \leq(n-2) / 2$ . Итого в этих путях $3 n-9$ ребер. Наконец, удалим пути $(0,0)-(0,1),(1,0)-(1,2)-(0,2)$ и $(0, n-1)-(1, n-1)-(1, n)$ . Всего удалено $4 n-4$ ребра. Все не граничные вершины имели степень входяших и исходяших ребер ровно по два, поэтому после удаления они остались равными. Легко проверить, что у всех вершин, лежащих строго на стороне квалрата стапо по одному входнему и исхолящему ребру У начальной и конечной вершины стало по одному исходящему и одному входящему ребру. Пример построен.

Задача 041

01.01.2025 от

На конгресс приехало 100 ученых, каждый из которых сделал доклад. В конце каждый заявил, что ему понравилось ровно 75 докладов, сделанных его коллегами на конгрессе. Докажите, что найдутся трое, каждому из которых понравились доклады двух других.

Подсказка

Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75).

Решение

Будем говорить, что ученые А и В взаимны, если им понравились доклады друг друга. Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75). Рассмотрим всех, кому понравился доклад A , и всех, чьи доклады понравились А. Так как тех и других не менее, чем по 75, а всего ученых, кроме А, ровно 99, то найдется хотя бы 51 человек, взаимный с А. Возьмём группу из ровно 51 такого учёного (назовем её s). Для любого ученого из s найдется как минимум $75-49=26$ ученых из s, доклады которых ему понравились. Рассмотрим в s такого ученого B , доклад которого понравился наибольшему числу его коллег из s. Таких будет не менее 26. Тогда так как B понравились не менее, чем 26 докладов из s , среди учёных из s найдется C , который взаимен с B . Тогда $\mathrm{A}, \mathrm{B}$ и C попарно взаимны, что и требовалось доказать.

Задача 064

01.01.2025 от

Докажите, что у любого конечного множества $A$ натуральных чисел существует подмножество $B$ , удовлетворяющее следующим условиям: если $b_{1}, b_{2} \in B$ различны, то ни одно из чисел $b_{1}, b_{2}$ не делится на другое и ни одно из чисел $b_{1}+1, b_{2}+1$ не делится на другое, а также для любого $a \in A$ найдётся $b \in B$ такое, что или $b$ делится на $a$ , или $a+1$ делится на $b+1$ .

Подсказка

Решение

Рассмотрим двуцветный ориентированный граф, у которого вершинами будут элементы множества $A$ , и от вершины $b$ к вершине $a$ идет синяя стрелка, если $b$ делится на $a$ , и красная, если $a+1$ делится на $b+1$ . Тогда мы хотим выбрать независимое подмножество вершин $B$ такое, что в любую вершину множества $A \backslash B$ ведет стрелка из $B$ .

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

Задача 068

01.01.2025 от

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

Подсказка

Выкидывание вершины с рёбрами не увеличивает степени остальных, потому степень каждого следующего выходящего (на момент выхода) хотя бы на 2 меньше предыдущей.

Решение

Ответ. 51 человек.

Решение: Оценка. Рассмотрим граф с 99 вершинами, рёбра соответствуют знакомствам. Выкидывание вершины с рёбрами не увеличивает степени остальных, потому степень каждого следующего выходящего (на момент выхода) хотя бы на 2 меньше предыдущей. Поэтому их степени не больше $98,96, \ldots 4,2$ соответственно. Но удалить вершину степени 2 невозможно, так как есть ещё ненулевые степени, а вершины степени 1 и 0 не подходят по условию. Таким образом, из комнаты выйдет не более 48 человек.

Пример. Пусть человек с номером $1 \leqslant k \leqslant 48$ знаком с людьми с номерами от $2 k+1$ до 99, других знакомств нет. Уходить они будут по порядку от 1 до 48 . На момент ухода $k$ -го человека: ему не знакомы только $k$ следующих за ним, остальным из этих 48 — хотя бы $k+1$ следующих и предыдущий, а последним 51 — хотя бы 50 , что тоже не меньше $k+2$ .