Страница 58 номер 90, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Может ли у графа существовать ровно два неизоморфных остовных дерева? Если да, приведите пример.
Да, может.
Граф на вершинах \(A\), \(B\), \(C\), \(D\) с рёбрами \(AB\), \(BC\), \(CA\), \(AD\) — треугольник \(ABC\) с подвешенным к вершине \(A\) ребром \(AD\).
\(v = 4\), \(e = 4\), цикломатическое число \(4 - 4 + 1 = 1\): удалить нужно ровно одно ребро, размыкающее цикл. Единственный цикл — треугольник \(ABCA\), поэтому удалить можно только \(AB\), \(BC\) или \(CA\): при удалении \(AD\) вершина \(D\) стала бы изолированной и граф перестал бы быть связным. Значит, остовных деревьев ровно три:
1) удалено \(BC\) — остаются рёбра \(AB\), \(AC\), \(AD\); степени вершин: \(A\) — 3, \(B\) — 1, \(C\) — 1, \(D\) — 1;
2) удалено \(AB\) — остаются рёбра \(BC\), \(CA\), \(AD\), то есть цепь \(BCAD\); степени: \(B\) — 1, \(C\) — 2, \(A\) — 2, \(D\) — 1;
3) удалено \(CA\) — остаются рёбра \(AB\), \(BC\), \(AD\), то есть цепь \(DABC\); степени: \(D\) — 1, \(A\) — 2, \(B\) — 2, \(C\) — 1.
Деревья 2) и 3) изоморфны: соответствие \(B \leftrightarrow D\), \(C \leftrightarrow A\), \(A \leftrightarrow B\), \(D \leftrightarrow C\) переводит рёбра \(BC\), \(CA\), \(AD\) второго дерева в рёбра \(DA\), \(AB\), \(BC\) третьего.
Дерево 1) им не изоморфно: при изоморфизме степени соответствующих вершин равны, а в дереве 1) есть вершина степени 3, тогда как в цепи наибольшая степень вершины равна 2.
Неизоморфных остовных деревьев ровно два: звезда с центром \(A\) и цепь из четырёх вершин.
Ответ: да, может; у графа с вершинами \(A\), \(B\), \(C\), \(D\) и рёбрами \(AB\), \(BC\), \(CA\), \(AD\) ровно два неизоморфных остовных дерева — звезда с центром \(A\) (рёбра \(AB\), \(AC\), \(AD\)) и цепь из четырёх вершин (например, рёбра \(AD\), \(AB\), \(BC\)).
Может ли у графа существовать ровно два неизоморфных остовных дерева? Если да, приведите пример.
Да, может.
Возьмём граф на четырёх вершинах \(A\), \(B\), \(C\), \(D\) с рёбрами \(AB\), \(BC\), \(CA\) и \(AD\): это треугольник \(ABC\), к вершине \(A\) которого подвешено ребро \(AD\).
В этом графе \(v = 4\) вершины и \(e = 4\) ребра, поэтому его цикломатическое число равно \(4 - 4 + 1 = 1\): чтобы получить остовное дерево, нужно удалить ровно одно ребро, и оно должно размыкать цикл. Единственный цикл графа — треугольник \(ABCA\), поэтому удалить можно только одно из рёбер \(AB\), \(BC\), \(CA\) (при удалении ребра \(AD\) вершина \(D\) стала бы изолированной и граф перестал бы быть связным). Значит, остовных деревьев ровно три:
1) удалено \(BC\) — остаются рёбра \(AB\), \(AC\), \(AD\); степени вершин: \(A\) — 3, \(B\) — 1, \(C\) — 1, \(D\) — 1;
2) удалено \(AB\) — остаются рёбра \(BC\), \(CA\), \(AD\), то есть цепь \(BCAD\); степени: \(B\) — 1, \(C\) — 2, \(A\) — 2, \(D\) — 1;
3) удалено \(CA\) — остаются рёбра \(AB\), \(BC\), \(AD\), то есть цепь \(DABC\); степени: \(D\) — 1, \(A\) — 2, \(B\) — 2, \(C\) — 1.
Деревья 2) и 3) изоморфны: соответствие \(B \leftrightarrow D\), \(C \leftrightarrow A\), \(A \leftrightarrow B\), \(D \leftrightarrow C\) переводит рёбра \(BC\), \(CA\), \(AD\) второго дерева в рёбра \(DA\), \(AB\), \(BC\) третьего.
Дерево 1) не изоморфно им: в нём есть вершина степени 3, а в цепи наибольшая степень вершины равна 2. При изоморфизме каждому ребру, примыкающему к вершине, отвечает ребро, примыкающее к соответствующей вершине, поэтому степени соответствующих вершин равны, и вершине степени 3 в цепи взяться неоткуда.
Значит, неизоморфных остовных деревьев ровно два: звезда с центром \(A\) и цепь из четырёх вершин.
Ответ: да, может; у графа с вершинами \(A\), \(B\), \(C\), \(D\) и рёбрами \(AB\), \(BC\), \(CA\), \(AD\) ровно два неизоморфных остовных дерева — звезда с центром \(A\) (рёбра \(AB\), \(AC\), \(AD\)) и цепь из четырёх вершин (например, рёбра \(AD\), \(AB\), \(BC\)).
