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

После закрытия одной дороги ровно 2 города А и В имеют степень вершины 99, а остальные - степень вершины 100.

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

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

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

Так как то далее можно осуществить перебор со следующими ограничениями: 1) (так как ; 2) числа и не содержат никаких простых множителей, кроме и В результате получаем три варианта: где , , соответственно.

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

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

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

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

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

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

Если считать, что озёра — вершины, а каналы — рёбра, то перед нами связный плоский граф с вершинами и рёбрами, значит мы можем использовать формулу Эйлера: откуда

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

Попытаемся удалить из данного наименьшее количество рёбер так, чтобы он стал планарным. Из неравенства понимаем, что в нём после удаления должно быть не более рёбер, а изначально в нём рёбер, значит необходимо удалить хотя бы ребра. С удалением каждого ребра исчезает хотя бы одно пересечение (иначе зачем удалять это ребро?). Таким образом, в исходном графе было хотя бы точки пересечения. Предъявим пример:

Пример: в каждой клетке сделаем разрез от левого нижнего угла до правого верхнего.

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

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

Пример (тут присутствуют не все доминошки, но те, которых нет, можно разместить произвольно):

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

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

Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим пауков (всего 1000 городов). Если то в одном из пауков выбраны все 4 города, что противоречит условию.

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

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

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

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

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

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

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

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

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

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

Итак, мы доказали, что в кратчайшем маршруте “обратно” нет вершины Следовательно, весь маршрут содержит менее вершин и менее стрелок.

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

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

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

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

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

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

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

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

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

База для проверяется непосредственно. Пусть оценка верна для всех Докажем ее для

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

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

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

(неравенство при следует при непосредственной проверке найденных значений, и при из предположения индукции), количество ребер в не превосходит

При для доказательства достаточно показать, что

что после раскрытия скобок и приведения подобных дает т.е. верно при

При для доказательства достаточно показать, что

что после раскрытия скобок и приведения подобных дает т.е. верно при

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

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

Если же в графе нет треугольников, то максимум количества ребер будет достигаться в случае полного двудольного графа с одинаковыми долями для четного а для нечетного — с долями отличающимися на Легко видеть, что такие двудольные графы являются примерами с нужным количеством ребер для всех Если же то примером с ребрами будет конструкция из треугольников, имеющих одно общее ребро.

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

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

С одной стороны, каждая пара учеников из разных отделений является похожей ровно для учеников; всего таких пар следовательно, С другой стороны, в любом одноцветном треугольнике каждые два ученика похожи для третьего; если же треугольник разноцветный (скажем, ребро отличается по цвету от других), то в нём ровно одна пара похожа для третьего. Так как количество одноцветных треугольников равно а разноцветных — то Значит, откуда