Страница 68 номер 90, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Докажите, что в дереве с \(n\) вершинами количество рёбер равно \((n-1)\).
Сначала докажем, что в дереве, у которого больше одной вершины, есть вершина степени 1.
Возьмём самую длинную цепь \(v_0 v_1 \ldots v_k\) (цепей конечное число, поэтому самая длинная есть; \(k \geqslant 1\)). Пусть из \(v_0\) выходит ещё одно ребро \(v_0 u\): если \(u\) на цепи не лежит, то цепь \(u\, v_0\, v_1 \ldots v_k\) длиннее выбранной, а если \(u = v_i\) при \(i \geqslant 2\), то \(v_0 v_1 \ldots v_i v_0\) — цикл, которого в дереве нет. Значит, степень вершины \(v_0\) равна 1.
У дерева с одной вершиной рёбер нет, и \(1 - 1 = 0\) — утверждение верно.
Пусть утверждение верно для деревьев с \(n-1\) вершиной, и дано дерево с \(n\) вершинами, \(n \geqslant 2\). Оторвём вершину \(v\) степени 1 вместе с её ребром. Оставшийся граф связен: цепь между любыми двумя оставшимися вершинами через \(v\) не проходит, ведь, придя в вершину степени 1, выйти можно только по тому же ребру, а в цепи рёбра не повторяются; циклов тоже не появилось. Значит, это дерево с \(n-1\) вершиной, и в нём \(n-2\) ребра.
Вернём \(v\) и её ребро: вершин \(n\), рёбер \(n - 2 + 1 = n - 1\), что и требовалось доказать.
Ответ: дерево с \(n\) вершинами содержит ровно \(n-1\) ребро: если отрывать от него по одной вершине степени 1, дерево сведётся к единственной вершине без рёбер, а при каждом отрывании и вершин, и рёбер становится на одну меньше.
Докажите, что в дереве с \(n\) вершинами количество рёбер равно \((n-1)\).
Сначала докажем, что в дереве, у которого больше одной вершины, обязательно есть вершина степени 1.
Возьмём в дереве самую длинную цепь \(v_0 v_1 \ldots v_k\) (цепей в дереве конечное число, поэтому самая длинная существует; \(k \geqslant 1\), так как дерево связно и вершин не меньше двух). Пусть из вершины \(v_0\) выходит ещё одно ребро, кроме \(v_0 v_1\), — ребро \(v_0 u\). Если вершина \(u\) на цепи не лежит, то цепь \(u\, v_0\, v_1 \ldots v_k\) длиннее выбранной, чего быть не может. Если же \(u\) — вершина самой цепи, то есть \(u = v_i\) при \(i \geqslant 2\), то \(v_0 v_1 \ldots v_i v_0\) — цикл, а в дереве циклов нет. Значит, из \(v_0\) выходит ровно одно ребро и степень вершины \(v_0\) равна 1.
Теперь докажем утверждение, разбирая деревья по числу вершин.
У дерева с одной вершиной рёбер нет, и \(1 - 1 = 0\) — утверждение верно.
Пусть оно верно для всех деревьев с \(n-1\) вершиной, и пусть дано дерево с \(n\) вершинами, где \(n \geqslant 2\). В нём есть вершина \(v\) степени 1; оторвём её вместе с единственным выходящим из неё ребром.
Оставшийся граф связен: цепь между любыми двумя оставшимися вершинами через \(v\) не проходит, потому что, придя в вершину степени 1, выйти из неё можно только по тому же ребру, а в цепи рёбра не повторяются. Циклов при удалении вершины тоже не появляется. Значит, это дерево с \(n-1\) вершиной, и по предположению в нём \(n-2\) ребра.
Вернём вершину \(v\) и её ребро: вершин станет \(n\), а рёбер \(n - 2 + 1 = n - 1\), что и требовалось доказать.
Ответ: дерево с \(n\) вершинами содержит ровно \(n-1\) ребро: если отрывать от него по одной вершине степени 1, дерево сведётся к единственной вершине без рёбер, а при каждом отрывании и вершин, и рёбер становится на одну меньше.
