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

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

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

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

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

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

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

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

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

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

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

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

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

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

Будем называть населенные пункты точками. Возьмем любую точку Она соединена не более, чем с тремя точками Любая другая точка должна быть соединена с одной из точек (поскольку она не соединена с ). Но каждая из них уже соединена с так что может быть соединена не более чем с двумя другими точками, Следовательно, общее число точек не более

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

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