Граф G - дерево с 2n листьями. Докажите, что к G можно добавить n ребер так, чтобы он стал 2-реберно-связным (т.е. не распадался при удалении любого из ребер).

Мои мысли: очевидно, что соединять надо листья между собой. Я пытаюсь придумать алгоритм соединения, и он у меня примерно такой: рассмотрим исходное дерево и ребра в нем, которые не инцидентны с листьями. Удалим ребро, граф распадётся на 2 компоненты, соединим 1 лист из 1ой компоненты с листом из 2ой. Вернём удалённое ребро и будем делать удаления до тех пор, пока все листья не заимеют пару (или же пока не кончатся подходящие рёбра). Если закончились подходящие рёбра, а листья остались, то просто разбиваем их на пары и досоединяем. А вот если листья кончились, то не очень понятно, как доказать, что всё норм.

Буду рада и развитию своего решения, если оно правильное, и другому решению.

задан 17 Окт '16 0:59

изменен 17 Окт '16 1:01

Вопрос сегодня уже звучал, ответ на него был дан здесь.

(17 Окт '16 1:33) falcao
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Повтор вопроса". Закрывший - falcao 17 Окт '16 1:33

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,789
×631

задан
17 Окт '16 0:59

показан
540 раз

обновлен
17 Окт '16 1:33

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru