Страница 15 номер 28, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Постройте граф, у которого ровно 3 различных остовных дерева.
Например, подходит граф-треугольник: вершины \(A\), \(B\), \(C\) и рёбра \(AB\), \(BC\), \(CA\).
Граф связный, в нём 3 вершины и 3 ребра. В любом его остовном дереве 3 вершины, значит, \(3 - 1 = 2\) ребра: удалить нужно ровно одно ребро. После удаления любого из трёх рёбер остаются два ребра с общей вершиной — цепь через все три вершины, то есть связный граф без циклов. Других способов удалить одно ребро нет, поэтому остовных деревьев ровно 3: с рёбрами \(BC\) и \(CA\), с рёбрами \(AB\) и \(CA\), с рёбрами \(AB\) и \(BC\). Все три различны: у них разные наборы рёбер.
Постройте граф, у которого ровно 3 различных остовных дерева.
Например, подходит граф-треугольник: вершины \(A\), \(B\), \(C\) и рёбра \(AB\), \(BC\), \(CA\). Его остовные деревья получаются удалением одного из трёх рёбер.
Граф связный, в нём 3 вершины и 3 ребра. В любом его остовном дереве 3 вершины, значит, \(3 - 1 = 2\) ребра: удалить нужно ровно одно ребро. После удаления любого из трёх рёбер остаются два ребра с общей вершиной — цепь через все три вершины, то есть связный граф без циклов. Других способов удалить одно ребро нет, поэтому остовных деревьев ровно 3: с рёбрами \(BC\) и \(CA\), с рёбрами \(AB\) и \(CA\), с рёбрами \(AB\) и \(BC\). Все три различны: у них разные наборы рёбер.
