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

Задача 069

01.01.2025 от

В стране 100 городов. Некоторые из них соединены дорогами, причем между любыми двумя городами есть не более одной дороги. Города пронумерованы числами от 1 до 100. Петя совершил 100 путешествий по дорогам страны, каждый раз начиная путешествия в разных городах. Все свои путешествия он осуществляет по следующему правилу. Оказавшись в каком-либо городе $A$ , Петя находит среди всех городов, соединенных с $A$ , город $B$ с наименьшим номером. Если город $B$ уже был посещен в этом путешествии, или из $A$ вообще нет ни одной дороги, путешествие тут же заканчивается в $A$ . $B$ противном случае, Петя перемещается из $A$ в $B$ и продолжает путешествие по этому же правилу. Оказалось, что совершив 100 путешествий, Петя посетил все города страны поровну раз. При каком наибольшем количестве дорог в стране такое возможно?

Подсказка

Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города $i<100$ и город $i$ соединен только с городом 100.

Решение

Ответ: 2500.

Решение. Оценка. Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города $i<100$ и город $i$ соединен только с городом 100. Предположим, что все города были посещены хотя бы три раза. Тогда есть хотя бы два города, которые соединены только с городом 100 . Но наибольший из таких городов может быть посещен только один раз (когда путешествие начинается в нем). Если все города посещены 1 раз, то в стране вообще нет дорог, что нас не устраивает. Значит, все города посещены ровно два раза. Удалим город 100 и город $i$ , соединенный только с ним. Мы удалили не более $98+1$ дорог. Для оставшейся части страны всё ещё верно утверждение, что при путешествиях с началом в каждом из городов, все города посещаются поровну раз, так как города $i$ и 100 посещались ровно 2 раза в путешествиях с началом $i$ и 100. Повторяя такие рассуждения, мы будем удалять пары городов, удаляя не более $97,95, \ldots, 1$ дорог. Значит, изначально в стране было не более $1+3+\ldots+99=$ 2500 дорог. Пример: при $i \leqslant 50$ город $i$ соединим с городами с номерами хотя бы $101-i$ . Также соединим попарно города с номерами, большими 50. Тогда начиная в городе $i$ мы перемещаемся в город $101-i$ и останавливаемся. Значит, все города будут посещены дважды. И количество ребер равно $1+2+\ldots+50+50 \cdot 49 / 2=2500$ .

Задача 072

01.01.2025 от

Нечётная раскраска графа — это такая раскраска множества его вершин в несколько иветов, что любые две соседние вершины покрашены в разный цвет и при этом для каждой вершины можно указать цвет, в который покрашено нечётное число её соседей. Барон Мюнхгаузен нарисовал граф и создал нечётную раскраску его вершин в 1022 ивета. «Вы можете мне не поверить, друзья, — говорит барон, — но на этом графе не существует нечётных раскрасок с меньшим числом цветов. Однако после того как я добавил всего одну вершину и соединил её с некоторыми вершинами этого графа, для нечётной раскраски мне понадобилось всего три цвета». Не обманывает ли нас барон?

Подсказка

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

Решение

Ответ: не обманывает.

Решение. Возьмем полный граф на 1022 вершинах, которые условно будем называть «толстыми». В середине каждого ребра поставим новую вершину (иными словами, мы заменяем каждое ребро этого графа на двузвенный путь). Новые вершины будем считать «тощими». Возьмём произвольную нечётную раскраску полученного графа. Для любых двух толстых вершин $A$ и $B$ рассмотрим тощую вершину $C$ , соединенную с ними. Так как у вершины $C$ в этом графе всего две соседние вершины (это как раз $A$ и $B$ ), эти вершины должны быть окрашены в разный цвет. Итак, любые две толстые вершины должны быть разного цвета, следовательно, в раскраске используется не меньше 1022 цветов.

Теперь добавим к нашему графу одну новую вершину и соединим её со всеми тощими. На полученном графе нам хватит трёх цветов: все толстые вершины красим в красный цвет, тощие — в зелёный, новую — в синий. Эта раскраска удовлетворяет требованию нечётности, поскольку у каждой красной вершины 1021 зелёный сосед, у каждой зелёной имеется один синий сосед, а у синей вершины имеется $\frac{1}{2} \cdot 1022 \cdot 1021$ , т.е. нечётное число зелёных соседей.

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

Задача 074

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

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

Задача 076

01.01.2025 от

Архипелаг состоит из 1000 островов, некоторые пары которых соединены мостами, причём от любого острова можно добраться по мостам до любого другого. Оказалось, что для любых четырёх островов $A, B, C, D$ таких, что есть мост между $A$ и $B$ , между $B$ и $C$ , между $C$ и $D$ , также есть мост между $A$ и $C$ или между $B$ и $D$ . Докажите, что есть остров, соединённый мостами со всеми остальными.

Подсказка

Решение

Рассмотрим граф, в котором вершины — архипелаги, ребра — мосты. Выберем в этом графе вершину наибольшей степени, назовем её $B$ . Предположим, что $B$ соединена не со всеми вершинами. Так как граф связный, какая-то вершина, соединенная с $B$ , должна быть соединена с вершиной, не соединенной с $B$ (иначе мы не доберемся от $B$ до тех вершин, с которыми она не соединена). Пусть $B$ соединена с $C, C$ соединена с $D$ , но $B$ не соединена с $D$ . Теперь для любой вершины $A$ , которая соединена с $B$ , мы можем применить условие задачи для пути $A-B-C-D$ и получить, что $A$ соединена с $C$ (так как между $B$ и $D$ нет ребра). Таким образом, $C$ соединена с $B$ , со всеми вершинами, с которыми соединена $B$ , и ещё с вершиной $D$ . Это значит, что её степень больше степени $B$ , что противоречит нашему изначальному выбору. Таким образом, вершина наибольшей степени обязана быть соединена со всеми остальными вершинами.

Задача 085

01.01.2025 от

Подсказка

Решение

Задача 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$ , если он не проиграл раньше.

Задача 087

01.01.2025 от

В первый день $2^{n}$ школьников играли в пинг-понг «навылет»: сначала сыграли двое, затем победитель сыграл с третьим, победитель этой пары — с четвёртым и т.д., пока не сыграл последний школьник (ничьих в пинг-понге не бывает). Во второй день те же школьники разыграли кубок: сначала произвольно разбились на пары и сыграли в парах, проигравшие выбыли, а победители снова произвольно разбились на пары и сыграли в парах, и т.д. Оказалось, что наборы игравших пар в первый и во второй день были одни и те же (возможно, победители были другие). Найдите наибольшее возможное значение $n$ .

Подсказка

Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Согласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир и выберем те партии, победители которых до этого не выигрывали (например, такова первая партия).

Решение

Ответ. 3.

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

Теперь рассмотрим тот же граф как граф кубкового турнира. Если из него выбросить висячие вершины, останется граф турнира на $2^{n-1}$ победителях первого этапа. Он, очевидно, является путём лишь при $n \leq 3$ , в противном случае победитель турнира будет иметь степень не меньше 3 . Значит, $n \leq 3$ .

Осталось привести пример при $n=3$ . Пусть участники пронумерованы от 1 до 8 и пары в кубке таковы (первым указан проигравший, вторым победитель): $1-2,3-4,5-6,7-8,2-4,6-8$ , $4-8$ тогда при игре навылет пары могли быть такими (победитель снова указан вторым): $1-2$ , $2-4,3-4,4-8,7-8,8-6,6-5$ .

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