Страница 67 номер 82, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Сколько рёбер нужно удалить из графа, изображённого на рисунке 57, чтобы получилось дерево? Удалите их и перерисуйте полученное дерево в тетрадь.
Дерево с \(n\) вершинами содержит \(n-1\) ребро, а вершины при удалении рёбер не исчезают: рёбер должно остаться на одно меньше, чем вершин.
а) Шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) по кругу, рёбра \(AB\), \(BC\), \(CD\), \(DE\), \(EF\), \(FA\) — один цикл. Дереву нужно \(6 - 1 = 5\) рёбер, удалить надо \(6 - 5 = 1\) ребро: удалим \(FA\) — оно лежит на цикле, поэтому связность сохранится, а других циклов нет. Останется цепь \(A\)—\(B\)—\(C\)—\(D\)—\(E\)—\(F\).
б) Пять вершин \(A\), \(B\), \(C\), \(D\), \(E\) и все 10 рёбер \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\). Дереву нужно \(5 - 1 = 4\) ребра, удалить надо \(10 - 4 = 6\) рёбер: оставим четыре ребра, выходящие из \(A\), а \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\) удалим — граф связен и циклов не содержит.
в) Восемь вершин: центральная \(O\) и семь внешних \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\); рёбра \(OA\), \(OB\), \(OC\), \(OD\), \(OE\), \(OF\), \(OG\) и \(AB\), \(CD\), \(EF\) — всего \(7 + 3 = 10\). Дереву нужно \(8 - 1 = 7\) рёбер, удалить надо \(10 - 7 = 3\) ребра: рёбра \(AB\), \(CD\), \(EF\) замыкают треугольники \(OAB\), \(OCD\), \(OEF\) — удалим все три. Останутся семь рёбер из \(O\): граф связен и циклов не имеет.
Ответ: а) 1 ребро — остаётся цепь из шести вершин; б) 6 рёбер — остаются четыре ребра, выходящие из одной вершины; в) 3 ребра — по стороне каждого из трёх треугольников, остаются семь рёбер, выходящих из центральной вершины.
Сколько рёбер нужно удалить из графа, изображённого на рисунке 57, чтобы получилось дерево? Удалите их и перерисуйте полученное дерево в тетрадь.
Вершины в задании не подписаны, поэтому обозначим их сами. Дерево с \(n\) вершинами содержит \(n-1\) ребро, а вершины при удалении рёбер никуда не деваются — значит, в каждом пункте нужно удалить столько рёбер, чтобы их осталось ровно на одно меньше, чем вершин.
а) Шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) расположены по кругу, и соединены соседние: рёбра \(AB\), \(BC\), \(CD\), \(DE\), \(EF\), \(FA\) — всего 6, они образуют один цикл. Дереву с шестью вершинами нужно \(6 - 1 = 5\) рёбер, значит, удалить надо \(6 - 5 = 1\) ребро. Удалим ребро \(FA\): оно лежит на цикле, поэтому связность сохранится, а других циклов в графе нет. Останется цепь \(A\)—\(B\)—\(C\)—\(D\)—\(E\)—\(F\) — это дерево.
б) Пять вершин \(A\), \(B\), \(C\), \(D\), \(E\) соединены всеми возможными рёбрами: \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\) — всего 10. Дереву с пятью вершинами нужно \(5 - 1 = 4\) ребра, значит, удалить надо \(10 - 4 = 6\) рёбер. Оставим четыре ребра, выходящие из вершины \(A\), а рёбра \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\) удалим. Оставшийся граф связен (из каждой вершины ведёт ребро в \(A\)) и циклов не содержит.
в) Здесь 8 вершин: центральная \(O\) и семь вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\) вокруг неё. Центральная вершина соединена с каждой из семи внешних — это рёбра \(OA\), \(OB\), \(OC\), \(OD\), \(OE\), \(OF\), \(OG\); кроме того, соединены три пары соседних внешних вершин: \(AB\), \(CD\), \(EF\). Всего \(7 + 3 = 10\) рёбер, а вершина \(G\) висячая. Дереву с восемью вершинами нужно \(8 - 1 = 7\) рёбер, значит, удалить надо \(10 - 7 = 3\) ребра. Каждое из рёбер \(AB\), \(CD\), \(EF\) замыкает свой треугольник (\(OAB\), \(OCD\), \(OEF\)) — удалим все три. Останутся семь рёбер, выходящих из \(O\): граф связен и циклов не имеет.
Ответ: а) 1 ребро — остаётся цепь из шести вершин; б) 6 рёбер — остаются четыре ребра, выходящие из одной вершины; в) 3 ребра — по стороне каждого из трёх треугольников, остаются семь рёбер, выходящих из центральной вершины.
