Условие:
Известно, что в графе 29 вершин и 18 ребер. Какое наименьшее число компонент связности может иметь такой граф?
Решение:
Мы хотим минимизировать число компонент связности, то есть соединить как можно больше вершин в одиночные компоненты, используя доступные 18 ребер.
Шаг 1. Для того чтобы граф был связным, в нём должно быть не менее (число вершин – 1) ребер. Это свойство называется минимальным числом ребер для связного графа (дерево).
Шаг 2. Пусть мы ф...