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