Страница 59 номер 98, ГДЗ по математике за 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\). Граф связен: по рёбрам \(AB\), \(AC\), \(BD\), \(CE\), \(DH\), \(EG\), \(FH\), \(HK\) от вершины \(A\) можно дойти до любой другой вершины, поэтому остовное дерево у него есть.
а) Остовное дерево содержит все вершины графа — 9 вершин.
б) В конечном дереве вершин на одну больше, чем рёбер, значит, рёбер в нём \(9 - 1 = 8\).
в) \(v = 9\), \(e = 15\), поэтому \[e - v + 1 = 15 - 9 + 1 = 7.\]
Ответ: а) 9 вершин; б) 8 рёбер; в) цикломатическое число графа равно 7.
Рассмотрите граф на рисунке 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\). Граф связен: по рёбрам \(AB\), \(AC\), \(BD\), \(CE\), \(DH\), \(EG\), \(FH\), \(HK\) от вершины \(A\) можно дойти до любой другой вершины, поэтому остовное дерево у него есть.
а) Остовное дерево графа содержит все его вершины, поэтому вершин в нём столько же, сколько в графе, — 9.
б) Остовное дерево — это дерево, а в конечном дереве вершин на одну больше, чем рёбер. Значит, рёбер в нём \(9 - 1 = 8\).
в) В графе \(v = 9\) вершин и \(e = 15\) рёбер, поэтому его цикломатическое число равно \[e - v + 1 = 15 - 9 + 1 = 7.\]
Ответ: а) 9 вершин; б) 8 рёбер; в) цикломатическое число графа равно 7.
