Деревья и остовные деревья
Ошибка.
Попробуйте повторить позже
Дан связный граф на вершинах. Известно, что при удалении ребер любого простого цикла этот граф теряет связность. Какое
наибольшее число ребер может быть в этом графе?
Подсказка 1:
Для оценки будет очень удобно разделить все рёбра на два множества так, что если удалить одно из них, граф останется связным (для второго так может не работать). Это может позволить удалить цикл, не потеряв связности.
Подсказка 2:
В этом поможет остовное дерево. Но выделить его нужно хитрым образом.
Подсказка 3:
Выделите его таким образом, чтобы в нём участвовали все рёбра, исходящие из корневой вершины. Объясните, почему так сделать можно.
Подсказка 4:
Рассмотрите граф из рёбер, не попавших в остовное дерево. Кажется, если там слишком много рёбер, найдётся цикл, который можно удалить без потери связности.
Предположим, что в графе хотя бы ребра. Выделим в нём остовное дерево, которое будет содержать все рёбра, выходящие из
какой-нибудь вершины. Покажем, что так сделать можно. Выделим какое-нибудь остовное дерево. Рассмотрим главную вершину (первый
уровень дерева). Также рассмотрим какую-нибудь вершину
которая не находится на втором уровне дерева и при этом в исходном графе
соединена с
Перенесём вершину
на второй уровень. Ребро, соединяющее вершину
с вершиной, находящейся уровнем выше,
удалим из дерева.
Теперь рассмотрим граф без рёбер, попавших в остовное дерево. В полученном графе вершина и
ребро (все рёбра вершины
в остовном дереве, поэтому её можно не учитывать). Разберём случаи.
Полученный граф связен. В этом случае в нём есть цикл, притом если его удалить, исходный граф останется связным, поскольку мы
выделили остовное дерево.
Полученный граф не связен, то есть состоит из нескольких компонент связности. Если каждая из компонент является деревом, то
количество рёбер в графе меньше, чем
Если же какая-то из компонент не является деревом, то есть имеет цикл, то мы приходим к
такому же противоречию, как в первом случае.
В качестве примера на вершинах c
ребрами, в котором две вершины
и
соединены со всеми (в том числе и друг с
другом), а остальные вершины соединены только с
и
Специальные программы

Программа
лояльности вер. 2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к твоему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас важно быть полезными учителям по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

