Страница 15 номер 27, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Найдите цикломатическое число графа, изображённого на рисунке 25. Нарисуйте какие-нибудь два остовных дерева этого графа.
Оба графа связные. В остовном дереве все вершины графа, а в конечном дереве вершин на одну больше, чем рёбер.
а) В графе 8 вершин и 10 рёбер. В любом его остовном дереве 8 вершин, значит, \(8 - 1 = 7\) рёбер. Удалить нужно \(10 - 7 = 3\) ребра. Цикломатическое число равно 3.
Например, остовные деревья получаются, если удалить рёбра \(de\), \(be\), \(gh\) или рёбра \(ab\), \(eg\), \(ch\).
В каждом из двух деревьев 8 вершин и 7 рёбер, любые две вершины соединены цепью, циклов нет.
б) В графе 6 вершин и 9 рёбер. В любом его остовном дереве 6 вершин, значит, \(6 - 1 = 5\) рёбер. Удалить нужно \(9 - 5 = 4\) ребра. Цикломатическое число равно 4.
Например, остовные деревья получаются, если удалить рёбра \(bc\), \(ce\), \(de\), \(ef\) или рёбра \(ac\), \(bc\), \(be\), \(ef\).
В каждом из двух деревьев 6 вершин и 5 рёбер, любые две вершины соединены цепью, циклов нет.
Ответ: а) 3; б) 4.
Найдите цикломатическое число графа, изображённого на рисунке 25. Нарисуйте какие-нибудь два остовных дерева этого графа.
Оба графа связные. В остовном дереве все вершины графа, а рёбер на одно меньше, чем вершин: в конечном дереве вершин на одну больше, чем рёбер.
а) В графе 8 вершин и 10 рёбер. В любом его остовном дереве 8 вершин, значит, \(8 - 1 = 7\) рёбер. Удалить нужно \(10 - 7 = 3\) ребра. Цикломатическое число равно 3.
Например, остовные деревья получаются, если удалить рёбра \(de\), \(be\), \(gh\) или рёбра \(ab\), \(eg\), \(ch\).
В каждом из двух деревьев 8 вершин и 7 рёбер, любые две вершины соединены цепью, циклов нет.
б) В графе 6 вершин и 9 рёбер. В любом его остовном дереве 6 вершин, значит, \(6 - 1 = 5\) рёбер. Удалить нужно \(9 - 5 = 4\) ребра. Цикломатическое число равно 4.
Например, остовные деревья получаются, если удалить рёбра \(bc\), \(ce\), \(de\), \(ef\) или рёбра \(ac\), \(bc\), \(be\), \(ef\).
В каждом из двух деревьев 6 вершин и 5 рёбер, любые две вершины соединены цепью, циклов нет.
Ответ: а) 3; б) 4.
