Есть идея!

Алгоритм Крускала (названный в честь Джозефа Б. Крускала, который впервые предложил его) позволяет свести построение минимальной сети к следующим этапам.

Определить расстояния между любыми двумя точками и расположить все расстояния в порядке возрастания (напомним, что расстоянием между двумя вершинами в графе называется число ребер, ведущих из одной вершины в другую). Кратчайшее расстояние равно 1, затем идет расстояние 2 и т. д. Если два расстояния одинаковы, то безразлично, какое из них считать первым. Соединить отрезками прямых все точки, расстояние между которыми равно 1. Затем соединить отрезками прямых все точки, расстояние между которыми равно 2, 3, 4, 5 и т. д. Никогда не проводить отрезок, замыкающий цикл. Если проведенная линия замыкает цикл, отбросить соответствующую пару точек и перейти к рассмотрению точек, разделенных следующим по величине расстоянием. Проделав все эти операции, мы получим минимальное дерево, соединяющее все заданные точки.

Минимальные деревья обладают интересными свойствами. Например, все рёбра пересекаются только в вершинах, причем в одной вершине пересекается не более 5 ребер.

Минимальные деревья отнюдь не обязательно совпадают с кратчайшей сетью, соединяющей n точек. Напомним, что дополнять сети новыми вершинами не разрешается. Если снять запрет на новые вершины, то сети могут стать короче. В качестве простого примера достаточно рассмотреть четыре вершины единичного квадрата. Минимальное дерево состоит из любых трех сторон квадрата (рис. 13, слева). Предположим, что разрешается вводить новые вершины. Существует ли тогда сеть короче 3, соединяющая четыре вершины?

Большинство людей считает, что минимальную сеть образуют две диагонали квадрата (рис. 13, посредине), но это не верно. Правильное решение изображено на рис. 13, справа. Суммарная длина двух диагоналей квадрата равна 2√2 ≈ 2,82… Суммарная длина сети на правом рисунке меньше, она равна лишь 1 + √3 ≈ 2,73…

Общая задача о построении минимальной сети, соединяющей n заданных точек на плоскости (при условии, что разрешается вводить новые вершины), известна под названием задачи Штейнера. Она решена лишь в отдельных частных случаях. Эффективный алгоритм, позволяющий определять положение «точек Штейнера» (новых вершин) минимального дерева Штейнера, соединяющего n заданных точек плоскости, не известен. Задача Штейнера имеет многочисленные приложения в технике — от элементов микросхем, используемых в ЭВМ, до прокладки кратчайших сетей железных дорог, воздушных маршрутов, телефонных линий и любых других видов транспорта и связи.

Хирурги и инфекция

В чаще тропических джунглей расположен госпиталь, в котором работают три хирурга: Джонс, Смит и Робисон.

Вождь местного племени поступил в госпиталь по подозрению в опасном инфекционном заболевании, требовавшем неотложного хирургического вмешательства. Ввиду особой сложности операции, ее должны были проводить, сменяя друг друга, все три хирурга. При осмотре вождя они могли заразиться и стать носителями инфекции.

Каждый хирург оперирует в тонких резиновых перчатках. Если он болен, то инфицируется внутренняя поверхность перчаток, соприкасающаяся с его руками. Если болен вождь, то инфицируется наружная поверхность перчаток.

Перед самым началом операции в комнату, где хирурги мыли руки, вбежала старшая сестра мисс Клини.

Мисс Клини. У меня для вас плохие новости, уважаемые эскулапы.

Мисс Клини. У нас остались только две пары стерильных перчаток: одна пара белых и одна пара синих.

Доктор Джонс. Только две пары? Если я оперирую первым, то обе стороны моих перчаток могут оказаться зараженными. После Смита, если он будет оперировать вторым, окажутся зараженными обе стороны другой пары перчаток, и Робисону не в чем будет оперировать.

Вдруг лицо доктора Смита просветлело.

Доктор Смит. А что если я надену две пары перчаток — синие поверх белых. Одна сторона каждой пары инфицируется, а другая останется стерильной.

Джонс быстро схватил мысль коллеги.

Доктор Джонс. После вас я надену синие перчатки стерильной стороной внутрь, а Робисон, вывернув, наденет белые перчатки стерильной стороной внутрь. При этом каждый из нас избежит опасности заразиться.

Сестра Клини. А о вожде вы не подумали? Ведь если кто-нибудь из вас является носителем инфекции, то вы можете заразить вождя во время операции.

Справедливое замечание медсестры повергло хирургов в замешательство. Что делать? И тут мисс Клини осенило.

Сестра Клини. Я придумала, как вам втроем оперировать вождя, не подвергая ни себя, ни его риску заражения.

Никто из трех врачей так и не смог ничего предложить, но когда мисс Клини объяснила, в какой последовательности надлежит надевать и выворачивать перчатки, все согласились, что ее план действительно обеспечивает полную безопасность и вождя и хирургов. Как предложила действовать мисс Клини?

Снаружи и внутри