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

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела графы и турниры

Решаем задачи

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

Задача 1#103481

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

Подсказка 4

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

Подсказка 5

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

Подсказка 6

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

Показать ответ и решение

Пример. Спросим про пары $(1,2),$ $(2,3)$ и $(3,1),$ а затем про все пары вида $(1,k),$ где $k= 4,...,20.$ Докажем, что за первые три вопроса мы выясним составы кружков $1,$ $2$ и $3.$ Посмотрим на любого человека. Если он не ходит ни в один из этих кружков, то его имя не будет названо ни разу, и это ни с чем не перепутаешь. Если он входит только в один кружок, то его имя всплывёт в двух вопросах, как посещающего один кружок. При этом по этим двум парам мы восстановим, в какой кружок он ходит. Если он ходит в два кружка, то однажды он появится, как посещающий два кружка, и дважды — как посещающий один из двух. В этой ситуации легко вычисляется, куда он ходит. Если он ходит во все, то во всех парах покажется, как посещающий оба, и тоже получится вычислить, что он во все ходит. То есть про любого человека мы поймём, куда он ходит, а это и значит, что вычислим составы всех кружков. Теперь, зная, кто ходит в первый кружок, после вопроса $(1,k)$ легко вычисляем, кто ходит в кружок $k.$

Оценка. Будем считать, что в школе $220$ учеников. Каждому ученику сопоставим уникальное подмножество кружков и направим его ровно в кружки из его подмножества. Предположим, что после $19$ вопросов удалось выяснить составы всех кружков. Это значит, что мы научились различать всех учеников. Рассмотрим граф, вершины которого — кружки. Соединим вершины ребром, если мы спросили про эту пару кружков. В графе $20$ вершин и $19$ рёбер, значит, хотя бы в одной компоненте связности рёбер меньше, чем вершин, то есть эта компонента связности — дерево. А вершины дерева можно правильным образом покрасить в два цвета. Обозначим множества вершин первого и второго цвета $A$ и $B.$ Тогда школьник, который ходит только в кружки множества $A,$ и школьник, который ходит только в кружки множества $B,$ по ответам не отличимы. Во всех вопросах про эту компоненту связности оба назывались как ходящие в один из двух кружков.

Ответ:

$20$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#125295

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

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

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

Показать ответ и решение

Пусть в дереве $n$ вершин, тогда там $n− 1$ ребро. Пусть висячих вершин $k.$ Тогда невисячих $n− k,$ причём каждая имеет степень 2. Значит, суммарная степень вершин

k+ 2(n− k)= 2n − k

С другой стороны, эта же сумма равна удвоенному количеству рёбер, то есть $2n− 2.$ Отсюда $k= 2.$

Ответ:

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

Задача 3#126097

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

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

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

Показать доказательство

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

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

Задача 4#83388

Дан граф $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.

Показать ответ и решение

1. В полном графе на четырех вершинах есть только 2 вида остовных деревьев: 1) цепь длины 4; 2) три вершины, "висящие"на четвертой.

Каждое дерево первого вида даст в остовный многочлен одночлен $xixj$ , $i⁄= j$ , причем каждый одночлен будет представлен 2 раза.

Каждое дерево второго вида даст в остовный многочлен одночлен $x2i$ , где $i$ — "вершина"остова.

В итоге получим многочлен:

$pict$

________________________________________________________________________________________________________________________________________________________________________________________________________

2. Распишем $PC = x1x2x3+ x2x3x4+ x3x4x5+ x4x5x1+ x5x1x2 5$ . Поскольку многочлен $PC 5$ линеен по каждой переменной, получаем, что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам не более четырех мономчиков, противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

3. Давайте сначала заметим, что можно последовательно выкидывать вершины по одной с сохранением связности, если $U$ связно. (Если несвязно, то просто 0 получится и все).

Для этого нужно подвесить за $U$ и поочередно удалять вершины с самого нижнего уровня. Теперь нужно понять, что при удалении только одной вершины $v$ граф остается хорошим. Для этого подставим 0 в $xv$ . Получим, что все слагаемые, в которые $xv$ входило в хотя бы первой степени, обнулились, а значит остались в точности те, где $v$ — висячая вершина. А все такие деревья устроены так: выбрано дерево в графе $G∖v$ , и потом одна из вершин из окрестности $v$ соединена с $v$ . Тогда многочлен после подстановки нуля равен $∑ PG∖v(x1,...,xn)⋅( u∈N(v)xu)$ . Подстановка нуля сохраняет раскладываемость на множители, значит $PG∖v$ тоже раскладываемый, значит, при удалении вершины $v$ граф останется хорошим.

_________________________________________________________________________________________________________________________________________________________________________________

4. Сначала докажем вспомогательный факт про такой тип графов.

Лемма о раздвоении без добавления ребра. Пусть дан граф $G$ на $n$ вершинах. Рассмотрим граф $G1$ , полученный из $G$ добавлением вершины $vn+1$ и соединением ее со всеми вершинами из $NG(vn)$ , но не самой $vn$ . Тогда

( ∑ ) PG1(x1,x2,...,xn+1)= PG(x1,...,xn+ xn+1)( xv). v∈NG(vn)

Доказательство. Давайте заметим, что любое дерево в графе $G$ устройство следующим образом — на всех вершинах, кроме $vn$ , берется некоторый лес, такой, что в каждой компоненте есть хотя бы одна вершина из $NG(vn)$ , и потом вершина $vn$ соединяется с ровно одной вершиной из каждой компоненты. Обозначим за $L$ множество всех таких лесов, за $t(K)$ — число компонент связности в лесу $K$ , и назовем $A1,A2,...At$ пересечения множеств $NG (v)$ с компонентами связности леса $K$ . Тогда из рассуждений выше

( ( ) ) ∑ ( ∏ degK(v)−1t(∏K)( ∑ ) t(K)−1) PG(x1,x2,...,xn) =K ∈L v∈V|v⁄=vnxv i=1 v∈Aixv xn .

Теперь давайте поймём, как устроены деревья в $G1$ . Там мы тоже берём лес, который содержит все вершины, кроме $vn$ , $vn+1$ , и такой, что каждая его компонента содержит хотя бы одну вершину из $NG(vn)$ , после чего одна из долей соединяется с обеими вершинами из $vn$ и $vn+1$ , а каждая из остальных $t(K)− 1$ долей — с ровно одной из этих вершин. Тогда в тех же обозначениях получается, что

$pict$

Теперь очевидно, что второй сомножитель равен $PG(x1,x2,...,xn+ xn+1)$ , и лемма доказана.

Лемма 2 (Лемма о раздвоении с добавлением ребра). Пусть дан граф $G,|G|= n$ . Рассмотрим граф $G2$ , получаемый из $G$ добавлением вершины $vn+1$ и соединением её со всеми вершинами из $NG(vn)$ , а также с самой $vn$ . Тогда

( ) PG2(x1,x2,...,xn+1)= PG(x1,x2,...,xn+ xn+1)( ∑ xv+xn +xn+1) . v∈NG (vn)

Доказательство. Пусть $G1$ — граф из леммы $1.$ Мы в лемме $1$ уже выяснили как устроены деревья в графе $G,$ поэтому нужно разобраться с тем, как они устроены в $G2$ . Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем одно из двух — либо не проводим ребро между $vn$ и $vn+1$ , и это слагаемое такое же как в $G1$ , либо проводим, и тогда каждую из долей соединяем с ровно одной из этих вершин. Стало быть, сумма всех первых слагаемых даст нам $PG1$ , а сумма вторых равна

$pict$

Тогда получается, что

$pict$

доказали требуемое.

Ответ:

1. $(x1+ x2 +x3+ x4)2$

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

Задача 5#97422

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

Показать доказательство

Выделим в исходном графе $G$ остовное дерево $T.$ В нем обязательно найдутся две висячие вершины $u$ и $v.$ Удаление их из графа $G$ не приведет к потере связности, поскольку удаление этих вершин не нарушает связность дерева $T.$ В графе есть цикл, значит, $G$ и $T$ — различные графы. Добавлением одного ребра, имеющегося в $G,$ которого нет в $T,$ мы получим граф $′ T$ с единственным циклом $C.$

Предположим, что цикл $C$ не содержит вершин $u$ и $v.$ Тогда в нем есть либо вершина, все ребра которой в $′ T$ — это ее ребра в цикле $C,$ и тогда удаление любого из ребер, инцидентных ей, приводит к тому, что получается новое дерево $-- T ,$ в котором есть дополнительная висячая вершина, удаление которой сохраняет связность $G;$ либо в этом графе такой вершины нет, что означает, что уже в дереве $T$ содержалось хотя бы три висячих вершины, каждую из которых можно удалять.

Предположим теперь, что $C$ содержит одну из вершин $u$ или $v$ (без ограничения общности можно полагать, что это вершина $u).$ Тогда можно из цикла $C$ удалить любое ребро, не инцидентное $u,$ с сохранением связности. Тогда получится новое дерево $∼ T,$ в котором $u$ не является висячей вершиной. Тогда в этом дереве есть висячая вершина, отличная от $u$ и $v,$ что снова приводит нас к нахождению третьей вершины, удовлетворяющей условию. Пусть теперь цикл $C$ содержит обе вершины $u$ и $v.$ Тогда ребро, которое мы добавили — это ребро $uv.$ Удалив любое другое ребро, получим новое дерево, в котором одна из вершин $u$ или $v$ не является висячей, а, следовательно, найдем еще одну вершину, которую можно будет удалить.

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

Задача 6#73294

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

Показать доказательство

Выделим в нашем графе остовное дерево. В нём $99$ рёбер.

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

Для дерева из двух вершин это очевидно.

Пусть у нас есть дерево из $n$ вершин и на втором уровне расположены вершины $A1,A2,...,Ak.$ Будем проводить обход следующим образом: спустимся из корня в $A1,$ обойдём по предположению индукции дерево с корнем в $A1,$ затем поднимемся в корень изначального дерева, спустимся в $A2$ и так дальше.

Курсы

Всё необходимое для достижения цели

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

Задача 7#74540

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

Показать доказательство

Предположим, что граф не является деревом. Тогда выделим в нём остовное дерево. Ясно, что в это дерево не попали все рёбра графа, иначе наше предположение неверно. Следовательно, в остовном дереве на $n$ вершинах не более $n− 2$ рёбер, получили противоречие с тем, что в дереве с $n$ вершинами $n− 1$ ребро.

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

Задача 8#91032

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

Показать ответ и решение

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

Теперь рассмотрим граф без рёбер, попавших в остовное дерево. В полученном графе $n− 1$ вершина и $n− 1$ ребро (все рёбра вершины $A$ в остовном дереве, поэтому её можно не учитывать). Разберём случаи.

$1)$ Полученный граф связен. В этом случае в нём есть цикл, притом если его удалить, исходный граф останется связным, поскольку мы выделили остовное дерево.

$2)$ Полученный граф не связен, то есть состоит из нескольких компонент связности. Если каждая из компонент является деревом, то количество рёбер в графе меньше, чем $n− 1.$ Если же какая-то из компонент не является деревом, то есть имеет цикл, то мы приходим к такому же противоречию, как в первом случае.

В качестве примера на $n$ вершинах c $2n − 3$ ребрами, в котором две вершины $B$ и $C$ соединены со всеми (в том числе и друг с другом), а остальные вершины соединены только с $B$ и $C.$

Ответ:

$2n− 3$

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

Задача 9#35478

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

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

Показать доказательство

(a) Проведём индукцию по $n.$ База для $n= 1$ верна. Пусть в любом связном графе с $n− 1$ вершиной хотя бы $n− 2$ ребра. Покажем, что в связном графе с $n$ вершинами хотя бы $n− 1$ ребро. Пусть степени всех вершин хотя бы 2. Тогда суммарная степень хотя бы $2n,$ а значит, рёбер хотя бы $n.$ Пусть нашлась вершина $X,$ степень которой не более 1. Если ее степень равна 0, то в графе всего 1 вершина, поскольку граф связен, и утверждение задачи верно. Пусть теперь степень $X$ равна 1. Тогда удалим эту вершину вместе с исходящим из неё ребром. Предположим, что нарушилась связность. Тогда есть какие-то 2 вершины $A$ и $B,$ путь между которыми обязательно проходил через $X.$ Но степень $X$ равна 1, значит, на пути мы зашли в $X$ и вышли по тому же ребру. Тогда рассмотрим такой же путь, но без захода в $X.$ Так можно удалить все посещения $X$ на пути, значит, связность не нарушилась. Тогда можно применить предположение индукции. В графе с удаленной вершиной не менее $n − 2$ ребер, следовательно, в исходном графе не менее $(n− 2)+ 1= n− 1$ ребер.

(b) Как и в предыдущем пункте, проведём индукцию по $n.$ База индукции очевидна. Пусть в дереве на $n− 1$ вершине ровно $n − 2$ ребра. Найдём висячую вершину (которая всегда существует в дереве) и удалим её. Связность не нарушилась (мы доказывали это в предыдущем пункте), в графе стало на 1 вершину и на 1 ребро меньше. По предположению индукции теперь рёбер $n − 2,$ значит, изначально их было $n− 1,$ что и требовалось доказать.

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

Задача 10#35479

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

Показать ответ и решение

Запустим такой процесс. Найдём в графе цикл (если их нет, то граф уже дерево) и удалим любое его ребро. Докажем, что при этом граф не потерял связности: в самом деле, если мы в каком-то пути использовали удалённое ребро, то вместо него можно пройти по оставшейся части цикла. Продолжим так удалять рёбра циклов, пока циклы не исчезнут. Полученный граф и будет остовным деревом.

Ответ:

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

Задача 11#35487

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

Показать доказательство

Выделим в графе остовное дерево. Если удалить любую его висячую вершину, граф останется связным.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#39388

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

$PIC$

Показать ответ и решение

ЛПЛП

Ответ: ЛПЛП

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

Задача 13#81407

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

Подсказка 5

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

Показать ответ и решение

Представим описанную в условии сеть дорог в виде графа, вершинами которого являются города, развилки и перекрестки, а ребрами — дороги. Покажем, что этот граф является деревом, то есть связным графом без циклов. Связность следует из того, что из любого города можно проехать в любой другой, а любая развилка или перекресток должны быть соединены с каким-либо городом. Допустим, что в нашем графе есть цикл. Он не содержит двух и более вершин-городов, так как в этом случае, двигаясь в противоположных направлениях по циклу, мы могли бы получить два различных пути из одного города в другой. Далее, пусть между некоторыми городами $A$ и $B$ существует путь, содержащий какую-то вершину цикла. Он обязательно найдется, так как иначе эта вершина не могла бы быть в нашей сети. Но тогда, добавляя к этому пути «кольцо» вдоль цикла, мы получим еще один путь между $A$ и $B.$ Значит, циклов в нашем графе быть не может и это действительно дерево.

По условию задачи все концевые вершины дерева — города. Назовем эти города концевыми. Назовем также концевой город $B$ следующим за концевым городом $A,$ если по пути из $A$ в $B$ на каждой развилке выбирается самая правая дорога. Выберем какой-нибудь концевой город $A1$ и измерим расстояние между ним и следующим за ним концевым городом $A2.$ Потом измерим расстояние между $A2$ и следующим за ним концевым городом $A3$ и так далее. После не более чем $100$ таких измерений мы вернемся в исходный город $A1.$

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

Наконец, сложив измеренные величины и разделив сумму пополам, мы получим длину всей сети.

Ответ:

Да, можно

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

Задача 14#70630

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

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

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

Подсказка 1.

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

Показать ответ и решение

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

Допустим, что среди туристов имеется $25$ (или более) «богачей». Нарисуем граф: вершины — это города, из каждого города проведем самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню, за исключением единственного ребра, выходящего из корня, — это ребро в дереве как бы двустороннее. Возьмем богача, который расположен ближе всего к корню своего дерева. Этот богач будет в течение $25$ ходов самым близким к корню. Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф — это путь из $50$ вершин, богачи занимают первые $25$ вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй половины. Отсюда следует, что богачей не может быть больше $25,$ а также что количество переездов тоже не превосходит $25.$

Тогда бедных туристов тоже $25$ и они двигаются по аналогичному «бедному» пути, причем в начальный момент они занимают всю вторую половину «богатого» пути. Эти пути не имеют общих звеньев, и при этом движение бедняков таково, что с каждым ходом они должны освобождать от своего присутствия очередную вершину второй половины богатого пути, смещаясь гуськом в первую половину. Тогда движение туристов может происходить, например, следующим образом.

Обозначим города $A1,A2,...,A50.$ Допустим, что путь

A1 → A2 → A3 → ⋅⋅⋅→ A49 → A50

составлен из самых дорогих авиалиний, для определенности пусть цена перелета $Ai → Ai+1$ равна $106 − i$ рублей. А «бедный путь» пусть сначала проходит по городам с большими четными номерами, потом — по городам с большими нечетными, а далее — с малыми: сначала с четными, потом с нечетными:

A26 → A28 → ⋅⋅⋅→ A50 → A27 → A29 → ⋅⋅⋅→ A49 → → A2 → A4 → ⋅⋅⋅→ A24 → A1 → A3 → ⋅⋅⋅→ A25

Цены этих авиалинии пусть убывают от $49$ до $1$ рубля при движении вдоль этого пути. Цены остальных авиалиний назначим произвольно в диапазоне от $100$ до $100000$ рублей.

Ответ:

При $k= 25$

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

Задача 15#79336

В тайном обществе $2020$ членов, и у каждого есть счет в банке (на счету целое число рублей, которое может быть отрицательным). Время от времени один из членов общества переводит со своего счета на счет каждого из своих друзей, состоящих в обществе, по $1$ рублю. Известно, что с помощью цепочки таких переводов они могут перераспределить имеющиеся на счетах средства произвольным образом. Докажите, что в этом обществе ровно $2019$ пар друзей.

Показать доказательство

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

Предположим противное: пусть вершины $A1,A2,...,An$ образуют цикл. Для краткости введем обозначения $A =A1$ и $B = A2.$ По условию несколькими переводами можно переместить 1 рубль из $A$ в $B,$ т. е. добиться того, что счет вершины $A$ уменьшится на $1,$ вершины $B$ — увеличится на $1,$ а счета остальных вершин не изменятся. Рассмотрим такой способ, в котором суммарное количество переводов — наименьшее из возможных. Ясно, что порядок переводов не важен: результат определяется тем, сколько переводов сделано из каждой вершины.

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

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

В результате всех переводов счет в вершине $B$ должен увеличиться на $1$ и это увеличение уже достигается переводом из $A.$ Значит, все остальные соседи вершины $B$ должны быть нулевыми. В частности, вершина $A3$ — нулевая. Поскольку $A3$ отлична от $B,$ все ее соседи тоже нулевые, в том числе $A4.$ Применяя это рассуждение к вершинам цикла по очереди, в итоге получаем, что и вершина $A$ должна быть нулевой. Противоречие.

Полученное противоречие доказывает, что в графе нет циклов, следовательно, он является деревом. В любом дереве количество ребер на $1$ меньше, чем количество вершин, следовательно, в нашем графе ровно $2010$ ребер, что и требовалось.

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

Задача 16#96644

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

Докажите, что вы будете удалять Т-тетрамино, частично клетки которых являются листьями дерева, то условие связности сохранится.

Показать доказательство

Лемма. Если в связной клетчатой фигуре $n$ белых клеток, то черных клеток в ней не более, чем $3n+ 1.$

Доказательство. Составим дерево следующим образом: в качестве корня возьмем произвольную белую клетку фигуры, на следующий ярус поместим все соседние с ней черные, далее — все соседние с ними белые, кроме уже помещенных ранее и т.д. Из первой вершины на следующий ярус ведет не более $4$ ребер, из всех остальных — не более, чем по $3,$ откуда и следует искомая оценка.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к доказательству задачи. В нашем случае количество черных клеток лишь на $1$ меньше максимального, поэтому каждая белая клетка граничит минимум с тремя черными. Покажем индукцией по числу белых клеток, что нашу фигуру можно разрезать на Т-тетрамино. База очевидна. Пусть для $≤ n$ белых клеток все доказано. Возьмем фигуру с $n +1$ белой клеткой, рассмотрим путь максимальной длины в построенном выше дереве, а в нем — предпоследние слева и справа вершины. Обе они — белые (иначе после удаления одной связанной с ней висячей белой нарушится утверждение леммы). Хотя бы с одной из них связано три висячих черных. Вместе с ней они образуют Т-тетрамино. Удалив ее, оказываемся в условиях предположения индукции.