Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в 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 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
1. Слайд – это изображение (или документ) в натуральном или электронном виде, предназначенное для просмотра через специальную аппаратуру графических объектов, текстов, видео или аудиоклипов. 2.Запускаете Power Point , и нажимаете "главная/создать слайд". Для создания второго и последующего слайдов воспользуйтесь кнопкой «Создать слайд» в левой части окна программы. Кнопка располагается во вкладке «Главная» верхней панели инструментов PowerPoint. Для выбора макета слайда при его создании кликните по треугольной стрелке, которая отображается прямо под кнопкой «Создать слайд». Выберите необходимый макет слайда и кликните по нему левой клавишей мыши. 3.В левой части окна нажать левой кнопкой мышки на нужный слайд и перенести его в нужный порядок 4.Вставка --> Картинка(Рисунок) 5.Выделите на слайде объект, который вы собираетесь анимировать и перейдите на вкладку «Анимация». Нажмите на кнопку «Настройка анимации» и справа появится соответствующая панель. 6.Нужно зайти во вкладку «Вставка», которая расположена в шапке презентации.Затем понадобится нажать на соответствующую иконку «Диаграмма». Выбрать тип диаграммы, в открывшемся окне Эксель, ввести данные, выделить их диапазоном, закрыть Эксель.
вершин, то общее число рёбер будет суммой по всем компонентам связности:
Объяснение:
Во вложении