Тема . Клетчатые задачи

Увидеть граф (переформулировки)

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела клетчатые задачи
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#103479

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

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Доказать существование покраски в графах чаще всего нередко можно конструктивно. Придумайте способ покраски дерева нужным образом.

Подсказка 6

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

Показать доказательство

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

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

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!