Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

Тема Графы и турниры

Деревья и остовные деревья

01. Вспоминай формулы
по каждой теме
02. Решай новые задачи
каждый день
03. Вдумчиво разбирай
решения
04. Готовиться с платформой
«Школково» — ЛЕГКО!
Подтемы раздела графы и турниры
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#103481Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

Число 20 выглядит произвольным. Скорее всего, задача имеет общее решение для произвольного количества кружков. Например, сколько вопросов необходимо задать, чтобы узнать списки 3 кружков?

Подсказка 2

Необходимо 3 вопроса, соответственно про (1, 2), (2, 3) и (3, 1) кружок. Отсюда может появиться предположение, что ответом на задачу является количество кружков, то есть 20. Почему этого количества вопросов будет достаточно?

Подсказка 3

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

Подсказка 4

Потребуем, чтобы весь список каждого кружка был уникален. Например, этого можно добиться, если количество учеников будет равно 2^20, причем каждый будет посещать уникальное множество кружков. Как удобно изображать множество вопросов, заданных в алгоритме?

Подсказка 4

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

Подсказка 5

В нем существует компонента, которая является суть путем. Что теперь нужно для того, чтобы закончить доказательство?

Подсказка 6

Можно доказать, что найдутся множества кружков A и B, для которых найдется школьник, который ходит только в кружки множества A, и школьник, который ходит только в кружки множества B, по ответам неотличимы. Найдите соответствующие множества среди кружков, соответствующих вершинам найденного пути.

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 2#125295Максимум баллов за задание: 7

В дереве есть рёбра, а все вершины имеют степень 1 или 2. Сколько в этом дереве может быть висячих вершин?

Подсказки к задаче

Подсказка 1:

Пусть имеется k вершин степени 1. Как можно выразить сумму степеней всех вершин через n и k, где n — общее количество вершин?

Подсказка 2:

Сумма степеней вершин равна k + 2(n − k) = 2n − k. А можно ли выразить эту же сумму как-то иначе, например, через количество рёбер?

Подсказка 3:

Вспомните, что в дереве количество рёбер на единицу меньше количества вершин. Осталось использовать это для составления уравнения, откуда найти все возможные значения k.

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 3#126097Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1:

Ясно, что нужно перевести условие на язык графов. Вершины – города, рёбра – дороги, граф – дерево, а каждую область будем рассматривать некоторый связный подграф.

Подсказка 2:

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

Подсказка 3:

Удалять вершины нужно так, чтобы сохранялось условие задачи. Проще всего это сделать с листьями дерева. Подумайте, почему в какой-то момент удалить лист не получится?

Сообщить об ошибке
Подсказки
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 4#147177Максимум баллов за задание: 7

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

Сообщить об ошибке
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 5#153042Максимум баллов за задание: 7

Дано некоторое натуральное n ≥2.  Какое наименьшее количество элементов может быть в множестве, обладающем следующим свойством: для любого k =2,3,...,n  найдутся два числа из множества с разностью Fk?  Напомним, что числа Фибоначчи — это последовательность чисел, заданная начальными условиями F1 = F2 = 1  и рекуррентным соотношением Fk+1 = Fk+ Fk−1.

Сообщить об ошибке
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 6#161766Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1.

Заметим, что если удалить ребро, сохраняющее связность, то утверждение задачи не изменится, а количество рёбер уменьшится. К чему в итоге приведёт такой процесс?

Сообщить об ошибке
Подсказки
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 7#83388Максимум баллов за задание: 7

Дан граф G =(V,E)  на n  вершинах: сопоставим каждой вершине v  переменную x
 v  . Пусть T  — множество остовных деревьев графа G  (то есть поддеревьев, содержащих все вершины). Рассмотрим остовный многочлен от n  переменных x1,...,xn

                ∑  ∏  deg v−1
PG(x1,x2,...,xn)=       xv  S  .
               S∈Tv∈V

Назовем связный граф хорошим, если PG (x1,...,xn)  раскладывается на линейные множители (в частности, если PG  — тождественный ноль), иначе плохим.

1. Найдите PK4(1,2,3,4)  , где K4  — полный граф на 4 вершинах.

2. Докажите, что цикл на пяти вершинах является плохим графом.

3. Пусть G  — хороший граф, U  — некоторое подмножество его вершин. Граф H  состоит из всех вершин, лежащих в U  , и всех ребер графа G  , соединяющих эти вершины. Докажите, что граф H  тоже хороший.

4. Назовём раздвоением вершины v  операцию, добавляющую в граф вершину v′ , соединенную ровно с теми же вершинами, что и   v  . Докажите, что граф, получающийся из одной вершины операциями добавления висячей вершины, раздвоения вершины с добавлением ребра   ′
vv и раздвоения вершины без добавления ребра   ′
vv , является хорошим.

Источники: ЮМШ - 2024, сюжет 2 (см. yumsh.ru)

Подсказки к задаче

Пункт 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.

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 8#97422Максимум баллов за задание: 7

Докажите, что если граф связен и в нём есть циклы, то в нём есть три вершины, удаление любой из которой сохраняет связность.

Сообщить об ошибке
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 9#134202Максимум баллов за задание: 7

Многие учащиеся математического кружка остаются в нём преподавать после выпуска. Будем говорить, что Ваня является последователем Саши, если Ваня учился у Саши или если Ваня учился у ученика Саши, ученика ученика Саши и так далее. Преподаватель кружка называется народным, если у него есть последователи, и не менее половины из них — победители международной олимпиады IMO. Известно, что всего в кружке училось 100 победителей IMO. Какое наибольшее количество народных преподавателей может быть в этом кружке, если у каждого человека не более одного учителя и никто не является собственным последователем?

Источники: Высшая проба - 2024, 10.4 (см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Верно, это будет набор непересекающихся деревьев! Рассмотрим какого-нибудь народного учителя, не являющегося последователем другого народного учителя. Если среди его последователей k победителей IMO, то сколько среди них может быть народных учителей?

Подсказка 3

Общее число последователей не может быть больше 2k+1, значит, учителей среди них не больше 2k. Получается, в одном таком поддереве количество народных учителей не более, чем удвоенное количество победителей IMO. А верна ли эта оценка для всего графа?

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 10#73294Максимум баллов за задание: 7

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

Сообщить об ошибке
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 11#74540Максимум баллов за задание: 7

Докажите, что если в связном графе на n  вершинах n− 1  ребро, то этот граф — дерево.

Сообщить об ошибке
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 12#91032Максимум баллов за задание: 7

Дан связный граф на n> 3  вершинах. Известно, что при удалении ребер любого простого цикла этот граф теряет связность. Какое наибольшее число ребер может быть в этом графе?

Подсказки к задаче

Подсказка 1:

Для оценки будет очень удобно разделить все рёбра на два множества так, что если удалить одно из них, граф останется связным (для второго так может не работать). Это может позволить удалить цикл, не потеряв связности.

Подсказка 2:

В этом поможет остовное дерево. Но выделить его нужно хитрым образом.

Подсказка 3:

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

Подсказка 4:

Рассмотрите граф из рёбер, не попавших в остовное дерево. Кажется, если там слишком много рёбер, найдётся цикл, который можно удалить без потери связности.

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 13#131966Максимум баллов за задание: 7

В стране N  городов. В ней действует N (N − 1)  дорог с односторонним движением: по одной дороге из X  в Y  для каждой упорядоченной пары городов X ⁄= Y.  У каждой дороги есть цена её обслуживания. Для данного k= 1,  …, N  рассмотрим все способы выделить k  городов и N − k  дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город, пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовём k  -оптимальной. Докажите, что города можно пронумеровать от 1 до N  так, что при каждом k= 1,2,  …, N  существует k  -оптимальная система дорог с выделенными городами 1,2,  …, k.

Источники: ВСОШ, ЗЭ, 2023, 11.8 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 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₀. Осталось совсем немного, чтобы завершить решение.

Сообщить об ошибке
Подсказки
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 14#35478Максимум баллов за задание: 7

(a) Докажите, что в связном графе с n  вершинами содержится как минимум n− 1  ребро.

(b) Докажите, что в дереве с n  вершинами количество рёбер равно n− 1.

Сообщить об ошибке
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 15#35479Максимум баллов за задание: 7

Докажите, что из любого связного графа можно выделить дерево, содержащее все его вершины (такое дерево называют остовным деревом).

Сообщить об ошибке
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 16#35487Максимум баллов за задание: 7

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

Сообщить об ошибке
Доказательство
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 17#39388Максимум баллов за задание: 7

Чтобы добраться от ствола к любому листу дерева, изображённого на рисунке, нужно на каждой развилке повернуть либо налево, либо направо. Например, для того чтобы добраться до листа с буквой А, нужно пройти так: ПППЛП (буква П — это поворот на развилке вправо, буква Л — поворот влево). Напишите с помощью букв П и Л путь к листу Б.

PIC

Сообщить об ошибке
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 18#81407Максимум баллов за задание: 7

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

Источники: ММО - 2021, первый день, 11.4 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Города и дороги сразу же намекают нам о том, что над задачей стоит думать в формате графа. Но что это за граф такой, в котором из любой вершины в любую другую можно попасть только одним единственным способом?

Подсказка 2

Наш граф является деревом, так как он связный и в нём не может быть циклов. Заметьте, что нам доступно не более 100 измерений. А чего в дереве из ста вершин будет менее сотни?

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Повторяем данный алгоритм последовательно, пока не вернемся в изначальный лист. Сколько раз в результате такого обхода будет посещено каждое ребро?

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 19#70630Максимум баллов за задание: 7

В стране 50  городов, каждые два города соединены (двусторонними) авиалиниями, цены всех перелетов попарно различны (для любой пары городов цена перелета «туда» равна цене «обратно»). В каждом городе находится турист. Каждый вечер все туристы переезжают: богатые туристы — по самой дорогой, бедные — по самой дешевой линии, ведущей из соответствующего города. Через k  дней оказалось, что в каждом городе снова по одному туристу. За это время ни один турист не посетил никакой город дважды. При каком наибольшем   k  такое возможно?

Источники: СпбОШ - 2016, задача 11.6(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1.

Сначала попробуем построить оценку. Можно считать, что богачей хотя бы половина. Рассмотрим ориентированный граф, в котором будем проводить из вершины только самое дорогое ребро. Тогда богачи движутся только по ребрам этого графа.

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Ошибка.
Попробуйте повторить позже

Задача 20#165193Максимум баллов за задание: 7

В стране есть n> 1  городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между любыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города X  подсчитал количество таких нумераций всех городов числами от 1  до n,  что на любом авиамаршруте, начинающемся в X,  номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчетов делятся на 2016.  Докажите, что и у оставшегося мэра результат также делится на 2016.

Источники: ВСОШ, ЗЭ, 2016, 11.6 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте получить некоторое равенство, включающее в себя числа, полученные мэрами, чтобы потом сказать, что раз все слагаемые, кроме одного, кратны 2016, то и последнее кратно.

Подсказка 2:

Назовём некоторый город А столицей. Назовём город чётным, если маршрут из A до него содержит чётное количество рейсов. Иначе нечётным. Докажите, что сумма чисел у нечётных городов равна сумме чисел у чётных.

Подсказка 3:

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

Подсказка 4:

Пусть некоторая нумерация была посчитана мэром города X. Какой номер в ней имеет X?

Подсказка 5:

Он имеет номер 1. Теперь рассмотрите любую нумерацию, подходящую чётному городу E. Пусть номер 2 имеет город W. Попробуйте подобрать нумерацию, подходящую для W.

Подсказка 6:

Что, если поменять номера 1 и 2?

Сообщить об ошибке
Подсказки
Доказательство
Сообщить об ошибке
Рулетка
Вы можете получить скидку в рулетке!