Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
МатематикаВопрос:
7. Какое наименьшее и какое наибольшее количество листьев может иметь дерево, у которого: а) 5 вершин; б) 55 вершин; в) 2025 вершин?
Ответ:
а) 5 вершин:
- Наименьшее количество листьев: 2. Это происходит в случае пути (линейного графа).
- Наибольшее количество листьев: 4. Это происходит в случае звезды (одна центральная вершина, соединенная со всеми остальными).
б) 55 вершин:
- Наименьшее количество листьев: 2. Это происходит в случае пути (линейного графа).
- Наибольшее количество листьев: 54. Это происходит в случае звезды (одна центральная вершина, соединенная со всеми остальными).
в) 2025 вершин:
- Наименьшее количество листьев: 2. Это происходит в случае пути (линейного графа).
- Наибольшее количество листьев: 2024. Это происходит в случае звезды (одна центральная вершина, соединенная со всеми остальными).
Похожие
- Запишите по возрастанию степени всех вершин графа (рис. 19).
- Определите, в каком из трёх описанных случаев граф существует, и постройте вгор: 1) траф из 5 вершин, в котором все верщины имеют степень 3; 2) траф из 8 вершин, в котором зое вершины имеют стопень 2; 3) граф из 8 вершин, в котором все вершины имеют степень 8
- На контрольной работе по вероятности и статистико каждый из 24 десятиклассников решил по 5 залач, а каждую задачу решило ровно 20 человек. Сколько задач было контрольной работе?
- Укажите, какие из перечисленных путей являются циклами в графе (рис. 20). В ответ выпишите их номера. 1) abafgkoda; 2) abcadca; 3) fghf 4) aeafa; 5) kebajigk.
- Какой из графов, изображённых на рисунках 21–23, содержит эйлеров цикл? Перечислите номера его вершин в порядке прохождения по циклу.
- 6. В государстве 12 городов, между некоторыми из которых построены автомагистрали. По магистралям можно доехать от любого города к любому другому и притом единственным способом. Сколько всего автомагистралей проложено в государстве?
- 8. В локальную сеть включено 20 компьютеров, причём каждая пара компьютеров соединена напрямую оптоволоконным кабелем. Администратор решил оптимизировать сеть, сократив число кабелей. Какое наибольшее их количество можно удалить, чтобы можно было по-прежнему передать информацию с любого компьютера на любой другой, но, возможно, через другие компьютеры?
