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