Будет ли наше аналоговое вычислительное устройство работать также безотказно при числе точек больше трех? Попробуйте придумать такое расположение четырех точек, при котором наше устройство даст заведомо неверный результат. Указание: что произойдет, если четыре точки расположены в вершинах невыпуклого четырехугольника?
Изучением систем точек (вершин), соединенных линиями (ребрами), занимается теория графов — обширный и быстро развивающийся раздел современной математики. Существуют десятки теорем теории графов, позволяющие находить минимальные пути. Одни задачи, связанные с отысканием минимальных путей, давно решены, другие ожидают своего решения. Примером знаменитой решенной задачи может служить следующая.
На плоскости заданы n точек. Требуется соединить их отрезками прямых так, чтобы суммарная протяженность сети была наименьшей. Добавлять новые вершины к заданным запрещается. Сеть, которую требуется построить, естественно назвать минимальным деревом. Можете ли вы предложить алгоритм для построения минимального дерева?
Алгоритм Крускала (названный в честь Джозефа Б. Крускала, который впервые предложил его) позволяет свести построение минимальной сети к следующим этапам.
Определить расстояния между любыми двумя точками и расположить все расстояния в порядке возрастания (напомним, что расстоянием между двумя вершинами в графе называется число ребер, ведущих из одной вершины в другую). Кратчайшее расстояние равно 1, затем идет расстояние 2 и т. д. Если два расстояния одинаковы, то безразлично, какое из них считать первым. Соединить отрезками прямых все точки, расстояние между которыми равно 1. Затем соединить отрезками прямых все точки, расстояние между которыми равно 2, 3, 4, 5 и т. д. Никогда не проводить отрезок, замыкающий цикл. Если проведенная линия замыкает цикл, отбросить соответствующую пару точек и перейти к рассмотрению точек, разделенных следующим по величине расстоянием. Проделав все эти операции, мы получим минимальное дерево, соединяющее все заданные точки.
Минимальные деревья обладают интересными свойствами. Например, все рёбра пересекаются только в вершинах, причем в одной вершине пересекается не более 5 ребер.
Минимальные деревья отнюдь не обязательно совпадают с кратчайшей сетью, соединяющей n точек. Напомним, что дополнять сети новыми вершинами не разрешается. Если снять запрет на новые вершины, то сети могут стать короче. В качестве простого примера достаточно рассмотреть четыре вершины единичного квадрата. Минимальное дерево состоит из любых трех сторон квадрата (рис. 13, слева). Предположим, что разрешается вводить новые вершины. Существует ли тогда сеть короче 3, соединяющая четыре вершины?
Большинство людей считает, что минимальную сеть образуют две диагонали квадрата (рис. 13, посредине), но это не верно. Правильное решение изображено на рис. 13, справа. Суммарная длина двух диагоналей квадрата равна 2√2 ≈ 2,82… Суммарная длина сети на правом рисунке меньше, она равна лишь 1 + √3 ≈ 2,73…
Общая задача о построении минимальной сети, соединяющей n заданных точек на плоскости (при условии, что разрешается вводить новые вершины), известна под названием задачи Штейнера. Она решена лишь в отдельных частных случаях. Эффективный алгоритм, позволяющий определять положение «точек Штейнера» (новых вершин) минимального дерева Штейнера, соединяющего n заданных точек плоскости, не известен. Задача Штейнера имеет многочисленные приложения в технике — от элементов микросхем, используемых в ЭВМ, до прокладки кратчайших сетей железных дорог, воздушных маршрутов, телефонных линий и любых других видов транспорта и связи.
Хирурги и инфекция
В чаще тропических джунглей расположен госпиталь, в котором работают три хирурга: Джонс, Смит и Робисон.
Вождь местного племени поступил в госпиталь по подозрению в опасном инфекционном заболевании, требовавшем неотложного хирургического вмешательства. Ввиду особой сложности операции, ее должны были проводить, сменяя друг друга, все три хирурга. При осмотре вождя они могли заразиться и стать носителями инфекции.
Каждый хирург оперирует в тонких резиновых перчатках. Если он болен, то инфицируется внутренняя поверхность перчаток, соприкасающаяся с его руками. Если болен вождь, то инфицируется наружная поверхность перчаток.
Перед самым началом операции в комнату, где хирурги мыли руки, вбежала старшая сестра мисс Клини.
Мисс Клини. У меня для вас плохие новости, уважаемые эскулапы.
Мисс Клини. У нас остались только две пары стерильных перчаток: одна пара белых и одна пара синих.
Доктор Джонс. Только две пары? Если я оперирую первым, то обе стороны моих перчаток могут оказаться зараженными. После Смита, если он будет оперировать вторым, окажутся зараженными обе стороны другой пары перчаток, и Робисону не в чем будет оперировать.
Вдруг лицо доктора Смита просветлело.
Доктор Смит. А что если я надену две пары перчаток — синие поверх белых. Одна сторона каждой пары инфицируется, а другая останется стерильной.
Джонс быстро схватил мысль коллеги.
Доктор Джонс. После вас я надену синие перчатки стерильной стороной внутрь, а Робисон, вывернув, наденет белые перчатки стерильной стороной внутрь. При этом каждый из нас избежит опасности заразиться.
Сестра Клини. А о вожде вы не подумали? Ведь если кто-нибудь из вас является носителем инфекции, то вы можете заразить вождя во время операции.
Справедливое замечание медсестры повергло хирургов в замешательство. Что делать? И тут мисс Клини осенило.
Сестра Клини. Я придумала, как вам втроем оперировать вождя, не подвергая ни себя, ни его риску заражения.
Никто из трех врачей так и не смог ничего предложить, но когда мисс Клини объяснила, в какой последовательности надлежит надевать и выворачивать перчатки, все согласились, что ее план действительно обеспечивает полную безопасность и вождя и хирургов. Как предложила действовать мисс Клини?
Снаружи и внутри
Прежде чем объяснять великолепный выход из затруднительного положения, предложенный мисс Клини, постараемся основательно разобраться в первом варианте решения, исключавшем опасность заражения только для хирургов.
Пусть Б1 — внутренняя, а Б2 — наружная сторона белых перчаток, С1 — внутренняя, а С2 — наружная сторона синих перчаток.
Доктор Смит надевает обе пары перчаток: сначала он натягивает белые перчатки, а поверх них синие. Сторона Б1 инфицируется, так как соприкасается с руками доктора Смита, сторону С2 может инфицировать вождь. После операции Смит снимает обе пары перчаток. Доктор Джонс надевает синие перчатки стерильной стороной С1 внутрь, а доктор Робинсон выворачивает белые перчатки наизнанку и надевает их стерильной стороной Б2 внутрь.
Переходим теперь к описанию процедуры, предложенной мисс Клини.
Доктор Смит по-прежнему надевает 2 пары перчаток. Стороны Б1 и С2 могут оказаться после операции инфицированными, но стороны Б2 и С1 останутся стерильными.
Доктор Джонс надевает синие перчатки стороной С1 внутрь.
Доктор Робисон выворачивает белые перчатки наизнанку и надевает их стороной Б2 внутрь. Поверх белых перчаток он натягивает синие перчатки стороной С2 наружу.
Во всех трех случаях вождя касается только сторона С2 синих перчаток, поэтому он не подвергается опасности заразиться от кого-нибудь из хирургов.
Насколько известно, общий случай этой задачи никогда не рассматривался, хотя он и небезынтересен для любителей занимательной математики. Приведем его для тех, кто захочет испытать свои силы: сколько перчаток необходимо заготовить хирургической сестре, чтобы при самом жестком режиме экономии полностью исключить возможность заражения хирургов и пациентов, если известно, что n хирургам предстоит прооперировать k пациентов?
Глава 6
Словесные находки
Неожиданные решения различного рода задач о буквах, словах и предложениях
Математики любят играть в слова. Например, в серьезной книге Ф. Хараря и Э. Палмера «Перечисление графов»[5] мы встречаем примечание: «Рид сообщил Райту, что и он, и Райт допустили ошибку. Затем Рид и Райт, чтобы исправить положение вещей, указали в совместной работе на допущенную ранее ошибку. Возможно, что все это выглядело несколько иначе, ибо Райт утверждает, что он первый написал Риду». Примеров можно было бы привести так много, что они могли бы составить целую книгу.
Нетрудно понять, почему математикам нравятся такие шутки. Слова представляют собой не что иное, как комбинации букв, составленных в определенном порядке, так же как предложения — линейные последовательности слов, составленные в соответствии с формальными правилами синтаксиса. Таким образом, многое роднит лингвистику с комбинаторной математикой. Словесные квадраты по своей структуре аналогичны магическим квадратам. Знаки препинания в предложении соответствуют математическим символам (скобкам, плюсам, минусам и т. д.), вводящим «пунктуацию» в алгебраические предложения.
