Страница 59 номер 99, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Постройте два неизоморфных остовных дерева графа, изображённого на рисунке 55.
Вершины на рисунке не подписаны, поэтому обозначим их сами: \(A\) — верхняя вершина; \(B\) и \(C\) — левая и правая во втором ряду; \(D\) и \(E\) — левая и правая в третьем ряду; \(F\) и \(G\) — в четвёртом ряду; \(H\) и \(K\) — нижние.
В графе 9 вершин и 15 рёбер: \(AB\), \(AC\), \(BC\), \(BD\), \(CD\), \(CE\), \(DE\), \(AE\), \(DH\), \(EG\), \(FG\), \(FH\), \(FK\), \(GK\), \(HK\). В любом остовном дереве этого графа 9 вершин и 8 рёбер.
Дерево \(T_1\) — рёбра \(AB\), \(BC\), \(BD\), \(CE\), \(DH\), \(EG\), \(FG\), \(GK\). Подграф связен: от вершины \(B\) рёбра ведут в \(A\), \(C\) и \(D\), от \(C\) — в \(E\), от \(E\) — в \(G\), от \(G\) — в \(F\) и \(K\), от \(D\) — в \(H\). В нём 9 вершин и 8 рёбер, цикломатическое число \(8 - 9 + 1 = 0\), значит, он сам является деревом. Степени его вершин: \(B\) — 3, \(G\) — 3, \(C\) — 2, \(D\) — 2, \(E\) — 2, \(A\) — 1, \(F\) — 1, \(H\) — 1, \(K\) — 1.
Дерево \(T_2\) — рёбра \(AC\), \(BC\), \(CD\), \(CE\), \(DH\), \(EG\), \(FH\), \(HK\). Подграф связен: от вершины \(C\) рёбра ведут в \(A\), \(B\), \(D\) и \(E\), от \(D\) — в \(H\), от \(H\) — в \(F\) и \(K\), от \(E\) — в \(G\). В нём снова 9 вершин и 8 рёбер, цикломатическое число \(8 - 9 + 1 = 0\), значит, это тоже дерево. Степени его вершин: \(C\) — 4, \(H\) — 3, \(D\) — 2, \(E\) — 2, \(A\) — 1, \(B\) — 1, \(F\) — 1, \(G\) — 1, \(K\) — 1.
Деревья \(T_1\) и \(T_2\) не изоморфны: при изоморфизме степени соответствующих вершин равны, а в \(T_2\) есть вершина степени 4, тогда как в \(T_1\) наибольшая степень вершины равна 3.
Ответ: годятся остовные деревья с рёбрами \(AB\), \(BC\), \(BD\), \(CE\), \(DH\), \(EG\), \(FG\), \(GK\) и с рёбрами \(AC\), \(BC\), \(CD\), \(CE\), \(DH\), \(EG\), \(FH\), \(HK\); они не изоморфны, потому что во втором есть вершина степени 4, а в первом наибольшая степень вершины равна 3.
Постройте два неизоморфных остовных дерева графа, изображённого на рисунке 55.
Вершины на рисунке не подписаны, поэтому обозначим их сами: \(A\) — верхняя вершина; \(B\) и \(C\) — левая и правая во втором ряду; \(D\) и \(E\) — левая и правая в третьем ряду; \(F\) и \(G\) — в четвёртом ряду; \(H\) и \(K\) — нижние.
В графе 9 вершин и 15 рёбер: \(AB\), \(AC\), \(BC\), \(BD\), \(CD\), \(CE\), \(DE\), \(AE\), \(DH\), \(EG\), \(FG\), \(FH\), \(FK\), \(GK\), \(HK\). В любом остовном дереве этого графа столько же вершин, сколько в самом графе, то есть 9, и на одно ребро меньше, то есть 8.
Первое дерево \(T_1\) составим из рёбер \(AB\), \(BC\), \(BD\), \(CE\), \(DH\), \(EG\), \(FG\), \(GK\) — все они есть в графе. Этот подграф связен: от вершины \(B\) рёбра ведут в \(A\), \(C\) и \(D\), от \(C\) — в \(E\), от \(E\) — в \(G\), от \(G\) — в \(F\) и \(K\), от \(D\) — в \(H\), так что достижима каждая из девяти вершин. В подграфе 9 вершин и 8 рёбер, поэтому его цикломатическое число равно \(8 - 9 + 1 = 0\): удалять из него нечего, значит, он сам является деревом. Следовательно, \(T_1\) — остовное дерево графа. Степени его вершин: \(B\) — 3, \(G\) — 3, \(C\) — 2, \(D\) — 2, \(E\) — 2, \(A\) — 1, \(F\) — 1, \(H\) — 1, \(K\) — 1.
Второе дерево \(T_2\) составим из рёбер \(AC\), \(BC\), \(CD\), \(CE\), \(DH\), \(EG\), \(FH\), \(HK\) — они тоже все есть в графе. Подграф связен: от вершины \(C\) рёбра ведут в \(A\), \(B\), \(D\) и \(E\), от \(D\) — в \(H\), от \(H\) — в \(F\) и \(K\), от \(E\) — в \(G\). В нём снова 9 вершин и 8 рёбер, цикломатическое число равно \(8 - 9 + 1 = 0\), значит, это дерево, то есть \(T_2\) — тоже остовное дерево графа. Степени его вершин: \(C\) — 4, \(H\) — 3, \(D\) — 2, \(E\) — 2, \(A\) — 1, \(B\) — 1, \(F\) — 1, \(G\) — 1, \(K\) — 1.
Деревья \(T_1\) и \(T_2\) не изоморфны. При изоморфизме каждому ребру, примыкающему к вершине, отвечает ребро, примыкающее к соответствующей вершине, поэтому степени соответствующих вершин равны. В дереве \(T_2\) есть вершина степени 4, а в дереве \(T_1\) наибольшая степень вершины равна 3, и вершине степени 4 отвечать в нём нечему.
Ответ: годятся остовные деревья с рёбрами \(AB\), \(BC\), \(BD\), \(CE\), \(DH\), \(EG\), \(FG\), \(GK\) и с рёбрами \(AC\), \(BC\), \(CD\), \(CE\), \(DH\), \(EG\), \(FH\), \(HK\); они не изоморфны, потому что во втором есть вершина степени 4, а в первом наибольшая степень вершины равна 3.
