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

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

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

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

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

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

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

2. Распишем . Поскольку многочлен линеен по каждой переменной, получаем, что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам не более четырех мономчиков, противоречие.

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

Для этого нужно подвесить за и поочередно удалять вершины с самого нижнего уровня. Теперь нужно понять, что при удалении только одной вершины граф остается хорошим. Для этого подставим 0 в . Получим, что все слагаемые, в которые входило в хотя бы первой степени, обнулились, а значит остались в точности те, где — висячая вершина. А все такие деревья устроены так: выбрано дерево в графе , и потом одна из вершин из окрестности соединена с . Тогда многочлен после подстановки нуля равен . Подстановка нуля сохраняет раскладываемость на множители, значит тоже раскладываемый, значит, при удалении вершины граф останется хорошим.

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

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

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

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

Теперь очевидно, что второй сомножитель равен , и лемма доказана. ________________________

Пусть - граф из леммы 1. Мы в лемме 1 уже выяснили как устроены деревья в графе , поэтому нужно разобраться с тем, как они устроены в . Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем одно из двух - либо не проводим ребро между и , и это слагаемое такое же как в , либо проводим, и тогда каждую из долей соединяем с ровно одной из этих вершин. Стало быть, сумма всех первых слагаемых даст нам , а сумма вторых равна

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве примера на вершинах c ребрами, в котором две вершины и соединены со всеми (в том числе и друг с другом), а остальные вершины соединены только с и

Будем проводить рёбра по одному и следить за количеством несвязанных кусочков. Изначально у нас есть вершин, никак не соединённых между собой. При проведении первого ребра будут связаны две вершины. Далее, как бы мы ни проводили новые рёбра, количество несвязанных кусочков будет уменьшаться на 1: ведь если мы проведём ребро внутри связанного кусочка, у нас образуется цикл. В конце должен получиться один связанный кусочек — весь граф. Таким образом, всего будет проведено ребро.

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

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

ЛПЛП

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

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

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

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

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

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

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

Обозначим города Допустим, что путь

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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