Страница 67 номер 85, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
В деревне 20 домов, между некоторыми из которых проложены тропинки. По тропинкам можно пройти от любого дома к любому другому и притом единственным образом. Сколько всего тропинок проложено в деревне?
Дома — вершины, тропинки — рёбра: граф связный, и цепь между любыми двумя вершинами ровно одна.
Циклов в нём нет: две вершины на цикле соединяли бы две разные цепи — по одной и по другой его части.
Связный граф без циклов — дерево, а в дереве с \(n\) вершинами \(n-1\) ребро: тропинок \(20 - 1 = 19\).
Ответ: 19 тропинок.
В деревне 20 домов, между некоторыми из которых проложены тропинки. По тропинкам можно пройти от любого дома к любому другому и притом единственным образом. Сколько всего тропинок проложено в деревне?
Дома — вершины графа, тропинки — его рёбра. По условию от любого дома можно пройти к любому другому, то есть граф связный, и притом единственным образом: цепь между любыми двумя вершинами ровно одна.
Циклов в таком графе нет. Если бы какие-то две вершины лежали на цикле, их соединяли бы две разные цепи — по одной и по другой части этого цикла, а единственность цепи такого не допускает.
Связный граф без циклов — это дерево, а дерево с \(n\) вершинами содержит \(n-1\) ребро. Домов 20, значит, тропинок \(20 - 1 = 19\).
Ответ: 19 тропинок.
