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