Циклы в графах

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

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

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

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

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

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

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

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

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

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

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

Ответ: Нет.

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

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

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

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

Ответ: 148.

Решение. Пример на 148. Построим ориентированный граф, вершинами которого будут числа от 1 до 100 , а каждое из ребер связывает номер места, на котором стоит том с данным номером, с самим этим номером. Поскольку из каждой вершины этого графа выходит ровно одно ребро, и в каждую его вершину входит ровно одно ребро, все его вершины и ребра разбиваются на непересекающиеся ориентированные циклы. Цикл, в который входит красный том, назовем особым, прочие — обычными. Возьмем любой обычный цикл и добавим в него красный том (пусть его номер равен ): . Затем последовательно поменяем местами красный том со всеми остальными элементами получившегося цикла. В итоге все элементы исходного обычного цикла встанут на предписанные им места, а красный том вернется на исходное место. Проделаем описанную процедуру со всеми обычными циклами длины, не меньшей 2 , а напоследок «прокрутим» особый цикл, после чего все тома окажутся на своих местах, т.е. будут идти в порядке возрастания. При этом на приведение в порядок каждого цикла длины , кроме особого, у нас ушла перестановка, а на особый цикл — перестановка, а всего — перестановки, где — число циклов длины не меньше 2 . Поскольку циклов длины 2 и больше не более 50, мы совершили не больше 148 перестановок. Оценка. Пусть получилось 50 циклов длины 2. На приведение в порядок каждого обычного цикла нужно минимум 3 перестановки: убрать один том, поставить на его место другой и поставить на место другого первый. Еще одна перестановка нужна на особый цикл. Итого .

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

Ответ: 27. Решение. Напомним, что через обозначается полный двудольный граф на 6 вершинах, то есть граф, три вершины которого можно покрасить в один цвет, а три — в другой так, что любые две одноцветные вершины будут соединены ребром, а любые две разноцветные — нет. В графе циклов длины 4, потому что цвета вершин в цикле чередуются, и по две вершины каждого цвета в можно выбрать способами. Отсюда получается пример на 27 циклов: достаточно взять три графа , а из двух оставшихся вершин рёбер не проводить.

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

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

Пусть в нашем графе ровно компонент связности вида . Тогда в нём вершин, входящих в «плохие» компоненты, где через каждое ребро проходит не более 3 циклов длины 4. В этих компонентах не более рёбер и, стало быть, не более циклов длины 4, а всего в графе этих циклов не больше, чем . Если же в графе 3 компоненты связности вида , то в этих компонентах 27 циклов длины 4 , а две оставшиеся вершины, не будучи связанными с остальными 18 -ю, новых циклов длины 4 добавить не могут. Итак, циклов длины 4 у нас всегда не более 27.

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

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

Пусть . Всего у 20 ребер 40 концов и легко понять, что есть не менее 12 ребер, концы которых не совпадают с другими концами наших 20 ребер. Выберем 5 таких ребер — пусть это ребра . Обозначим через множество, состоящие из вершин и произвольных 40 вершин не входящих в . Применим операцию ко всем 50 вершинам множества . Тогда на каждом из ребер образуется по 30 треугольников (со всеми вершинами, не входящими в ), а на каждом из 15 оставшихся ребер — по 50 треугольников (со всеми вершинами множества ). Итого получается треугольников.