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

122

281

Посмотреть ответы 2

Ответы на вопрос:

derugaboris200p08t6d

Информатика

4,6(42 оценок)

Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). если в i-ой компоненте связности вершин, то общее число рёбер будет суммой по всем компонентам связности: требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна n и ni - натуральные числа. если k = 1, то всё очевидно - ответ n(n - 1)/2. пусть k > 1. предположим, n1 < = n2 < = < = nk - набор чисел, для которых достигается максимум, и n1 > 1. уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в k-ую компоненту связности. вычислим, как изменится сумма квадратов: поскольку по предположению n1 > 1 (тогда и nk > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. выкинем эту компоненту связности, останутся k - 1 компонента связности и n - 1 вершина. будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине. итак, должно выполняться подставив в исходную формулу, получаем это и есть ответ.

lariliv75

Информатика

4,5(64 оценок)

Function t10_q(x,q: longint): string; const s='0123456789abcdefghi'; var t,m: longint; r: string; begin t: =x; r: =''; while t> =q do begin m: =t mod q; r: =s[m+1]+r; t: =t div q end; t10_q: =s[t+1]+r end; { тестирование } var q,n: longint; begin write('введите основание системы счисления (2-20): '); readln(q); write('введите натуральное число для перевода: '); readln(n); writeln(n,'(10)=',t10_q(n,q),'(',q,')') end. тестовое решение: введите основание системы счисления (2-20): 16 введите натуральное число для перевода: 16350 16350(10)=3fde(16)