Какое максимальное количество ребер у неориентированного графа с N вершин и K компонент связности. Напомню, что для полного неориентированного графа это N * (N - 1) / 2

Предыдущий
вопрос Следующий
вопрос

Для неориентированного графа с K компонентами связности максимальное количество ребер будет достигаться в случае, когда каждая компонента связности представляет собой полный граф. Тогда количество ребер в каждой компоненте будет равно N_i * (N_i - 1) / 2, где N_i - количество вершин в i-й компоненте связности.

Итак, суммарное количество ребер в графе будет равно сумме количеств ребер в каждой компоненте связности:

Количество ребер = N_1 (N_1 - 1) / 2 + N_2 (N_2 - 1) / 2 + ... + N_K * (N_K - 1) / 2

где N_1 + N_2 + ... + N_K = N

Для максимизации количества ребер нужно максимизировать каждый из множителей в сумме. Это происходит в случае, когда каждая компонента связности содержит по одной вершине, то есть N_i = 1 для всех i. В этом случае суммарное количество ребер будет максимальным:

Количество ребер = 1 0 + 1 0 + ... + 1 * 0 = 0

Таким образом, в неориентированном графе с N вершинами и K компонентами связности максимальное количество ребер равно 0.