Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Вот еще задачка. Докажите,что из каждого связного графа можно удалить вершину (вместе со всеми выходящими из нее ребрами) так, что он останется связным.
Deggial
Re: Теория графов
15.04.2013, 17:02
Попробуйте воспользоваться покрывающим деревом.
Monster
Re: Теория графов
15.04.2013, 21:20
Вы имеете ввиду остов?Я понимаю,что есть какая-то связь.Объясните.
Sonic86
Re: Теория графов
16.04.2013, 07:03
Решите задачу сначала для деревьев. Можно ли в любом (неединичном) дереве удалить вершину так, что оно останется деревом?
Monster
Re: Теория графов
16.04.2013, 17:30
Абсолютно точно.Можно удалить одну из висячих вершин.А что дальше?