Задачу выполняют 10 устройств. Между некоторыми парами устройств проложены двусторонние каналы, всего каналов 10 (между одной и той же парой устройств не бывает более одного канала). Независимой группой назовём такую группу устройств, в которой от любого устройства можно добраться до любого другого по цепочке каналов, а между разными такими группами нет ни одного канала. Какое наибольшее число независимых групп можно получить в таких условиях?
Рассмотрим условие задачи. Имеется 10 устройств (вершин) и 10 двусторонних каналов (ребёр). Независимая группа – это компонента связности, то есть такая группа вершин, что между любой парой вершин существует путь по рёбрам, и между разными группами нет рёбер.
Шаг 1. Минимальное число рёбер, необходимое для того, чтобы s вершин были соединены (то есть формировали дерево), равно s–1. Если граф состоит из c компонент связности, а суммарное число вершин равно 10, то минимальное число рёбер в графе равно 10 – c.
Шаг 2. Нам дано ровно 10 рёбер. Обозначим c – число компон...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
