Двудольные графы и переформулировки к ним
Ошибка.
Попробуйте повторить позже
На доске 
отмечены 
клеток. Известно, что ладья, начав с любой из отмеченных клеток, может за несколько ходов оказаться в
любой строке, а также в любом столбце, причем она может перемещаться только по отмеченным клеткам. Какое наименьшее количество
клеток может быть отмечено на доске?
Подсказка 1
В условии задачи говорится скорее про отношение между строками и столбцами, чем между клетками исходной доски. Как лучше представлять доску, чтобы "разделить" столбцы и строки и выразить отношение уже между ними?
Подсказка 2
Популярным является представление доски как двудольного графа, где каждому столбцу поставлена в соответствие вершина левой доли, а каждой строке — правой. Чем будут клетки в данном представлении?
Подсказка 3
Для каждой отмеченной клетки, которая стоит на пересечение i строки и j столбца проведем ребро. Каким является граф, если, начиная в любом столбце (строке), можно перейти в любой столбец (строку)?
Подсказка 4
Связным. Как оценить снизу количество ребер в связном графе?
Подсказка 5
Докажите, что в связном графе, количество ребер не меньше, чем на 1 количества вершин граф. Примените полученный результат в задаче.
Пример. Отметим все клетки первой строки и первого столбца.
Оценка. Построим двудольный граф, каждому столбцу поставим в соответствие вершину в левой доли, а каждой строке — в правой.
Для каждой отмеченной клетки, которая стоит на пересечение 
строки и 
столбца проведем ребро, между соответствующими им
вершинами.
По условию, начав с любого столбца(строки) 
мы можем дойти до любой столбца(строки) 
то есть существует путь в графе между
вершинами, соответствующими произвольными вершинами 
и 
а значит, полученный граф является связным и количество его ребер не
меньше, чем на 1 меньше количества вершин графа, то есть хотя бы
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
