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

Ориентированный граф ациклический, а значит, мы можем расположить вершины в таком порядке, чтобы ребро шло из вершины с меньшим номером в вершину с большим номером. Запустим процесс. Будем идти по вершинам, начиная с первой, и закидывать их в группу с минимальным номером, чтобы требуемые условия выполнялись. Пусть мы дошли до -й вершины и не смогли её добавить ни в одну из групп. Это значит, что в -й группе есть вершина с некоторым номером из которой идёт ребро в А почему не получилось поместить вершину в группу? Потому что в ней есть некоторая вершина из которой идёт ребро в Продолжая такие рассуждения для всех групп, получим путь длины которого по условию быть не должно, пришли к противоречию.

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

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

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

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

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

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

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 города способами, значит, именно столько раз мы посчитали каждую дорогу.

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

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

Приведём пример разбиения на пары для первых -ти раундов.

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

1.

-ый сыграл со -ым. Тогда имеем следующую ситуацию:

	1	2	3	4	5	6	7	8
1	X	6	1	2	3	4	5	No
2		X	5	1	2	3	4	No
3			X	3			2	4
4				X	4			5
5					X	5		1
6						X	1	2
7							X	3
8								X

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

	1	2	3	4	5	6	7	8
1	X	6	1	2	3	4	5	No
2		X	5	1	2	3	4	No
3			X	3	6	No	2	4
4				X	4	6	No	5
5					X	5	6	1
6						X	1	2
7							X	3
8								X

2.

-ый сыграл с -ым. Тогда имеем следующую ситуацию:

	1	2	3	4	5	6	7	8
1	X	No	1	2	3	4	5	6
2		X	5	1	2	3	4	No
3			X	3			2	4
4				X	4			5
5					X	5		1
6						X	1	2
7							X	3
8								X

Далее аналогичными рассуждениями из предыдущего пункта получаем противоречие.

В обоих случаях противоречие, следовательно, пример рабочий.

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

Занумеруем города числами 0, 1, 2, …, 29 так, чтобы изначально у нас был цикл Добавим 9 авиалиний …, (а 10-ю авиалинию добавим какую угодно).

Покажем, что условие выполняется. Возьмем любые два города и От можно не более чем за 1 перелёт добраться до города с номером, кратным 3. Аналогично, от можно не более чем за 1 перелёт добраться до города с номером, кратным 3. А между городами и либо есть путь не более, чем из двух перелётов, так как все города с номерами, кратными 3, соединены с городом номер 0.

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

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

Рассмотрим граф, в котором вершины это команды. Будем проводить ребро, если они ещё не сыграли. Легко проверить, что если вершин не больше 4, то турнир можно закончить за 3 дня. Теперь пусть вершин хотя бы 5. Пусть имеется вершина степени не меньше 3. Рассмотрим четверку: и три команды, с которыми она не играла. Добавим к этой четверке любую команду. Тогда в получившейся пятерке не выполняется условие на расстановку для вершины Значит, степень каждой вершины не превосходит 2.

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

(a) Покажем, что каждая компонента связности графа является простым циклом. Тогда разбиение на компоненты связности будет искомым.

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

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

(b) Аналогично пункту (a) будем считать граф связным и запустим покраску. Если есть вершина степени 0, то весь граф состоит только из неё. сама по себе образует цепочку. Если в графе нет вершин степени 1, то по пункту (a) мы найдём простой цикл. Если же есть вершина степени 1, то начнём покраску из неё. Граф конечен, поэтому процесс остановится, причём вернуться в уже посещенную вершину нельзя. Значит, мы закончим в другой вершине степени 1. Тогда получилась цепочка. Аналогично циклу, мы обошли весь граф.

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

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

Рассмотрим граф, в котором клеточки многоугольника будут вершинами, ребро будем проводить, если клеточки граничат по стороне. Каждому ребру сопоставим стороны клеточек, которые мы пересекаем этим ребром. Так, каждому ребру будет сопоставлено по 2 стороны. Заметим, что стороны клеток, которые пересечены ребром, оказываются внутри фигуры, поэтому не учитываются при подсчете периметра. Граф связен, поэтому там хотя бы ребро. Значит, сторон, которые не учитываются при подсчете периметра, хотя бы Оставшихся сторон не более чем В качестве примера на подходит полоска

Пусть в дереве вершин, тогда там ребро. Пусть висячих вершин Тогда невисячих причём каждая имеет степень 2. Значит, суммарная степень вершин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

Нечётных степеней среди них

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

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

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

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

Имеем: