Двудольные графы и переформулировки к ним

Пример. Отметим все клетки первой строки и первого столбца.

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

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

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

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

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

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

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

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

Обозначим количество мальчиков через , а девочек — через . Тогда количество рёбер со стороны мальчиков равно , а со стороны девочек оно равно . Так как это на самом деле все рёбра в графе, мы получаем . Из этого равенства следует, что делится на 4. Пусть , тогда из равенства выше получаем, что , а общее количество детей равно — число, делящееся на 7.

Раскрасим черные клетки доски в два цвета. Тогда слон каждый раз будет менять цвет, на котором стоит. Клеток второго цвета 16, поэтому всего слон сможет посетить не более клеток. Слон может посетить 33 клетки.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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