7класс
Страница 15 номер 30, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Глава 10. Деревья и плоские графы. §58. Остовное дерево и цикломатическое число графа. Страница 15. Номер 30
Задание / условие:
Найдите цикломатическое число связного графа, в котором: а) 6 вершин и 12 рёбер; б) 12 вершин и 23 ребра.
Решение:
Остовное дерево связного графа содержит все его вершины, а в конечном дереве вершин на одну больше, чем рёбер.
а) В любом остовном дереве этого графа 6 вершин. Значит, в нём \(6 - 1 = 5\) рёбер. Удалить нужно \(12 - 5 = 7\) рёбер. Цикломатическое число равно 7.
б) В любом остовном дереве этого графа 12 вершин. Значит, в нём \(12 - 1 = 11\) рёбер. Удалить нужно \(23 - 11 = 12\) рёбер. Цикломатическое число равно 12.
Ответ: а) 7; б) 12.
Решение подготовила Екатерина Копова, учитель математики первой категории
