Связность и связные подграфы (клики)
Ошибка.
Попробуйте повторить позже
В связном графе 
даны два непересекающихся множества вершин 
и 
между этими множествами нет ни одного ребра. Пусть в
графе 
ровно 
компонент связности, а в графе 
ровно 
компонент связности. Какое наименьшее количество компонент
связности может быть в графе 
Напомним, что для множества вершин 
через 
обозначается граф, полученный из 
в результате удаления всех вершин
множества 
и всех выходящих из них ребер.
Источники:
Подсказка 1
Операцию G - W, не так удобно рассматривать в данной задаче, как операцию G\Е(это граф получающий удалением в G всех ребер, входящих в Е), где Е — множество рёбер, у которых хотя бы один конец лежит в W.
Подсказка 2
Пусть количество компонент связанности в графе H = G\(E₁∩E₂) равно k, где G — связный граф, а E₁ и E₂ — два непересекающихся множества его рёбер. Пусть n₁ и n₂ — количество компонент связанности в G\E₁ и G\E₂ соответственно.
Подсказка 3
Если добавить и те, и другие ребра из прошлой подсказки, то граф станет связным, тогда можно составить неравенство для k, n₁ и n₂, которое и даст оценку для k.
Подсказка 4
Теперь можно использовать полученную оценку для G, Eₓ и Eᵧ. Тогда, если обозначить vₓ и vᵧ как количество вершин множества X и Y соответственно, то можно точно выразить число компонент связанности G\Eₓ и G\Eᵧ. Тогда, после применения ранее полученной оценки, останется привести для неё пример.
Пример графа показан на рисунке. Множество 
содержит 
вершину, множество 
— 
вершину.
_________________________________________________________________________________________________________________________________________________________________________________
Оценка. Для графа 
и некоторого множества его ребер 
через 
обозначим граф, получающийся из графа 
удалением всех его ребер, входящих в 
, т.е. граф 
.
_________________________________________________________________________________________________________________________________________________________________________________
Лемма. Пусть 
— связный граф, и пусть 
и 
— два непересекающихся множества его ребер. Обозначим через 
(
)
количество компонент связности графа 
. Тогда количество компонент связности графа 
не меньше, чем
.
_________________________________________________________________________________________________________________________________________________________________________________
Доказательство. Пусть в графе 
ровно 
компонент связности. Если добавить к 
все ребра из множества 
, то
получится 
компонент связности. Поэтому если мы будем последовательно добавлять в граф 
те ребра из 
, которые уменьшают
число компонент связности, то, добавив в точности 
ребер из 
, получим 
компонент связности (поскольку добавление каждого
ребра уменьшает число компонент связности не более, чем на 1). Добавление остальных ребер из 
уже не уменьшит
количество компонент связности. Аналогично к графу 
можно добавить такие 
ребер из множества 
, что в
итоге получаются все 
компонент связности графа 
. Но если к графу 
добавить и те, и другие ребра (в общей
сложности 
ребер), то граф станет связным. Следовательно, 
и, значит,
.
_________________________________________________________________________________________________________________________________________________________________________________
Обозначим через 
и 
количества вершин в множествах 
и 
. Пусть 
— множество ребер, хотя бы один конец, который
лежит в 
, а 
— множество ребер, хотя бы один конец которых лежит в 
. Поскольку между вершинами из 
и 
нет
ни одного ребра, множества 
и 
не пересекаются. Тогда в графе 
ровно 
компонент связности
(среди них 
компонент состоят из одной вершины), в графе 
ровно 
компонент связности, а в графе
ровно 
компонент связности, где 
— число компонент связности в графе 
. Тогда по
лемме
следовательно, 
.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
