Графы и турниры

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

Таким образом, переход доказан.

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

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

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

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

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

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

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

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

откуда

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

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

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

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

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

База очевидна.

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

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

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

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

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

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

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

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

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

Пример. Пусть все школьники дружат между собой. Тогда можно обойтись фруктами и десертом.

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