Перевод статьи из электронной версии газеты "Franckfurten Allgemeine", посвященной результатам проекта распределенных вычислений Rectilinear Crossing Number

 

Полный граф - вызов компьютеру.

Математики все чаще занимаются проблемами, для решения которых не достаточны мощности даже самых мощных универсальных вычислительных машин. Однако, через Интернет можно объединить вычислительные мощности тысяч компьютеров.

          07  февраля 2007    Математики часто оказываются вовлеченными в такие проблемы, которые, на первый взгляд, не имеют никакого практического значения. Как пример - теория графов.

Граф - фигура, составленная из точек и линий, соединяющих некоторые из этих точек между собой. Точки называются узлами, а линии - ребрами. Для математика имеет значения только топологическая структура графов, а не точное  расположение его элементов. Таким образом, можно представлять себе узлы узлы бисером, а ребра резиновыми нитями. Мы можем применять бисер и нити совершенно любые, по желанию, без изменения сущности графа. Два графа могут выглядеть совершенно непохоже, хотя  это два различных представления одного и того же графа.

Сравнение с проводниками печатных плат

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

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

Необходимо найти: число пересечений

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

Казалось бы, если упростить проблему числа пересечений, то должна быть возможность легко определять число пересечений для заданного числа узлов. Но это ошибка. В 1960 году известный английский математик Ричард К. Гай, своей статьей, опубликованной в журнале Nabla начал охоту за решением проблемы числа пересечений. Многие математики откликнулись на этот призыв, но добыча оказалась невелика: к 2000 году были определены количество пересечений только для графов с числом узлов менее девяти.

Быстро растущие числа

Графы с одним, двумя или тремя узлами в принципе не могут иметь пересечений. Кроме того, четыре узла можно разместить таким образом, что шесть ребер не будут пересекаются. Только с граф с пятью узлами имеет, по крайней мере, одну точку пересечения. С возрастанием числа узлов быстро увеличивается и число пересечений. Для графов с шестью узлами их 3; с семью узлами - 9; с восемью узлами - 19; и с девятью узлами - 36.

В 2000 году Алексу Бродскому, Стефану Дюроше и Эллену Гезеру из Университета Британской Колумбии в Ванкувере, наконец, удалось обнаружить число пересечений для графов с десятью узлами. Независимо от них, используя другой метод, Освин Айхольцер, Франц Ауренхаммер и Ханнс Крассер из Технологического Университета Граца (Австрия) получили такой же результат.

Различные формы

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

С увеличением числа узлов, число разнородных графов увеличивается в геометрической прогрессии. Для десяти точек существует уже более 14 миллионов вариантов. Айхольцер и его исследовательская группа проанализировала  каждый из этих вариантов и обнаружили, в некотором роде в качестве побочного результата, что наименьшее число пересечений было 62, и только для 2 вариантов из 14 миллионов графов. Все другие формы графа имеют большее число пересечений. Воодушевленные этим успехом, они применили свой метод для  графов с одиннадцатью узлами. Исследователи проверили более двух миллиардов различных вариантов и обнаружили, что минимальное число пересечений равно 102.

Сеть в 7500 компьютеров

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

И тем не менее, требуемая  вычислительная мощность для этого исследования настолько велика, что технический университет Граца не в состоянии ее обеспечить. Поэтому Айхольцером был начат в 2004 году проект "Прямолинейное число пересечений" (Rectilinear Crossing Number Project), в котором каждый пользователь может через Интернет добавить вычислительные мощности своего собственного компьютера (http://dist.ist.tugraz.at/cape5). Уже более 7500 компьютеров из 80 стран присоединились к этому проекту.

Граф с 18 узлами

Исследование вскоре привело к успеху. В течение первых двух лет были рассчитаны число пересечений K для графов от 12 до 17 узлов: К(12) = 153,  К(13) = 229,  К(14) = 324,  К(15) = 447,  К(16) = 603 и К(17) = 798. Однако, до общего метода, с помощью которого можно было бы легко вычислить число пересечений для заданного числа узлов было еще очень далеко.

Однако Айхольцеру удалось разработать уравнения, которые могут быть использованы для оценки минимального количества пересечений. Он нашел число пересечений для графов с 19 и 21 узлами, в точности равными нижним пределам. Ему удалось определить, что К(19) = 1318 и К(21) = 2055. В декабре прошлого (2006) года, Айхольцеру и его группе, наконец, удалось вычислить число пересечений для графа с 18 узлами. Чтобы найти этот результат понадобилось 10.000 часов процессорного времени ежедневно. Количество пересечений было подтверждено в январе 2007 года, оно равно 1029.

 

Обновленный список лучших наборов точек, известных на данный момент, можно посмотреть здесь ...

Вернуться:   к описанию проекта RCN     на сайт BOINC.RU