Вопросы после параграфа §12 на странице 58, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни

Остовное дерево связного графа \(G\) — это подграф графа \(G\), который содержит все вершины графа \(G\) и является деревом, то есть связен и не имеет циклов.

Получают остовное дерево удалением части рёбер: рёбра удаляют так, чтобы каждый раз размыкался какой-нибудь цикл, — тогда граф остаётся связным, а все вершины сохраняются.

Например, у треугольника \(ABC\) остовным деревом будет цепь с рёбрами \(AB\) и \(BC\): в ней те же три вершины, она связна и циклов не имеет.

Ответ: остовное дерево связного графа — это его подграф, который содержит все вершины графа и является деревом.

Конечного такого дерева не существует. Пусть в конечном дереве \(v\) вершин. Тогда рёбер в нём \(v - 1\), а сумма степеней всех вершин равна удвоенному числу рёбер, то есть \(2(v - 1) = 2v - 2\). Если бы каждая из \(v\) вершин имела степень 2, сумма степеней равнялась бы \(2v\). Но \(2v \ne 2v - 2\) ни при каком \(v\), значит, такого конечного дерева нет.

Бесконечное дерево с таким свойством существует. Занумеруем вершины всеми целыми числами: \(\ldots,\ V_{-2},\ V_{-1},\ V_0,\ V_1,\ V_2,\ \ldots\) ; ребро соединяет две вершины, номера которых отличаются на 1.

Этот граф связен: от вершины \(V_k\) до вершины \(V_m\) ведёт цепь по всем промежуточным номерам. Циклов в нём нет. Действительно, в цикле конечное число вершин, поэтому среди них есть вершина \(V_m\) с наибольшим номером; в цикле к каждой вершине примыкают два ребра, а у вершины \(V_m\) есть только два ребра — \(V_{m-1}V_m\) и \(V_mV_{m+1}\), и второе из них ведёт в вершину с бо́льшим номером, которой в цикле нет. Значит, в цикле к \(V_m\) примыкает не больше одного ребра — противоречие.

Следовательно, это дерево, и к каждой вершине \(V_n\) примыкают ровно два ребра — \(V_{n-1}V_n\) и \(V_nV_{n+1}\), то есть степень каждой вершины равна 2.

Ответ: конечного дерева, у которого все вершины имеют степень 2, не существует; бесконечное существует — это двусторонне бесконечная цепь.

Цикломатическим числом связного графа называется число рёбер, которые нужно удалить из него, чтобы получить остовное дерево.

Если в связном графе \(v\) вершин и \(e\) рёбер, то в его остовном дереве те же \(v\) вершин и \(v - 1\) рёбер, поэтому удалить нужно \(e - (v - 1) = e - v + 1\) рёбер.

Например, у треугольника \(v = 3\) и \(e = 3\), поэтому его цикломатическое число равно \(3 - 3 + 1 = 1\): чтобы получить остовное дерево, достаточно удалить одно ребро.

Ответ: цикломатическое число связного графа — это число рёбер, которые нужно удалить, чтобы получить остовное дерево; у связного графа с \(v\) вершинами и \(e\) рёбрами оно равно \(e - v + 1\).

Да, может.

Возьмём два графа на одних и тех же трёх вершинах \(A\), \(B\), \(C\). Первый — цепь с рёбрами \(AB\) и \(BC\). Второй — треугольник с рёбрами \(AB\), \(BC\) и \(CA\).

Первый граф связен и циклов не имеет, значит, он сам является деревом и сам себе остовным деревом. У второго графа есть цикл \(ABCA\); удалив ребро \(CA\), мы размыкаем этот цикл и получаем связный подграф на всех трёх вершинах с рёбрами \(AB\) и \(BC\) — то же самое дерево.

Эти два графа не изоморфны: у первого 2 ребра, а у второго 3, тогда как у изоморфных графов рёбер поровну.

Ответ: да, может; цепь с рёбрами \(AB\) и \(BC\) является остовным деревом и для самой этой цепи, и для треугольника \(ABC\), а эти два графа не изоморфны.

В графе \(v = 6\) вершин и \(e = 7\) рёбер, поэтому его цикломатическое число равно \[e - v + 1 = 7 - 6 + 1 = 2.\]

Ответ: цикломатическое число этого графа равно 2.