Графы и турниры → .04 Считаем рёбра

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

Следовательно,

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

Складывая эти неравенства по всем неупорядоченным парам смежных вершин многогранника, получаем

По доказанному выше неравенству отсюда следует требуемая оценка.

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

Рассмотрим граф, в котором вершины — ребра, города — дороги. Выделим в нем максимальную антиклику . Если она размера 7 или более, то нам повезло. Иначе отделим эти вершины, а в оставшемся графе снова выберем максимальную антиклику . Наберем таким образом 8 непересекающихся антиклик. Теперь в одну часть отнесем все вершины этих восьми антиклик (их будет не более ), а во вторую часть — все оставшиеся вершины. Заметим, что любая оставшаяся вершина имеет хотя бы по одной смежной в каждой антиклике, иначе на очередном шаге эту вершину можно было бы присоединить к этой антиклике. Следовательно, из каждой вершины второй части, которых хотя бы 52, выходит не менее 8 ребер в первую часть. Итого, не менее 416 ребер между частями. Противоречие.

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

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

Первое решение. Докажем сначала следующую лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем по индукции.

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

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

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

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

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

Второе решение. Cначала докажем лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер. Докажем это.

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

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

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

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

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

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

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

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

Приведём пример на Введём систему координат так, что левая нижняя точка имеет координаты Удалим все рёбра, соединяющие вершины с координатами и — чётное.

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

Разделим ребра на два типа: те, что соединяют две клетки из одной вертикали и те, что соединяют две клетки из одной горизонтали.

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

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

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

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

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

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

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

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

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

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

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

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

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