Вопросы после параграфа §58 на странице 14, ГДЗ по алгебре за 7 класс к учебнику Высоцкого часть 2
Например, граф-треугольник с вершинами \(A\), \(B\), \(C\) и рёбрами \(AB\), \(BC\), \(CA\) связный, и в нём есть цикл \(ABCA\). Разомкнуть его можно, удалив любое из трёх рёбер: граф останется связным, а циклов в нём не будет. Без ребра \(AB\) получим остовное дерево с рёбрами \(BC\) и \(CA\), без ребра \(BC\) — с рёбрами \(AB\) и \(CA\): это разные остовные деревья, у них разные наборы рёбер.
Ответ: да, может.
Остовное дерево получается из графа удалением рёбер, все вершины графа в нём остаются, а дерево — связный граф. В несвязном графе есть две вершины, которые не соединены путём. При удалении рёбер новые пути не появляются, поэтому и после удаления любых рёбер эти две вершины не будут соединены путём: получившийся граф несвязный и деревом не является.
Ответ: нет, не существует.
Дерево — связный граф без циклов, размыкать в нём нечего: само дерево и есть своё остовное дерево. Удалять не нужно ни одного ребра, да и нельзя: если из дерева удалить ребро, то граф перестанет быть связным.
Ответ: цикломатическое число дерева равно 0.
Да. Например, граф-треугольник с вершинами \(A\), \(B\), \(C\) и рёбрами \(AB\), \(BC\), \(CA\) связный, и в нём есть цикл \(ABCA\). Разомкнуть его можно, удалив любое из трёх рёбер: граф останется связным, а циклов в нём не будет. Удалив ребро \(AB\), получим остовное дерево с рёбрами \(BC\) и \(CA\), а удалив ребро \(BC\) — остовное дерево с рёбрами \(AB\) и \(CA\). Это разные остовные деревья: у них разные наборы рёбер.
Ответ: да, может.
Нет. Остовное дерево получается из графа удалением рёбер, все вершины графа в нём остаются, а дерево — связный граф. В несвязном графе есть две вершины, которые не соединены путём. При удалении рёбер новые пути не появляются, поэтому и после удаления любых рёбер эти две вершины не будут соединены путём: получившийся граф несвязный и деревом не является.
Ответ: нет, не существует.
Дерево — связный граф без циклов, размыкать в нём нечего: само дерево и есть своё остовное дерево. Удалять не нужно ни одного ребра, да и нельзя: если из дерева удалить ребро, то граф перестанет быть связным. Значит, цикломатическое число дерева равно 0.
Ответ: цикломатическое число дерева равно 0.
