Сириус. Комбинаторика. 7 класс. Введение в графы

В графе 100 вершин, степень каждой вершины равна 2. Какое максимальное число компонент связности может быть в этом графе?

Компонента связности - это кусочек графа, в котором вершины связаны ребрами.

Тут у нас получается, что у каждой вершины степень 2. Значит мы можем взять 3 вершины, соединить их между собой ребрами и получить самый маленький связанный подграф, удовлетворяющий условию со степенями вершин.

Так что чтоб получить максимальное число компонент нам надо разбить 100 вершин на группки из 3х вершин, ну и одна из 4х получится.

Поэтому получаем 100:3=33 таких группы.

Ответ: 33

Остальные задачи раздела