Hi-Tech

4:27PM Thursday, Feb 12, 2009

Два возможных варианта раскраски графа с девятью вершинами в четыре цвета. Изображение авторов исследования

Группа ученых из США и Германии разработала новый алгоритм подсчета раскрасок графа с фиксированным числом цветов, который может применяться в самом широком круге задач физики и математики. Об этом сообщается в пресс-релизе на сайте Института динамики и самоорганизации Макса Планка. Работа ученых опубликована в New Journal of Physics.

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

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

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

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

Смотрите также: Hi-Tech, Интернет, Hardware, SoftNews

Рассылки:
  Новости-почтой
  TV-Программа
  Гороскопы
  Job Offers
  Концерты
  Coupons
  Discounts
  Иммиграция
  Business News
  Анекдоты
Многое другое...