Графы и турниры → .06 Подвешивание, ранжирование, упорядочивание в графах

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

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

образуют цикл длины 5, что противоречит условию. Остаётся заметить, что вершин хотя бы что и требовалось доказать.

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

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

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

Рассмотрим граф, в котором вершинами будут города, а ребрами — дороги. Подвесим граф за вершину Для каждой вершины определим её глубину — наименьшую длину пути до этой вершины из Назовём уровнем множество вершин одной глубины. Заметим, что вершина глубины может быть соединена ребром только с вершинами глубин или так что если глубины вершин отличаются хотя бы на 3, то у них нет общих соседей. Предположим, что есть вершина глубины более чем 63. Тогда рассмотрим вершины

где глубина будет Каждая из этих вершин имеет степень хотя бы 93, причём их соседи не пересекаются, так что всего вершин хотя бы противоречие. Значит, из до любой другой вершины можно добраться с не более чем 62 пересадками. Из независимости выбора получаем требуемое в условии.

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

Представим страну как граф, где вершины — города, а ребра — дороги между городами.

“Подвесим” наш граф за какую-либо вершину. На первом уровне у нас будет только одна вершина, за которую мы подвешиваем. На втором уровне у нас будут все вершины, в которые можно попасть из вершины на первом уровне. На третьем уровне будут все вершины, в которые можно попасть из вершин второго уровня, которых нет на предыдущих двух уровнях. На четвертом уровне будут все вершины, в которые можно попасть из вершин третьего уровня, которых нет на предыдущих трех уровнях.

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

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

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

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

С другой стороны, перелёта всегда достаточно, чтобы добраться от любого города до любого.

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

Каждый город на уровне может быть соединён только с городами на уровнях и

Это значит, что на каждых трёх подряд идущих уровнях в сумме хотя бы города. Кроме того, на двух первых уровнях не менее городов, как и на двух последних.

Это означает, что у нас не может быть более

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

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

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

У кроме есть ещё знакомых, а у , кроме ещё Поскольку то у и есть хотя бы один общий знакомый Тройка и есть искомая тройка человек.

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

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

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

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

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

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

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

Далее рассмотрим какую-нибудь вершину третьего уровня. Она соединена не более чем с вершинами второго уровня, а значит мы сможем её покрасить в какой-нибудь цвет, не нарушая правильности. Покажем, что аналогично мы можем закрасить все вершины третьего уровня. Предположим, что это не так. Пусть мы дошли до некоторой вершины третьего уровня, для которой не осталось цветов. Но такого не может быть, поскольку она соединена суммарно с не более чем вершинами из третьего и второго уровней. Следовательно, третий уровень мы сможем закрасить. Аналогично закрасим остальные уровни. Что и требовалось.

Возьмём вершину степени 10 и поместим на первый уровень. На второй уровень поместим всех соседей . На третий уровень поместим всех соседей соседей , ещё не появившихся на картинке, и так далее. У нас образуется 10 “веточек”, началами которых будут соседи . Посмотрим, чем заканчивается каждая веточка, то есть на самые низкие вершины веточки. Из них и выходит по одному ребру: только наверх, рёбра не могут идти на тот же уровень или вниз. При этом в каждой веточке есть хотя бы одна самая низкая вершина, что нам и даёт искомые 10 вершин.

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

Равенство невозможно, поскольку имело бы своими следствиями взаимоисключающие равенства и так как еще соединена с

Допустим, что и Тогда то есть город соединён либо с либо с Но соединён с и а — с и

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

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

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

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

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

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

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

Действительно, все рёбра, выходящие из вершин с номерами от до делятся на два типа:

идущие в вершины с номерами от до — таких не болыше

идущие в вершины с номерами от до — таких не больше но каждое мы можем посчитать по два раза.

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

противоречие.

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

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

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

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

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

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