Страница 67 номер 84, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Если дерево с заданными степенями вершин существует — постройте его, если нет — объясните, почему такого дерева не существует: а) 1, 1, 2, 2, 2; б) 2, 2, 2, 3; в) 1, 1, 1, 1, 1; г) 1, 1, 1, 1, 1, 1, 2, 4.
Дерево с \(n\) вершинами содержит \(n-1\) ребро, а сумма степеней равна удвоенному числу рёбер, то есть \(2(n-1)\); этим и проверяются наборы.
а) Вершин 5, сумма степеней \(1 + 1 + 2 + 2 + 2 = 8\), а у дерева с пятью вершинами она равна \(2 \cdot (5 - 1) = 8\) — совпадает. Дерево есть: цепь \(A\)—\(B\)—\(C\)—\(D\)—\(E\) со степенями вершин \(A\) — 1, \(B\) — 2, \(C\) — 2, \(D\) — 2, \(E\) — 1.
б) Сумма степеней \(2 + 2 + 2 + 3 = 9\) — нечётная, а сумма степеней любого графа чётна: графа с такими степенями нет вовсе, тем более дерева.
в) Сумма степеней \(1 \cdot 5 = 5\) — снова нечётная, такого графа нет.
г) Сумма степеней \(6 \cdot 1 + 2 + 4 = 12\) — чётная, чётность ничего не запрещает. Но вершин 8, а дерево с восемью вершинами обязано иметь \(8 - 1 = 7\) рёбер, то есть сумму степеней \(2 \cdot 7 = 14\), а не 12. Дерева с такими степенями не существует.
Ответ: а) дерево существует — это цепь из пяти вершин со степенями 1, 2, 2, 2, 1; б) не существует, так как сумма степеней 9 нечётна; в) не существует, так как сумма степеней 5 нечётна; г) не существует, так как у дерева с восемью вершинами сумма степеней равна 14, а не 12.
Если дерево с заданными степенями вершин существует — постройте его, если нет — объясните, почему такого дерева не существует: а) 1, 1, 2, 2, 2; б) 2, 2, 2, 3; в) 1, 1, 1, 1, 1; г) 1, 1, 1, 1, 1, 1, 2, 4.
Дерево с \(n\) вершинами содержит \(n-1\) ребро, а сумма степеней всех вершин любого графа равна удвоенному числу рёбер. Значит, у дерева с \(n\) вершинами сумма степеней равна \(2(n-1)\) — этим и проверяются наборы.
а) Степени \(1, 1, 2, 2, 2\). Вершин 5, сумма степеней \(1 + 1 + 2 + 2 + 2 = 8\), а у дерева с пятью вершинами она должна равняться \(2 \cdot (5 - 1) = 8\) — совпадает. Такое дерево есть: цепь \(A\)—\(B\)—\(C\)—\(D\)—\(E\). В ней степени вершин такие: \(A\) — 1, \(B\) — 2, \(C\) — 2, \(D\) — 2, \(E\) — 1; граф связен, циклов не имеет, рёбер 4.
б) Степени \(2, 2, 2, 3\). Их сумма \(2 + 2 + 2 + 3 = 9\) — число нечётное, а сумма степеней любого графа чётна, ведь она равна удвоенному числу рёбер. Графа с такими степенями не существует вовсе, тем более дерева.
в) Степени \(1, 1, 1, 1, 1\). Их сумма \(1 \cdot 5 = 5\) — снова нечётное число, поэтому и такого графа нет.
г) Степени \(1, 1, 1, 1, 1, 1, 2, 4\). Их сумма \(6 \cdot 1 + 2 + 4 = 12\) — число чётное, поэтому чётность здесь ничего не запрещает. Но вершин 8, а дерево с восемью вершинами обязано иметь \(8 - 1 = 7\) рёбер, то есть сумму степеней \(2 \cdot 7 = 14\), у нас же она равна 12. Дерева с такими степенями не существует.
Ответ: а) дерево существует — это цепь из пяти вершин со степенями 1, 2, 2, 2, 1; б) не существует, так как сумма степеней 9 нечётна; в) не существует, так как сумма степеней 5 нечётна; г) не существует, так как у дерева с восемью вершинами сумма степеней равна 14, а не 12.
