Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в 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 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
Что могу сказать . Microsoft Paint — многофункциональный, но в то же время довольно простой в использовании растровый графический редактор компании Microsoft и есть на всех ос Windows . Первая версия Paint появилась в Windows 1.0. В Windows 3.0 был переименован в PaintBrush. Но потом в Windows 95 и поздних версиях Windows, он был опять переименован в Paint. Возможности и приёмы работы Многократное увеличение или уменьшение инструмента Полная палитра Выбор третьего цвета для рисования Замена цвета Десятикратное увеличение Прозрачное выделение Пользовательская кисть Подрезка вставленного изображения. В общем маленький , но удаленький Adobe Photoshop -многофункциональный графический редактор, разработанный и распространяемый фирмой Adobe Systems. Первая версия появилась в 1987 году. Её создал студент Мичиганского университета Томас Нолл для платформы Macintosh. Он назвал её Display, но в 1988 году переименовал в ImagePro. В сентябре 1988 года Adobe Systems купила права на программу, оставив разработчиком Томаса Нолла, а в 1989 году программу переименовали в Photoshop. В 1990 году появился Photoshop 1.0.В основном работает с растровым изображением , но есть и векторные инструменты. Доступен почти на всех платформах.Включая и телефоны.Но создавалась для макинтош. . Редактор создавался для редактирования изображения полиграфии, но сейчас очень популярен в веб (создания макетов сайтов , логотипов) , так же используется очень широко фотографами.Так же есть расширенная версия программы Adobe Photoshop Extended предназначена для более профессионального использования, а именно — при создании фильмов, видео, мультимедийных проектов, трехмерного графического дизайна и веб-дизайна, для работы в областях производства, медицины, архитектуры, при проведении научных исследований. Итог: Пайнт - это хороший и простой редактор , который есть во всех версиях Ос Windows . И он бесплатный . Хорошо подходит для маленьких задач. Обрезать фотки , увеличить размер . Добавить надпись . Фотошоп- это уже профессиональный инструмент . Который стоит довольно дорого , но очень хорошо справляется со своими задачами. Фотошоп используют во многих сферах . И конечно функционал у него намного больше. Так же есть специальные дополнительные пакеты (шрифты,кисти и многое другое) . Тут конечно не всё , но думаю продолжить и дополнить уже сможете сами. Удачи!
Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех 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 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
Итак, должно выполняться
Подставив в исходную формулу, получаем
Это и есть ответ.