Усложним теперь исходную задачу. Предположим теперь, что в точках A, B и C находятся не населенные пункты с одинаковым количеством жителей, а три дома, причем в доме A живут 20 школьников, в доме B — 30 школьников и в доме C — 40 школьников. Все дети ходят в одну школу. Где следует выстроить школу, чтобы свести до минимума сумму расстояний, проходимых всеми детьми?
Если дети идут в школу по улицам города, то можно воспользоваться алгоритмом с голосованием, считая, что каждый ребенок обладает одним голосом. Он позволяет довольно быстро указать, где именно следует построить школу. Но если три дома возведены в чистом поле и школьники могут идти в школу по прямой, то как следует усовершенствовать нашу аналоговую вычислительную машину, чтобы и эта задача была ей под силу?
Нужно взять грузики с массами, пропорциональными числу детей в каждом доме. Положение узла покажет, где именно следует построить школу.
Сработает ли наше аналоговое устройство, если в одном доме учеников окажется больше, чем в двух других домах, вместе взятых, например, если 20 школьников живут в доме A, 30 школьников — в доме B и 100 школьников — в доме C? Да, сработает: грузик весом в 100 единиц будет тянуть свою веревочку до тех пор, пока узел не совместится с отверстием C. Это означает, что школу следует построить в точке C!
Будет ли наше аналоговое вычислительное устройство работать также безотказно при числе точек больше трех? Попробуйте придумать такое расположение четырех точек, при котором наше устройство даст заведомо неверный результат. Указание: что произойдет, если четыре точки расположены в вершинах невыпуклого четырехугольника?
Изучением систем точек (вершин), соединенных линиями (ребрами), занимается теория графов — обширный и быстро развивающийся раздел современной математики. Существуют десятки теорем теории графов, позволяющие находить минимальные пути. Одни задачи, связанные с отысканием минимальных путей, давно решены, другие ожидают своего решения. Примером знаменитой решенной задачи может служить следующая.
На плоскости заданы n точек. Требуется соединить их отрезками прямых так, чтобы суммарная протяженность сети была наименьшей. Добавлять новые вершины к заданным запрещается. Сеть, которую требуется построить, естественно назвать минимальным деревом. Можете ли вы предложить алгоритм для построения минимального дерева?
Алгоритм Крускала (названный в честь Джозефа Б. Крускала, который впервые предложил его) позволяет свести построение минимальной сети к следующим этапам.
Определить расстояния между любыми двумя точками и расположить все расстояния в порядке возрастания (напомним, что расстоянием между двумя вершинами в графе называется число ребер, ведущих из одной вершины в другую). Кратчайшее расстояние равно 1, затем идет расстояние 2 и т. д. Если два расстояния одинаковы, то безразлично, какое из них считать первым. Соединить отрезками прямых все точки, расстояние между которыми равно 1. Затем соединить отрезками прямых все точки, расстояние между которыми равно 2, 3, 4, 5 и т. д. Никогда не проводить отрезок, замыкающий цикл. Если проведенная линия замыкает цикл, отбросить соответствующую пару точек и перейти к рассмотрению точек, разделенных следующим по величине расстоянием. Проделав все эти операции, мы получим минимальное дерево, соединяющее все заданные точки.