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