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

Оценка. Обозначим через количество стран, а через и — количество мужчин и женщин в -й стране соответственно. По условию

Заметим, что

Значит,

По условию поэтому Заметим, что если из -й страны приехало нечётное число участников, то Следовательно, стран с нечётным числом участников не более трёх.

Пример. Пусть стран всего три, из двух приехало по одному мужчине, а из третьей — одна женщина.

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

стрелок ведущих из в или

Алгоритм Эдмондса-Карпа с обходом в ширину

Шаги алгоритма:

1.

Инициализация: поток для всех рёбер.

2.

Пока существует путь из истока в сток в остаточной сети

• Найти кратчайший путь из в с помощью BFS (обход в ширину).
• Увеличить поток вдоль на величину остаточной пропускной способности
• Обновить остаточную сеть

Корректность:

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

Пример несходящегося алгоритма: Рассмотрим сеть с источником стоком рёбрами и пропускными способностями:

а пропускные способности остальных рёбер равны целому числу

Константа удовлетворяет условию:

Используем пути в остаточном графе:

• После шагов и остаточные пропускные способности рёбер имеют вид где

• Цикл из путей может повторяться бесконечно. Полный поток после шага

  

• При бесконечном выполнении поток сходится к:

  

  но максимальный поток равен

Будем называть замкнутый маршрут из пяти дорог, существование которого запрещено условием, 5-циклом.

Докажем сначала, что если мы рассмотрим какие-либо шесть городов, между ними будет проведено не более 10 дорог из возможных 15. Предположим противное: пусть между какими-то шестью городами проведено не менее 11 дорог. Тогда среди этих шести городов и соединяющих их дорог найдём 5-цикл, существование которого запрещено условием.

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

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

Какие-то две антидороги точно выходят из одного города. Исключим его и рассмотрим оставшиеся пять городов. Пронумеруем их числами от 1 до 5. Между этими городами не более двух антидорог. Опять же, достаточно найти 5-цикл в ситуации, когда этих антидорог ровно две, в противном случае он найдётся и подавно.

Есть две возможных ситуации: когда эти антидороги имеют общий конец, и когда не имеют.

В первом случае без ограничения можно считать, что антидороги соединяют город 1 с городами 2 и 3. Тогда мы можем найти следующий 5-цикл: 1-4-2-3-5-1.

Во втором случае можно считать, что наши антидороги соединяют город 1 с городом 2, а город 3 с городом 4. Тогда мы сможем найти такой 5-цикл: 1-3-5-2-4-1.

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

Докажем это чуть более строго. В каждой шестёрке городов не более 10 дорог. Всего этих шестёрок Итого получаем дорог, однако, каждая из них посчитана несколько раз. А именно, к каждой паре городов можно подобрать ещё 4 города способами, значит, именно столько раз мы посчитали каждую дорогу.

Таким образом, всего дорог не более

(a) Рассмотрим граф, в котором дети это вершины. Будем проводить ребро, если дети дружат. По условию все вершины имеют степень 2, значит, в графе 30 рёбер. Будем выбирать произвольное ребро, выкидывать вершины на его концах и все рёбра, исходящие из этих вершин. Так мы удалим не более 3 рёбер (поскольку степени вершин не превосходят 2, а одно из рёбер у этих вершин общее). Значит, если проделать такой процесс 9 раз, останется хотя бы 3 ребра, и удастся сделать десятый шаг. Составим пары для дежурств из учеников, соответствующих концам выбранных ребер. Тогда дежурят только друзья, и никто не дежурит дважды, поскольку мы сразу же удаляем вершины. Таким образом, мы выбрали 10 пар.

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

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

Назовём антитреугольником тройку вершин, которые не образуют треугольник. Оценим число антитреугольников. Всего антирёбер

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

Пусть — степень -ой вершины в дополнительном графе. Каждый путь длины 2 содержит ровно одну центральную вершину, так что

По неравенству о средних оценим

Тогда всего антитреугольников не более, чем

Подставляя в оценку из условия вместо получаем:

Мы добавили к требуемой оценке число, которое не меньше числа антитреугольников, и получили в точности количество всех троек вершин. Значит, треугольников не меньше что и требовалось.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Каждый появляется каждый раз, когда является концом ребра из , то есть раз; всего пар , значит вычитается раз. По неравенству Коши–Буняковского:

Наконец, сумма Следовательно,

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

Посчитаем число троек где дружит с и с а и не дружат.

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

Имеем:

Рассмотрим граф, вершинами которого являются отмеченные точки, а рёбрами — проведённые отрезки.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Подграф с новыми числами на рёбрах удовлетворяет условию с той же константой

Доказательство леммы. Заметим, что для каждого -рёбра есть одно и то же количество -шестёрок, в которые входят оба его конца. И наоборот, для любой -шестёрки среди 15 рёбер между её вершинами есть одно и то же количество -рёбер. То же верно для -рёбер и для -рёбер. Значит, сумма чисел на рёбрах в -шестёрке в новой расстановке есть среднее сумм по всем -шестёркам в старой расстановке, то есть среднее нескольких чисел, не больших – значит, Аналогичное утверждение верно для сумм в -шестёрках. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Далее изучаем новую расстановку. Рассмотрим случаи.

Случай Иными словами, есть ровно одна -шестёрка, на которой пятнадцать -рёбер, и шесть -шестёрок, на каждой из которых десять -рёбер и пять -рёбер. Имеем систему неравенств:

Умножим первое на сложим со вторым, умноженным на 3, получим откуда

Случай Теперь у нас две -вершины и пять -вершин, то есть на -шестёрке есть десять -рёбер и пять -рёбер, а на -шестёрке – шесть -рёбер, восемь -рёбер и одно -ребро. Имеем

Исключая получаем

значит,

Случай Аналогично предыдущему, имеем

Избавляясь на этот раз от получаем откуда

Случаи сводятся к рассмотренным умножением всех чисел на что ведёт к замене Итак, оценка доказана.

Пример. Любое число вершин от двух до 999995 объявим вершинами типа остальные – вершинами типа На всех рёбрах между двумя вершинами типа напишем число на всех остальных – число 1. Тогда, если в шестёрке вершин хотя бы пять -вершин, то сумма в ней не больше а иначе – не меньше

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

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

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

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

Обозначим количество городов в группах и через и соответственно, Пусть в городов не меньше, чем в то есть В есть город Z, из которого выходит не менее дорог в города из Кроме того, из выходит дорог к городам группы Значит, из выходит не менее дорог. Противоречие.

Случай, когда в больше городов, чем в рассматривается аналогично.

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

Теперь приведём пример на Нужно ставить королей в следующем порядке на клетки с координатами:

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

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

Значит, между этими подграфами не более рёбер. Внутри же каждого из этих подграфов не более рёбер. Значит, всего в графе не более

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

_________________________________________________________________________________________________________________________________________________________________________________

Приведём пример на рёбер. Разбиваем города на групп по городов. Внутри групп между городами авиалиний нет, а между городами из разных групп — есть.

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

по неравенству между средним квадратическим и средним арифметическим

Мы показали, что для произвольного подграфа в примере выполняется условие задачи.

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

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

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

(a) Рассмотрим произвольного человека Пусть он знаком с людьми Заметим, что если какие-то и дружат, мы нашли треугольник Предположим, что они между собой не дружат. Пусть всего в компании человек. Тогда каждый человек может дружить не более чем с людьми. Учитывая, что получаем противоречие.

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

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

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

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

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

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

Оценим количество ребер между людьми из разных множеств и

С одной стороны, не больше суммы степеней вершин множества откуда

С другой стороны, из каждой вершины множества не более ребер идет в вершины множества и значит, не менее ребер идет в вершины множества Отсюда

Получаем неравенство:

откуда Это означает, что всего лжецов не менее

Пример. Как и прежде, номер человека будет означать его ответ. Возьмем два множества людей:

и

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

У человека будет всего друзей:

из множества и все люди множества кроме него самого. При этом все люди в — лжецы, а в — рыцари. Видим, что все условия задачи выполняются.

1) Рассмотрим красный шестиугольник и концентрический синий шестиугольник внутри него. Соединим соответственные вершины синими ребрами.

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

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

4) Размыкаем синее рёбер в точке пересечения с красным, получаем две точки, соединим их какой-нибудь выпуклой красной кривой, поставим на ней пять точек и отметим "внутри"ещё две точки. Точки на кривой соединяем красными ребрами, а "внутрение"точки друг с другом синими. Осталось из внутренних провести два синих ребра, для этого соединим их точками с кривой.