Теория графов

[Monster]

Вот еще задачка.
Докажите,что из каждого связного графа можно удалить вершину (вместе со всеми выходящими из нее ребрами) так, что он останется связным.

[Deggial]

Попробуйте воспользоваться покрывающим деревом.

[Monster]

Вы имеете ввиду остов?Я понимаю,что есть какая-то связь.Объясните.

[Sonic86]

Решите задачу сначала для деревьев. Можно ли в любом (неединичном) дереве удалить вершину так, что оно останется деревом?

[Monster]

Абсолютно точно.Можно удалить одну из висячих вершин.А что дальше?

[Deggial]

Monster в сообщении #711140 писал(а):

Абсолютно точно.Можно удалить одну из висячих вершин.А что дальше?

Как можно связать остовы и связные графы? Скомбинируйте имеющуюся у Вас информацию.

[Monster]

У любого связного графа есть остов.Остов-дерево.Но почему если мы выкинем висячую вершину из остова,то начальный граф останется связным?

[iifat]

Похоже, осталось себе представить несвязный граф со связным остовом -- либо доказать несуществование такового.

[Deggial]

Monster в сообщении #711212 писал(а):

то начальный граф останется связным?

Вот Вы удалили вершину, которая является висячей для остова. Что произойдет с остовом после удаления вершины? Остов останется деревом?

[Monster]

Ну конечно.Связного остова в несвязном графе не существует.Понял.Большое спасибо.