6 класс — Страница 2 — Задачи на Графы

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

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

Задача 062

01.01.2025 от

B стране $n$ городов, один из которых является столицей. Между некоторыми парами городов налажено авиасообщение. Расстоянием между городами называется минимальное количество перелетов, которые необходимо совершить, чтобы добраться от одного города до другого. Правительство хочет закрыть авиасообщение между некоторыми парами городов, но чтобы расстояние от столицы до любого другого города не изменилось. Известно, что существует нечетное количество способов, которыми правительство может это сделать. В том числе считается способ, в котором не закрывается ничего.
Докажите, что нельзя, стартовав в некотором городе и совершив нечетное число перелетов, вернуться обратно в него.

Подсказка

Подвесим граф за вершину-столицу С. Вспомним, что вершины $i$ -го яруса определяются в точности как те вершины, расстояние от которых до C равно $i$ .

Решение

Введём граф, в котором вершины — города, рёбра — наличие авиасообщения. Подвесим граф за вершину-столицу С. Вспомним, что вершины $i$ -го яруса определяются в точности как те вершины, расстояние от которых до C равно $i$ . В таком графе рёбра могут быть либо внутри одного яруса, либо между ярусами с номерами, отличающимися на 1. Мы рассматриваем множества ребер, при удалении которых сохраняется ярус каждой вершины в нашем графе, будем называть их интересными. Если некоторое ребро $v$ соединяет две вершины одного яруса, то при включении или исключении $v$ интересность множества ребер не меняется. Таким образом, все интересные множества разбиваются на пары, что противоречит условию. Следовательно, в графе нет ребер, соединяющих вершины одного яруса. Тогда в любом цикле ярусы соседних вершин отличаются на 1 , тем самым они имеют разную четность. Значит, любой цикл в данном графе имеет четную длину, что и требовалось.

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

Задача 074

01.01.2025 от

Докажите, что нельзя, стартовав в некотором городе и совершив нечетное число перелетов, вернуться обратно в него.

Подсказка

Для каждой вершины посчитаем расстояние от неё до столицы. Очевидно, что для двух вершин, соединенных ребром, эти расстояния отличаются не более чем на 1.

Решение

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

Задача 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$ , что противоречит нашему изначальному выбору. Таким образом, вершина наибольшей степени обязана быть соединена со всеми остальными вершинами.

Задача 079

01.01.2025 от

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

Подсказка

Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека $A, B, C$ .

Решение

Ответ: 3.

Решение. Оценка. Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека $A, B, C$ . Пусть $A$ тот, у кого больше всех знакомых. Если у $A$ один знакомый, то у кого-то из $B$ и $C$ тоже есть один знакомый (сам $A$ ), но тогда у $A$ не больше всех знакомых. Следовательно, у $A$ два знакомых и он знаком с $B$ и $C$ . Пусть $D$ — человек, который ушел перед $A$ . Так как у $A$ хотя бы два знакомых из $B, C$ и $D$ , то у $D$ их должно быть не менее 3 . Значит, $D$ знаком с $A, B$ и $C$ . Но тогда и у $A$ три знакомых. Противоречие.

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

Задача 090

01.01.2025 от

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

Подсказка

Пусть нет игрока, знакомого со всеми остальными. Возьмем любого игрока А. По условию есть игрок Б, знакомый со всеми игроками, кроме А.

Решение

Будем называть участников турнира игроками. Пусть нет игрока, знакомого со всеми остальными. Возьмем любого игрока А. По условию есть игрок Б, знакомый со всеми игроками, кроме А. Уберем игрока Б. Со всеми оставшимися может быть знаком только игрок A : иначе игрок $\mathrm{C} \neq \mathrm{A}$ , знакомый со всеми оставшимися, будет знаком и с Б, что противоречит нашему предположению. Назовем таких игроков А и Б антиподами. Из проведенного рассуждения следует, что при нашем предположении у каждого игрока А есть единственный антипод Б, для которого А в свою очередь является антиподом. Но это значит, что все игроки должны разбиться на пары антиподов, а это невозможно, ибо число игроков нечетно. Противоречие.