Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Графы >> Номер 22

[Назад]    [Содержание ]    [Вперед]

  


Номер 22


  Условие: Номер 22


Задача 22. Имеется N точек и M проводков. Проводком можно соединить некоторую пару различных точек, причем пара может быть соединена не более чем одним проводком. Все проводки должны быть использованы. Пусть Di - количество проводков, которые будут соединены с точкой с номером i, i=1, ..., N. Необходимо соединить N точек с помощью M проводков таким образом, чтобы сумма S=D1*D1 + D2*D2 + ... + Dn*Dn была максимальной. Вывести величины Di в неубывающем порядке и. по требованию (priznak=1), список соединений. ВВОД: <Введите N:> N (N<=100) <Введите M:> M (M<=1000) <PRIZNAK=> PRIZNAK ВЫВОД: <Результирующая конфигурация:> Di в неубывающем порядке. <Сумма S> S <Список соединений> <Точку 1 соединить с> список точек ..... <Точку N соединить с> список точек

  Решение задачи: Номер 22


Решение задачи 22. Показывается, что точное решение есть максимум из двух решений, полученных при помощи следующих эвристик: 1) Вершину 1 соединяем последовательно с вершинами 2, 3, ...,N. Вершину 2 соединяем последовательно с вершинами 3,4,...,N. ...... Вершину i соединяем последовательно с вершинами i+1, i+2, ...,N. ...... и так до тех пор, пока хватит проводков. 2) Вершину 2 соединяем с вершиной 1. Вершину 3 соединяем последовательно с вершинами 1,2. ...... Вершину i соединяем последовательно с вершинами i-1, i-2,...,1. ...... и так до тех пор, пока хватит проводков.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017