Деревья и остовные деревья
по каждой теме
каждый день
решения
«Школково» — ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В школе запустили кружков. За один вопрос можно про любые два кружка узнать, какие ученики ходят в оба эти кружка, а какие
ходят ровно в один из них (без указания в какой именно). За какое наименьшее количество вопросов можно узнать списки посещающих
каждый кружок?
Подсказка 1
Число 20 выглядит произвольным. Скорее всего, задача имеет общее решение для произвольного количества кружков. Например, сколько вопросов необходимо задать, чтобы узнать списки 3 кружков?
Подсказка 2
Необходимо 3 вопроса, соответственно про (1, 2), (2, 3) и (3, 1) кружок. Отсюда может появиться предположение, что ответом на задачу является количество кружков, то есть 20. Почему этого количества вопросов будет достаточно?
Подсказка 3
Поскольку мы уже уже выдвинули предположение о том, что условие задачи верно для любого количества кружков, поэтому алгоритм нахождения списков несложно строить индуктивно. Как показать, что меньшего количества вопросов не хватит в общем случае?
Подсказка 4
Потребуем, чтобы весь список каждого кружка был уникален. Например, этого можно добиться, если количество учеников будет равно 2^20, причем каждый будет посещать уникальное множество кружков. Как удобно изображать множество вопросов, заданных в алгоритме?
Подсказка 4
Каждый из вопросов связывает пару из вопросов, поэтому является отношением на данном множестве. Отношение удобно отображать на графах. Пусть в графе каждому кружку в соответствие поставлена вершина, парой соединены те вершины, которые соответствуют кружкам для которых существует вопрос, в котором они учувствовали. Какой вид имеет данный граф?
Подсказка 5
В нем существует компонента, которая является суть путем. Что теперь нужно для того, чтобы закончить доказательство?
Подсказка 6
Можно доказать, что найдутся множества кружков A и B, для которых найдется школьник, который ходит только в кружки множества A, и школьник, который ходит только в кружки множества B, по ответам неотличимы. Найдите соответствующие множества среди кружков, соответствующих вершинам найденного пути.
Пример. Спросим про пары
и
а затем про все пары вида
где
Докажем, что за первые три
вопроса мы выясним составы кружков
и
Посмотрим на любого человека. Если он не ходит ни в один из этих кружков, то его имя
не будет названо ни разу, и это ни с чем не перепутаешь. Если он входит только в один кружок, то его имя всплывёт в двух вопросах, как
посещающего один кружок. При этом по этим двум парам мы восстановим, в какой кружок он ходит. Если он ходит в два кружка, то
однажды он появится, как посещающий два кружка, и дважды — как посещающий один из двух. В этой ситуации легко
вычисляется, куда он ходит. Если он ходит во все, то во всех парах покажется, как посещающий оба, и тоже получится
вычислить, что он во все ходит. То есть про любого человека мы поймём, куда он ходит, а это и значит, что вычислим
составы всех кружков. Теперь, зная, кто ходит в первый кружок, после вопроса
легко вычисляем, кто ходит в кружок
Оценка. Будем считать, что в школе учеников. Каждому ученику сопоставим уникальное подмножество кружков и
направим его ровно в кружки из его подмножества. Предположим, что после
вопросов удалось выяснить составы
всех кружков. Это значит, что мы научились различать всех учеников. Рассмотрим граф, вершины которого — кружки.
Соединим вершины ребром, если мы спросили про эту пару кружков. В графе
вершин и
рёбер, значит, хотя бы в
одной компоненте связности рёбер меньше, чем вершин, то есть эта компонента связности — дерево. А вершины дерева
можно правильным образом покрасить в два цвета. Обозначим множества вершин первого и второго цвета
и
Тогда
школьник, который ходит только в кружки множества
и школьник, который ходит только в кружки множества
по ответам не отличимы. Во всех вопросах про эту компоненту связности оба назывались как ходящие в один из двух
кружков.
Ошибка.
Попробуйте повторить позже
В дереве есть рёбра, а все вершины имеют степень 1 или 2. Сколько в этом дереве может быть висячих вершин?
Подсказка 1:
Пусть имеется k вершин степени 1. Как можно выразить сумму степеней всех вершин через n и k, где n — общее количество вершин?
Подсказка 2:
Сумма степеней вершин равна k + 2(n − k) = 2n − k. А можно ли выразить эту же сумму как-то иначе, например, через количество рёбер?
Подсказка 3:
Вспомните, что в дереве количество рёбер на единицу меньше количества вершин. Осталось использовать это для составления уравнения, откуда найти все возможные значения k.
Ошибка.
Попробуйте повторить позже
В королевстве имеется сеть дорог, соединяющих города. Из любого города можно по дорогам попасть в любой другой, но между каждой парой городов есть только один путь. Область — это группа городов, между которыми можно перемещаться, не проходя через другие города. Король выбрал несколько областей так, что каждая пара из них имеет общий город. Докажите, что все выбранные области имеют общий город.
Подсказка 1:
Ясно, что нужно перевести условие на язык графов. Вершины – города, рёбра – дороги, граф – дерево, а каждую область будем рассматривать некоторый связный подграф.
Подсказка 2:
Нужно показать, что выбранные области имеют общую вершину. Хорошей идеей будет постепенное удаление некоторых лишних вершин до тех пор, пока не удастся наткнуться на нужную.
Подсказка 3:
Удалять вершины нужно так, чтобы сохранялось условие задачи. Проще всего это сделать с листьями дерева. Подумайте, почему в какой-то момент удалить лист не получится?
Ясно, что задачу можно переформулировать в терминах графов: вершины — города, а ребра — дороги. Из условия известно, что граф —
дерево, а каждая область — это дерево какого-то подграфа. Рассмотрим произвольный лист дерева. Если его удаление не
нарушает условие пересечения выбранных областей, удалим его и повторим процедуру. Так как количество вершин в графе
конечно, процесс обязательно закончится. Пусть при удалении листа условие пересечения нарушается для поддеревьев
и
Рассмотрим смежную с
вершину
(если её нет, то осталась одна вершина — общая для всех). Тогда,
поскольку нарушение наблюдается, хотя бы одно из поддеревьев, скажем
не содержит
Это возможно если
состоит только из
Так как все области пересекаются с
содержится во всех поддеревьях, как и требовалось
доказать.
Ошибка.
Попробуйте повторить позже
Докажите, что можно выбрать не более половины вершин связного графа так, чтобы каждая из оставшихся вершин была смежна с одной из выбранных.
Рассмотрим в связном графе любое остовное дерево и разобьём вершины на слои по расстоянию от какой-то вершины. Так как каждое ребро дерева соединяет соседние слои, то если взять все вершины из чётных слоёв, каждая вершина из нечётного слоя будет с ними соединена, и наоборот, поэтому можно выбрать ту из двух частей, где вершин не больше половины, и тогда каждая из оставшихся вершин будет соединена хотя бы с одной выбранной.
Ошибка.
Попробуйте повторить позже
Дано некоторое натуральное Какое наименьшее количество элементов может быть в множестве, обладающем следующим свойством:
для любого
найдутся два числа из множества с разностью
Напомним, что числа Фибоначчи — это последовательность
чисел, заданная начальными условиями
и рекуррентным соотношением
Рассмотрим множество состоящее из чисел Фибоначчи с четными индексами, и нуля:
где а
— наименьшее четное число, не меньшее
Размер этого множества
- Если
четно,
то мы должны взять
Тогда
Размер множества
-
Если
нечетно,
то мы должны взять
Тогда
Размер множества
Обе эти формулы можно объединить в одну:
Проверим, что это множество удовлетворяет условию. Нам нужно показать, что для любого найдутся два элемента в
разность которых равна
- 1.
-
Для любого
(где
) разность
реализуется, так как
и
- 2.
-
Используем известное тождество для чисел Фибоначчи:
Для любого
такого, что
нам нужно, чтобы в множестве
были элементы
и
Согласно построению
это так.
Таким образом, все требуемые разности от до
можно получить. Минимальный размер множества не превосходит
Докажем, что размер множества не может быть меньше
Пусть
— произвольное множество, удовлетворяющее условию.
Рассмотрим подмножество требуемых разностей с нечетными индексами:
Количество элементов в этом подмножестве равно
Определим граф вершины которого — элементы множества
Для каждой разности
в графе должно
существовать как минимум одна пара вершин
такая, что
Проведем ребро между
и
и пометим его числом
Используем свойство чисел Фибоначчи: для любого
Это означает, что ни одно ребро в нашем
графе не может быть представлено как сумма или разность других ребер с меньшими весами. Из этого следует, что в
графе, не может быть циклов. Таким образом, этот граф является лесом. Таким образом, количество вершин не менее
Ошибка.
Попробуйте повторить позже
В связном графе чётное число вершин. Докажите, что можно убрать из него часть рёбер так, что степень каждой вершины станет нечётной.
Подсказка 1.
Заметим, что если удалить ребро, сохраняющее связность, то утверждение задачи не изменится, а количество рёбер уменьшится. К чему в итоге приведёт такой процесс?
Выделим в графе остовное дерево Все рёбра графа, не входящие в
удалим. Теперь будем выбирать, какие рёбра остовного дерева
оставить, а какие — удалить. Подвесим дерево
за произвольную вершину
Будем определять судьбу рёбер, двигаясь от листьев к
корню, индукцией по высоте поддерева.
Для каждой вершины рассмотрим ребро
соединяющее
с её родителем. Решение о том, сохранять ли
будем принимать только тогда, когда уже приняты решения для всех рёбер, идущих из
к её детям, таким образом
степень вершины
не меняется после рассмотрения ребра
Пусть
— степень вершины
в текущем подграфе.
- Если
— нечётное число, то мы сохраняем ребро
Тогда степень
остается нечётной.
- Если
— четное число, то мы удаляем ребро
Степень
становится нечётной.
Таким образом, мы обеспечили нечётность степени для всех вершин графа, кроме, возможно, корня у которого нет родителя, и мы не
можем подкорректировать его степень ребром.
Проверим степень корня. Сумма степеней всех вершин в любом графе чётна (по лемме о рукопожатиях). Всего вершин кроме корня — нечетное число, и их степени также нечетны, то есть сумма степеней по всем вершнам кроме корня нечетна. Тогда и степень корня нечетна.
Ошибка.
Попробуйте повторить позже
Дан граф на
вершинах: сопоставим каждой вершине
переменную
. Пусть
— множество остовных
деревьев графа
(то есть поддеревьев, содержащих все вершины). Рассмотрим остовный многочлен от
переменных
Назовем связный граф хорошим, если раскладывается на линейные множители (в частности, если
— тождественный
ноль), иначе плохим.
1. Найдите , где
— полный граф на 4 вершинах.
2. Докажите, что цикл на пяти вершинах является плохим графом.
3. Пусть — хороший граф,
— некоторое подмножество его вершин. Граф
состоит из всех вершин, лежащих в
, и всех ребер
графа
, соединяющих эти вершины. Докажите, что граф
тоже хороший.
4. Назовём раздвоением вершины операцию, добавляющую в граф вершину
, соединенную ровно с теми же вершинами, что и
.
Докажите, что граф, получающийся из одной вершины операциями добавления висячей вершины, раздвоения вершины с добавлением ребра
и раздвоения вершины без добавления ребра
, является хорошим.
Источники:
Пункт 1, подсказка 1
Нас просят найти значения многочлена для графа К₄. Может, стоит подумать о его остовных деревьях?
Пункт 1, подсказка 2
В К₄ бывает только 2 вида остовных деревьев. Это либо цепь длины 4, либо три вершины, "висящие" на четвертой. А что нам дадут данные деревья в основный многочлен?
Пункт 1, подсказка 3
Остовные деревья первого вида дадут xᵢxⱼ, а второго - (xᵢ)², где i - вершина остова. Осталось только аккуратно записать искомый многочлен.
Пункт 2, подсказка 1
Для начала, как и в прошлом пункте, рассматриваем остовные деревья и записываем многочлен.
Пункт 2, подсказка 2
Проверьте, у Вас должен был получиться такой многочлен: x₁x₂x₃ + x₂x₃x₄ + x₃x₄x₅ + x₄x₅x₁ + x₅x₁x₂. Вспомните, какой граф мы называем "плохим"?
Пункт 2, подсказка 3
Заметим, что наш многочлен линеен по каждой переменной. Попробуйте показать, что у нас каждая переменная будет "жить" лишь в одной из скобок.
Пункт 2, подсказка 4
Убедитесь, что переменные разбиваются только на скобки вида 2-2-1 и 3-1-1. Что из этого следует?
Пункт 3, подсказка 1
Давайте подумаем, как связность U будет влиять на остовный многочлен?
Пункт 3, подсказка 2
Если U несвязно, то в качестве многочлена мы получим 0. А можем ли мы при связном U выкидывать по одной вершины с сохранением связности?
Пункт 3, подсказка 3
Давайте "подвесим" граф за множество U и будем удалять вершины, начиная с самого нижнего уровня. Что тогда получится?
Пункт 3, подсказка 4
Удалим вершину v. Это равносильно подстановке 0 в xᵥ. Какой вывод можно получить?
Пункт 3, подсказка 5
У нас получится, что все слагаемые c xᵥ обнуляются, следовательно, останутся лишь те, где v - висячая вершина. Как устроены такие деревья?
Пункт 3, подсказка 6
Мы выбираем дерево в графе G\{v}, а потом одна из вершин окрестности v соединяется с v. Какой вид у нас примет тогда остовный многочлен?
Пункт 3, подсказка 7
Докажите, что многочлен останется раскладываемым на множители.
Пункт 4, подсказка 1
Пусть G₁ - граф, получаемый из G на n вершинах добавлением вершины vₙ₊₁, как в операции раздвоения вершины. Давайте для начала подумаем про остовный многочлен графа G. Надо понять, как устроены деревья этого графа.
Пункт 4, подсказка 2
Возьмем лес на всех вершинах, кроме vₙ. Что обязательно должно быть в каждой его компоненте?
Пункт 4, подсказка 3
В каждой компоненте должна быть хотя бы одна вершина из окрестности vₙ в графе G. Как должна быть связана вершина vₙ с этим множеством?
Пункт 4, подсказка 4
vₙ будет соединена ровно с одной такой вершиной из каждой компоненты. Как тогда может быть представлен наш остовный многочлен?
Пункт 4, подсказка 5
Обозначьте за L множество таких лесов, за t(K) - число компонент связности в лесу K, за A₁, A₂, ... , Aₜ - множества пересечений окрестности вершины v в графе G с компонентами связности леса K. Запишите многочлен, пользуясь этими обозначениями.
Пункт 4, подсказка 6
Теперь посмотрим на деревья в графе G₁. Какой лес мы возьмем там?
Пункт 4, подсказка 7
Мы вновь возьмем лес, содержащий все вершины, кроме vₙ, но теперь еще не будем брать вершину vₙ₊₁. Снова подумаем, что должно быть в каждой его компоненте.
Пункт 4, подсказка 8
Как и ранее, в каждой компоненте должна быть хотя бы одна вершина из окрестности vₙ в графе G, после чего одна из долей будет соединена с вершинами vₙ и vₙ₊₁, а все остальные доли - лишь с одной из них. Теперь запишите и преобразуйте остовный многочлен графа G₁, используя те же обозначения, что и для графа G.
Пункт 4, подсказка 9
У Вас должно получиться, что для графа G₁ остовный многочлен от (x₁, x₂, ..., xₙ₊₁) равен остовному многочлену для графа G от (x₁, x₂, ..., xₙ + xₙ₊₁), умноженному на сумму вершин из окрестности vₙ в графе G.
Пункт 4, подсказка 10
Давайте теперь рассмотрим граф G₂, получаемый из G₁ соединением вершин vₙ и vₙ₊₁. Может быть, леса G₁ и G₂ похожи?
Пункт 4, подсказка 11
Мы снова рассмотрим лес, как с графом G₁, но теперь либо не будем проводить ребро между vₙ и vₙ₊₁, либо проведем и соединим каждую из долей ровно с одной из вершин. Какие выводы можно сделать из этих построений?
Пункт 4, подсказка 12
В первом случае мы получим такое же слагаемое, как в G₁. Тогда что нам дает сумма таких слагаемых?
Пункт 4, подсказка 13
Эти слагаемые дадут нам остовный многочлен графа G₁. Осталось только разобраться с суммой вторых слагаемых. Это можно сделать при помощи тех же обозначений, что и для графа G.
1. В полном графе на четырех вершинах есть только 2 вида остовных деревьев: 1) цепь длины 4; 2) три вершины, "висящие"на четвертой.
Каждое дерево первого вида даст в остовный многочлен одночлен ,
, причем каждый одночлен будет представлен 2
раза.
Каждое дерево второго вида даст в остовный многочлен одночлен , где
— "вершина"остова.
В итоге получим многочлен:
________________________________________________________________________________________________________________________________________________________________________________________________________
2. Распишем . Поскольку многочлен
линеен по каждой переменной, получаем,
что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам
не более четырех мономчиков, противоречие.
_________________________________________________________________________________________________________________________________________________________________________________
3. Давайте сначала заметим, что можно последовательно выкидывать вершины по одной с сохранением связности, если связно. (Если
несвязно, то просто 0 получится и все).
Для этого нужно подвесить за и поочередно удалять вершины с самого нижнего уровня. Теперь нужно понять, что при удалении
только одной вершины
граф остается хорошим. Для этого подставим 0 в
. Получим, что все слагаемые, в которые
входило в хотя
бы первой степени, обнулились, а значит остались в точности те, где
— висячая вершина. А все такие деревья устроены так: выбрано
дерево в графе
, и потом одна из вершин из окрестности
соединена с
. Тогда многочлен после подстановки нуля равен
. Подстановка нуля сохраняет раскладываемость на множители, значит
тоже раскладываемый,
значит, при удалении вершины
граф останется хорошим.
_________________________________________________________________________________________________________________________________________________________________________________
4. Сначала докажем вспомогательный факт про такой тип графов.
Лемма о раздвоении без добавления ребра. Пусть дан граф на
вершинах. Рассмотрим граф
, полученный из
добавлением вершины
и соединением ее со всеми вершинами из
, но не самой
. Тогда
Доказательство. Давайте заметим, что любое дерево в графе устройство следующим образом — на всех вершинах, кроме
,
берется некоторый лес, такой, что в каждой компоненте есть хотя бы одна вершина из
, и потом вершина
соединяется с ровно
одной вершиной из каждой компоненты. Обозначим за
множество всех таких лесов, за
— число компонент связности в лесу
, и назовем
пересечения множеств
с компонентами связности леса
. Тогда из рассуждений
выше
Теперь давайте поймём, как устроены деревья в . Там мы тоже берём лес, который содержит все вершины, кроме
,
, и
такой, что каждая его компонента содержит хотя бы одну вершину из
, после чего одна из долей соединяется с обеими вершинами
из
и
, а каждая из остальных
долей — с ровно одной из этих вершин. Тогда в тех же обозначениях получается,
что
Теперь очевидно, что второй сомножитель равен , и лемма доказана.
Лемма 2 (Лемма о раздвоении с добавлением ребра). Пусть дан граф . Рассмотрим граф
, получаемый из
добавлением вершины
и соединением её со всеми вершинами из
, а также с самой
. Тогда
Доказательство. Пусть — граф из леммы
Мы в лемме
уже выяснили как устроены деревья в графе
поэтому нужно
разобраться с тем, как они устроены в
. Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем
одно из двух — либо не проводим ребро между
и
, и это слагаемое такое же как в
, либо проводим, и тогда каждую из
долей соединяем с ровно одной из этих вершин. Стало быть, сумма всех первых слагаемых даст нам
, а сумма вторых
равна
Тогда получается, что
доказали требуемое.
Ошибка.
Попробуйте повторить позже
Докажите, что если граф связен и в нём есть циклы, то в нём есть три вершины, удаление любой из которой сохраняет связность.
Выделим в исходном графе остовное дерево
В нем обязательно найдутся две висячие вершины
и
Удаление их из графа
не
приведет к потере связности, поскольку удаление этих вершин не нарушает связность дерева
В графе есть цикл, значит,
и
—
различные графы. Добавлением одного ребра, имеющегося в
которого нет в
мы получим граф
с единственным циклом
Предположим, что цикл не содержит вершин
и
Тогда в нем есть либо вершина, все ребра которой в
— это ее
ребра в цикле
и тогда удаление любого из ребер, инцидентных ей, приводит к тому, что получается новое дерево
в котором есть дополнительная висячая вершина, удаление которой сохраняет связность
либо в этом графе такой
вершины нет, что означает, что уже в дереве
содержалось хотя бы три висячих вершины, каждую из которых можно
удалять.
Предположим теперь, что содержит одну из вершин
или
(без ограничения общности можно полагать, что это вершина
Тогда можно из цикла
удалить любое ребро, не инцидентное
с сохранением связности. Тогда получится новое дерево
в котором
не является висячей вершиной. Тогда в этом дереве есть висячая вершина, отличная от
и
что
снова приводит нас к нахождению третьей вершины, удовлетворяющей условию. Пусть теперь цикл
содержит обе
вершины
и
Тогда ребро, которое мы добавили — это ребро
Удалив любое другое ребро, получим новое дерево, в
котором одна из вершин
или
не является висячей, а, следовательно, найдем еще одну вершину, которую можно будет
удалить.
Ошибка.
Попробуйте повторить позже
Многие учащиеся математического кружка остаются в нём преподавать после выпуска. Будем говорить, что Ваня является последователем Саши, если Ваня учился у Саши или если Ваня учился у ученика Саши, ученика ученика Саши и так далее. Преподаватель кружка называется народным, если у него есть последователи, и не менее половины из них — победители международной олимпиады IMO. Известно, что всего в кружке училось 100 победителей IMO. Какое наибольшее количество народных преподавателей может быть в этом кружке, если у каждого человека не более одного учителя и никто не является собственным последователем?
Источники:
Подсказка 1
У нас есть люди, причём некоторые из них связаны каким-то отношением... Всё это очень похоже на граф! Рассмотрим ориентированный граф, где вершины — это ученики и преподаватели кружка, а ребра ведут от учителя к его ученику. Каким будет этот граф?
Подсказка 2
Верно, это будет набор непересекающихся деревьев! Рассмотрим какого-нибудь народного учителя, не являющегося последователем другого народного учителя. Если среди его последователей k победителей IMO, то сколько среди них может быть народных учителей?
Подсказка 3
Общее число последователей не может быть больше 2k+1, значит, учителей среди них не больше 2k. Получается, в одном таком поддереве количество народных учителей не более, чем удвоенное количество победителей IMO. А верна ли эта оценка для всего графа?
Рассмотрим ориентированный граф, где вершины ученики и преподаватели кружка, а ребра ведут от учителя к его ученику. По условию
этот граф — лес. Оценка. Выберем какого-нибудь народного учителя который не является последователем другого народного учителя.
Пусть у вершины
последователей победителей IMO. Тогда не победителей IMO, у
не более чем
так как
— народный. А,
значит, всего вершин в поддереве
не более
из которых только
учителей могут будут народными, так хотя бы один человек
никого не учил. Осталось заметить, что поддеревья соответствующие разным выбранным народным учителям, не пересекаются. Поэтому
число народных преподавателей кружка не больше чем удвоенное число победителей IMO. Получили оценку на
Пример. Возьмём
ориентированный путь из
вершины. Победители IMO — это
нижних учеников. Тогда все преподаватели, кроме самого нижнего в
этом пути — народные.
Ошибка.
Попробуйте повторить позже
В стране городов, причем из любого города можно проехать в любой. Докажите, что можно побывать во всех городах и вернуться в
исходный город, проехав не более, чем по
дорогам.
Выделим в нашем графе остовное дерево. В нём рёбер.
Докажем индукцией по количеству вершин, что можно обойти все вершины дерева, проехав не более двух раз по каждому ребру. Тогда
для дерева из вершин можно сделать обход за не более, чем
проездов.
Для дерева из двух вершин это очевидно.
Пусть у нас есть дерево из вершин и на втором уровне расположены вершины
Будем проводить обход следующим
образом: спустимся из корня в
обойдём по предположению индукции дерево с корнем в
затем поднимемся в корень изначального
дерева, спустимся в
и так дальше.
Ошибка.
Попробуйте повторить позже
Докажите, что если в связном графе на вершинах
ребро, то этот граф — дерево.
Ошибка.
Попробуйте повторить позже
Дан связный граф на вершинах. Известно, что при удалении ребер любого простого цикла этот граф теряет связность. Какое
наибольшее число ребер может быть в этом графе?
Подсказка 1:
Для оценки будет очень удобно разделить все рёбра на два множества так, что если удалить одно из них, граф останется связным (для второго так может не работать). Это может позволить удалить цикл, не потеряв связности.
Подсказка 2:
В этом поможет остовное дерево. Но выделить его нужно хитрым образом.
Подсказка 3:
Выделите его таким образом, чтобы в нём участвовали все рёбра, исходящие из корневой вершины. Объясните, почему так сделать можно.
Подсказка 4:
Рассмотрите граф из рёбер, не попавших в остовное дерево. Кажется, если там слишком много рёбер, найдётся цикл, который можно удалить без потери связности.
Предположим, что в графе хотя бы ребра. Выделим в нём остовное дерево, которое будет содержать все рёбра, выходящие из
какой-нибудь вершины. Покажем, что так сделать можно. Выделим какое-нибудь остовное дерево. Рассмотрим главную вершину (первый
уровень дерева). Также рассмотрим какую-нибудь вершину
которая не находится на втором уровне дерева и при этом в исходном графе
соединена с
Перенесём вершину
на второй уровень. Ребро, соединяющее вершину
с вершиной, находящейся уровнем выше,
удалим из дерева.
Теперь рассмотрим граф без рёбер, попавших в остовное дерево. В полученном графе вершина и
ребро (все рёбра вершины
в остовном дереве, поэтому её можно не учитывать). Разберём случаи.
Полученный граф связен. В этом случае в нём есть цикл, притом если его удалить, исходный граф останется связным, поскольку мы
выделили остовное дерево.
Полученный граф не связен, то есть состоит из нескольких компонент связности. Если каждая из компонент является деревом, то
количество рёбер в графе меньше, чем
Если же какая-то из компонент не является деревом, то есть имеет цикл, то мы приходим к
такому же противоречию, как в первом случае.
В качестве примера на вершинах c
ребрами, в котором две вершины
и
соединены со всеми (в том числе и друг с
другом), а остальные вершины соединены только с
и
Ошибка.
Попробуйте повторить позже
В стране городов. В ней действует
дорог с односторонним движением: по одной дороге из
в
для каждой
упорядоченной пары городов
У каждой дороги есть цена её обслуживания. Для данного
…,
рассмотрим все способы
выделить
городов и
дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город, пользуясь только
выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовём
-оптимальной.
Докажите, что города можно пронумеровать от 1 до
так, что при каждом
…,
существует
-оптимальная система дорог с
выделенными городами
…,
Источники:
Подсказка 1:
Назовём сети из N – k дорог k-сетями. Что можно сказать про количество компонент связности в такой сети?
Подсказка 2:
Их ровно k. Если сами не дошли до этого, обоснуйте этот момент. Глобально хочется провести следующие рассуждения. Давайте возьмём k + 1-оптимальную сеть A и k-оптимальную сеть B. Попробуйте найти другие k-сети, включающие в себя города из этих оптимальных сетей.
Подсказка 3:
Обозначим города сети A через yᵢ, i от 0 до k, а города B — через xᵢ, i от 1 до k. Рассмотрим следующие множества: U — множество городов, из которых в A можно добраться до y₀; a, b — множества дорог, выходящих из U в сетях A, B соответственно. Что можно сказать про мощности a и b? Попробуйте с помощью этих множеств получить какие-то сети из городов A и B.
Подсказка 4:
Обратите внимание на множество (A \ a) ∪ b. Сколько в нём дорог? Является ли оно k-сетью и если да, то для каких городов?
Подсказка 5:
Это k-сеть городов yᵢ, где i от 1 до k. Теперь обратите внимание на множество (B \ b) ∪ a. Что можно сказать про него?
Подсказка 6:
Это (k + 1)-сеть из городов xᵢ, i от 1 до k и y₀. Осталось совсем немного, чтобы завершить решение.
Рассматриваемые сети из дорог называем далее
-сетями. Рассмотрим неориентированный граф, образованный дорогами
-сети. В нём не более чем
компонент связности, поскольку в каждой есть выделенный город. С другой стороны, компонент не менее
поскольку рёбер всего не более чем
Поэтому компонент ровно
каждая из них есть дерево, содержит
единственный выделенный город и — вспоминая про ориентацию — рёбра каждого дерева направлены по направлению к
выделенному городу. В частности, из каждого не выделенного города должна выходить ровно одна дорога, а из выделенного 0
дорог.
Рассмотрим -оптимальную сеть
с выделенными городами
и -оптимальную сеть
с выделенными городами
Не умаляя общности, ни из одного нельзя добраться в сети
до города
Пусть
— множество городов, из
которых в
можно добраться до
а
— множества дорог, выходящих из
в сетях
соответственно.
Имеем
Рассмотрим сеть
Утверждается, что это -сеть для выделенных городов
В самом деле, число дорог в ней равно
Из каждого города, кроме выходит ровно одна дорога. Выезжая из любого города вне
и используя дороги сети, мы
по-прежнему можем попасть в один из городов
Выезжая из города в
мы либо попадаем вне
— и далее в один из
городов
— либо зацикливаемся в
Но тогда
содержит цикл, что невозможно.
Рассмотрим сеть
Утверждается, что это -сеть для выделенных городов
В самом деле,
и, выезжая из любого города по дорогам сети мы либо попадаем в
— и тогда по
доезжаем до
— либо ни разу не
попадаем в
и тогда доезжаем до одного из городов
Итак, —
-сеть и
-сеть. Сумма их стоимостей такая же, как у
и
Значит, они обе оптимальны. Таким образом,
для сети
удалось выкинуть выделенный город и найти оптимальную
-сеть с оставшимися выделенными городами. Теперь можно
построить требуемую нумерацию в обратном порядке (начиная с пустой
-сети).
Ошибка.
Попробуйте повторить позже
(a) Проведём индукцию по База для
верна. Пусть в любом связном графе с
вершиной хотя бы
ребра. Покажем, что в связном графе с
вершинами хотя бы
ребро. Пусть степени всех вершин хотя бы 2. Тогда
суммарная степень хотя бы
а значит, рёбер хотя бы
Пусть нашлась вершина
степень которой не более 1. Если ее
степень равна 0, то в графе всего 1 вершина, поскольку граф связен, и утверждение задачи верно. Пусть теперь степень
равна 1. Тогда удалим эту вершину вместе с исходящим из неё ребром. Предположим, что нарушилась связность.
Тогда есть какие-то 2 вершины
и
путь между которыми обязательно проходил через
Но степень
равна 1,
значит, на пути мы зашли в
и вышли по тому же ребру. Тогда рассмотрим такой же путь, но без захода в
Так
можно удалить все посещения
на пути, значит, связность не нарушилась. Тогда можно применить предположение
индукции. В графе с удаленной вершиной не менее
ребер, следовательно, в исходном графе не менее
ребер.
(b) Как и в предыдущем пункте, проведём индукцию по База индукции очевидна. Пусть в дереве на
вершине ровно
ребра. Найдём висячую вершину (которая всегда существует в дереве) и удалим её. Связность не нарушилась (мы доказывали это в
предыдущем пункте), в графе стало на 1 вершину и на 1 ребро меньше. По предположению индукции теперь рёбер
значит,
изначально их было
что и требовалось доказать.
Ошибка.
Попробуйте повторить позже
Докажите, что из любого связного графа можно выделить дерево, содержащее все его вершины (такое дерево называют остовным деревом).
Запустим такой процесс. Найдём в графе цикл (если их нет, то граф уже дерево) и удалим любое его ребро. Докажем, что при этом граф не потерял связности: в самом деле, если мы в каком-то пути использовали удалённое ребро, то вместо него можно пройти по оставшейся части цикла. Продолжим так удалять рёбра циклов, пока циклы не исчезнут. Полученный граф и будет остовным деревом.
Ошибка.
Попробуйте повторить позже
Докажите, что в любом связном графе есть вершина, при удалении которой граф остается связным.
Ошибка.
Попробуйте повторить позже
Чтобы добраться от ствола к любому листу дерева, изображённого на рисунке, нужно на каждой развилке повернуть либо налево, либо направо. Например, для того чтобы добраться до листа с буквой А, нужно пройти так: ПППЛП (буква П — это поворот на развилке вправо, буква Л — поворот влево). Напишите с помощью букв П и Л путь к листу Б.
![]()
Ошибка.
Попробуйте повторить позже
В некоторой стране есть городов, которые связаны такой сетью дорог, что из любого города в любой другой можно проехать
только одним способом без разворотов. Схема сети дорог известна, развилки и перекрестки сети необязательно являются
городами, всякая тупиковая ветвь сети обязательно заканчивается городом. Навигатор может измерить длину пути по этой
сети между любыми двумя городами. Можно ли за
таких измерений гарантированно определить длину всей сети
дорог?
Источники:
Подсказка 1
Города и дороги сразу же намекают нам о том, что над задачей стоит думать в формате графа. Но что это за граф такой, в котором из любой вершины в любую другую можно попасть только одним единственным способом?
Подсказка 2
Наш граф является деревом, так как он связный и в нём не может быть циклов. Заметьте, что нам доступно не более 100 измерений. А чего в дереве из ста вершин будет менее сотни?
Подсказка 3
В дереве на ста вершинах всегда будет меньше ста листов. Подумайте над обходом, который обходит последовательно все листья и позволяет нам посчитать количество всех ребер в дереве.
Подсказка 4
Подвесим наше дерево за одну из вершин, не являющуюся листом, это будет корень. Рассмотрим вариант обхода. Выбираем случайный лист и ищем следующий для него, всегда будем идти по самому правому, еще не посещенному, ведущему вниз ребру, если таких нет, то поднимаемся на уровень выше, движемся таким образом, пока не окажемся в листе.
Подсказка 5
Повторяем данный алгоритм последовательно, пока не вернемся в изначальный лист. Сколько раз в результате такого обхода будет посещено каждое ребро?
Представим описанную в условии сеть дорог в виде графа, вершинами которого являются города, развилки и перекрестки, а ребрами —
дороги. Покажем, что этот граф является деревом, то есть связным графом без циклов. Связность следует из того, что из любого
города можно проехать в любой другой, а любая развилка или перекресток должны быть соединены с каким-либо городом.
Допустим, что в нашем графе есть цикл. Он не содержит двух и более вершин-городов, так как в этом случае, двигаясь в
противоположных направлениях по циклу, мы могли бы получить два различных пути из одного города в другой. Далее,
пусть между некоторыми городами и
существует путь, содержащий какую-то вершину цикла. Он обязательно
найдется, так как иначе эта вершина не могла бы быть в нашей сети. Но тогда, добавляя к этому пути «кольцо» вдоль
цикла, мы получим еще один путь между
и
Значит, циклов в нашем графе быть не может и это действительно
дерево.
По условию задачи все концевые вершины дерева — города. Назовем эти города концевыми. Назовем также концевой город
следующим за концевым городом
если по пути из
в
на каждой развилке выбирается самая правая дорога. Выберем какой-нибудь
концевой город
и измерим расстояние между ним и следующим за ним концевым городом
Потом измерим расстояние между
и следующим за ним концевым городом
и так далее. После не более чем
таких измерений мы вернемся в исходный город
Покажем, что при этом каждая дорога нашей сети будет пройдена ровно два раза в противоположных направлениях. Рассмотрим
произвольную дорогу. При удалении из дерева любого ребра оно распадается на две компоненты связности и
причем каждая из
них содержит города. Пусть изначально мы находились в
Поскольку необходимо обойти все города сети, мы должны пройти по этой
дороге два раза: первый раз — когда движемся из
в
а второй — когда возвращаемся обратно. Процедура обхода устроена таким
образом, что мы посетим все вершины компоненты
до того, как покинем ее, поэтому больше проходить по дороге из
в
не
потребуется.
Наконец, сложив измеренные величины и разделив сумму пополам, мы получим длину всей сети.
Да, можно
Ошибка.
Попробуйте повторить позже
В стране городов, каждые два города соединены (двусторонними) авиалиниями, цены всех перелетов попарно различны (для любой
пары городов цена перелета «туда» равна цене «обратно»). В каждом городе находится турист. Каждый вечер все туристы переезжают:
богатые туристы — по самой дорогой, бедные — по самой дешевой линии, ведущей из соответствующего города. Через
дней оказалось,
что в каждом городе снова по одному туристу. За это время ни один турист не посетил никакой город дважды. При каком наибольшем
такое возможно?
Источники:
Подсказка 1.
Сначала попробуем построить оценку. Можно считать, что богачей хотя бы половина. Рассмотрим ориентированный граф, в котором будем проводить из вершины только самое дорогое ребро. Тогда богачи движутся только по ребрам этого графа.
Ясно, что во время путешествий никакие два богатых туриста (или два бедных) не могли оказаться в одном городе. С другой стороны, условие задачи не запрещает находиться в одном городе одновременно бедному и богатому туристу, важно лишь, чтобы в начальный и в конечный момент в каждом городе было по одному туристу.
Допустим, что среди туристов имеется (или более) «богачей». Нарисуем граф: вершины — это города, из каждого города проведем
самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню,
за исключением единственного ребра, выходящего из корня, — это ребро в дереве как бы двустороннее. Возьмем богача,
который расположен ближе всего к корню своего дерева. Этот богач будет в течение
ходов самым близким к корню.
Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф — это путь из
вершин, богачи занимают первые
вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй
половины. Отсюда следует, что богачей не может быть больше
а также что количество переездов тоже не превосходит
Тогда бедных туристов тоже и они двигаются по аналогичному «бедному» пути, причем в начальный момент они занимают всю
вторую половину «богатого» пути. Эти пути не имеют общих звеньев, и при этом движение бедняков таково, что с каждым ходом они
должны освобождать от своего присутствия очередную вершину второй половины богатого пути, смещаясь гуськом в первую половину.
Тогда движение туристов может происходить, например, следующим образом.
Обозначим города Допустим, что путь
составлен из самых дорогих авиалиний, для определенности пусть цена перелета равна
рублей. А «бедный путь»
пусть сначала проходит по городам с большими четными номерами, потом — по городам с большими нечетными, а далее — с малыми:
сначала с четными, потом с нечетными:
Цены этих авиалинии пусть убывают от до
рубля при движении вдоль этого пути. Цены остальных авиалиний назначим
произвольно в диапазоне от
до
рублей.
При
Ошибка.
Попробуйте повторить позже
В стране есть городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между любыми
двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города
подсчитал количество таких
нумераций всех городов числами от
до
что на любом авиамаршруте, начинающемся в
номера городов идут в порядке
возрастания. Все мэры, кроме одного, заметили, что их результаты подсчетов делятся на
Докажите, что и у оставшегося мэра
результат также делится на
Источники:
Подсказка 1:
Попробуйте получить некоторое равенство, включающее в себя числа, полученные мэрами, чтобы потом сказать, что раз все слагаемые, кроме одного, кратны 2016, то и последнее кратно.
Подсказка 2:
Назовём некоторый город А столицей. Назовём город чётным, если маршрут из A до него содержит чётное количество рейсов. Иначе нечётным. Докажите, что сумма чисел у нечётных городов равна сумме чисел у чётных.
Подсказка 3:
Попробуйте некоторым образом взаимно однозначно сопоставить нумерации для нечётных и чётных городов.
Подсказка 4:
Пусть некоторая нумерация была посчитана мэром города X. Какой номер в ней имеет X?
Подсказка 5:
Он имеет номер 1. Теперь рассмотрите любую нумерацию, подходящую чётному городу E. Пусть номер 2 имеет город W. Попробуйте подобрать нумерацию, подходящую для W.
Подсказка 6:
Что, если поменять номера 1 и 2?
Назовём какой-нибудь город столицей. Назовём город чётным, если маршрут из
до него содержит чётное число рейсов, и нечётным
иначе (таким образом, город
чётный). Тогда чётность любых двух городов, соединённых рейсом, различна. Мы докажем, что сумма
чисел, полученных мэрами чётных городов, равна сумме чисел, полученных мэрами нечётных; из этого следует утверждение
задачи.
Назовём нумерацию городов подходящей для города если мэр города
её посчитал. Ясно, что в любой нумерации, подходящей
городу
он имеет номер
так что каждая нумерация подходит не более, чем одному городу.
Рассмотрим любую нумерацию, подходящую чётному городу Пусть номер
в ней носит город
тогда
— нечётный город,
соединённый с
иначе на маршруте от
до
встретился бы город с большим номером. Поменяем местами номера
и
мы
получим нумерацию, в которой номер
носит нечётный город
Рассмотрим любой маршрут начинающийся в
Он получается из некоторого маршрута, выходящего из
либо добавлением
города
в начало (если
проходит через
), либо откидыванием
из начала (в противном случае). Тогда легко видеть, что после
обмена
и
номера на
идут в порядке возрастания.
Итак, после перемены номеров и
из нумерации, подходящей для чётного города, получается нумерация, подходящую для
нечётного (и наоборот). Это сопоставление взаимно однозначно. Значит, тех и других нумераций поровну, что и требовалось
доказать.




