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

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

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

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

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

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

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

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

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

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

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

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

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

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

Раскрасим строки доски в 2 цвета: строки с нечётными номерами в первый, а с чётными — во второй. Тогда слон каждый раз будет менять цвет, на котором стоит. Чёрных клеток второго цвета 16, поэтому всего слон сможет посетить не более клеток.

Приведём пример, в котором посетим 33 клетки. Начнём с пойдём по двум нижним строкам: далее пойдём в Заметим, что мы оказались в угловой клетке пустой доски причём нам нужно обойти 25 клеток. Используем аналогичный обход двух строк, окажемся в клетке и так далее. В итоге мы посетим 33 клетки и закончим в

Раскрасим кубики в шахматном порядке (угловые кубики считаем черными). Тогда мышка съела 12 белых кубиков и 14 черных кубиков. Но при переходе к следующему кубику меняется цвет, поэтому мышка не сможет съесть весь куб кроме центрального кубика.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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