Страница 68 номер 92, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Сколько рёбер в связном графе с \(n\) вершинами, если в нём имеется единственный цикл?
Пусть в связном графе \(n\) вершин и ровно один цикл.
Удалим любое ребро этого цикла: связность сохранится — между его концами остаётся путь по другой части цикла, а циклов не остаётся вовсе, ведь цикл был единственным.
Получилось дерево с \(n\) вершинами, в нём \(n-1\) ребро. Вернём удалённое ребро: рёбер \(n - 1 + 1 = n\).
Ответ: в связном графе с \(n\) вершинами и единственным циклом ровно \(n\) рёбер — на одно больше, чем в дереве с тем же числом вершин.
Сколько рёбер в связном графе с \(n\) вершинами, если в нём имеется единственный цикл?
Пусть в связном графе \(n\) вершин и ровно один цикл.
Возьмём любое ребро этого цикла и удалим его. Связность сохранится: ребро, лежащее на цикле, мостом не является — между его концами остаётся путь по другой части цикла. Циклов после удаления не остаётся: единственный цикл графа разрушен, а других в графе не было.
Получился связный граф без циклов, то есть дерево с \(n\) вершинами; в нём \(n-1\) ребро. Вернём удалённое ребро — в исходном графе рёбер \(n - 1 + 1 = n\).
Ответ: в связном графе с \(n\) вершинами и единственным циклом ровно \(n\) рёбер — на одно больше, чем в дереве с тем же числом вершин.
