Страница 67 номер 83, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Сколько рёбер нужно добавить к графу, изображённому на рисунке 58, чтобы получилось дерево? Добавьте их и перерисуйте полученное дерево в тетрадь.
Ребро внутри одного куска даёт цикл: его концы уже соединены цепью. Ребро между разными кусками уменьшает число кусков на один и цикла не создаёт, поэтому, если в самих кусках циклов нет, для сборки дерева из \(k\) кусков нужно ровно \(k-1\) ребро.
а) Восемь вершин соединены попарно четырьмя отдельными рёбрами \(AB\), \(CD\), \(EF\), \(GH\): кусков 4, добавить надо \(4 - 1 = 3\) ребра. Проведём \(BC\), \(DE\), \(FG\) — цепь \(A\)—\(B\)—\(C\)—\(D\)—\(E\)—\(F\)—\(G\)—\(H\): 8 вершин и \(4 + 3 = 7\) рёбер, циклов нет.
б) Восемь вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\), \(H\) без единого ребра: кусков 8, добавить надо \(8 - 1 = 7\) рёбер. Проведём \(AB\), \(BC\), \(CD\), \(DE\), \(EF\), \(FG\), \(GH\) — снова цепь из восьми вершин с 7 рёбрами.
в) Три куска по 6 вершин и 5 рёбер, каждый уже дерево: всего \(3 \cdot 6 = 18\) вершин и \(3 \cdot 5 = 15\) рёбер. Кусков 3, добавить надо \(3 - 1 = 2\) ребра: возьмём по одной вершине в каждом куске — \(A\), \(B\), \(C\) — и проведём \(AB\) и \(BC\). Выйдет связный граф без циклов с 18 вершинами и \(15 + 2 = 17\) рёбрами, а \(18 - 1 = 17\) — это дерево.
Ответ: а) 3 ребра — четыре отдельных ребра связываются в цепь из восьми вершин; б) 7 рёбер — восемь отдельных вершин связываются в цепь; в) 2 ребра — три дерева связываются в одно дерево с 18 вершинами.
Сколько рёбер нужно добавить к графу, изображённому на рисунке 58, чтобы получилось дерево? Добавьте их и перерисуйте полученное дерево в тетрадь.
Вершины в задании не подписаны, поэтому обозначим их сами.
Ребро, соединяющее две вершины одного куска, дерева не даст: эти вершины уже соединены цепью, и вместе с новым ребром получится цикл. Ребро же, соединяющее вершины разных кусков, уменьшает число кусков ровно на один и цикла не создаёт. Значит, если в самих кусках циклов нет, то для сборки дерева из \(k\) кусков нужно добавить ровно \(k-1\) ребро.
а) Восемь вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\), \(H\) соединены попарно четырьмя отдельными рёбрами: \(AB\), \(CD\), \(EF\), \(GH\). Кусков 4, значит, добавить надо \(4 - 1 = 3\) ребра. Проведём \(BC\), \(DE\), \(FG\) — получится цепь \(A\)—\(B\)—\(C\)—\(D\)—\(E\)—\(F\)—\(G\)—\(H\): 8 вершин и \(4 + 3 = 7\) рёбер, циклов нет.
б) Восемь вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\), \(H\), ни одного ребра: каждая вершина — отдельный кусок, кусков 8, добавить надо \(8 - 1 = 7\) рёбер. Проведём \(AB\), \(BC\), \(CD\), \(DE\), \(EF\), \(FG\), \(GH\) — снова цепь из восьми вершин, в ней 7 рёбер.
в) Три отдельных куска, в каждом 6 вершин и 5 рёбер, и ни в одном нет цикла — то есть каждый кусок уже дерево. Всего \(3 \cdot 6 = 18\) вершин и \(3 \cdot 5 = 15\) рёбер. Кусков 3, добавить надо \(3 - 1 = 2\) ребра. Возьмём по одной вершине в каждом куске — \(A\) в первом, \(B\) во втором, \(C\) в третьем — и проведём рёбра \(AB\) и \(BC\). Получится связный граф с 18 вершинами и \(15 + 2 = 17\) рёбрами, циклов в нём нет, и \(18 - 1 = 17\) — это дерево.
Ответ: а) 3 ребра — четыре отдельных ребра связываются в цепь из восьми вершин; б) 7 рёбер — восемь отдельных вершин связываются в цепь; в) 2 ребра — три дерева связываются в одно дерево с 18 вершинами.
