Вопросы к пункту 2 «Деревья» на странице 60, ГДЗ по алгебре за 10 класс к учебнику Бунимовича вероятность и статистика
Вопросы к пункту 2 «Деревья».
Дерево — связный граф без циклов; удаление любого его ребра разрывает граф на две части.
Ответ: дерево — это связный граф, в котором нет ни одного цикла.
В дереве каждое ребро — мост: не будь ребро \(xy\) мостом, после его удаления \(x\) и \(y\) остались бы соединены цепью, а вместе с самим ребром цепь дала бы цикл.
Между любыми двумя вершинами дерева существует единственная цепь: хотя бы одна есть по связности, а будь их две, они образовали бы цикл.
Дерево с \(n\) вершинами содержит ровно \(n-1\) ребро.
Ответ: в дереве каждое ребро — мост; между любыми двумя вершинами дерева есть ровно одна цепь; дерево с \(n\) вершинами имеет \(n-1\) ребро.
Рёбер на единицу меньше числа вершин: \(2024 - 1 = 2023\).
Ответ: 2023 ребра.
Вершин на единицу больше числа рёбер: \(1000 + 1 = 1001\).
Ответ: 1001 вершина.
Вопросы к пункту 2 «Деревья».
Деревом называется связный граф без циклов. У дерева нет «лишних» рёбер: удаление любого из них разрывает граф на две части.
Ответ: дерево — это связный граф, в котором нет ни одного цикла.
Первое свойство: в дереве каждое ребро является мостом. Если бы какое-то ребро \(xy\) мостом не было, то после его удаления вершины \(x\) и \(y\) остались бы соединёнными цепью, а вместе с самим ребром \(xy\) эта цепь дала бы цикл, которого в дереве нет.
Второе свойство: между любыми двумя вершинами дерева существует единственная цепь. Хотя бы одна цепь есть, потому что дерево связно; будь их две, они вместе образовали бы цикл.
Третье свойство: дерево с \(n\) вершинами содержит ровно \(n-1\) ребро.
Ответ: в дереве каждое ребро — мост; между любыми двумя вершинами дерева есть ровно одна цепь; дерево с \(n\) вершинами имеет \(n-1\) ребро.
Число рёбер дерева на единицу меньше числа его вершин: \(2024 - 1 = 2023\).
Ответ: 2023 ребра.
Число вершин дерева на единицу больше числа рёбер: \(1000 + 1 = 1001\).
Ответ: 1001 вершина.
