Российская Информационная Сеть
English   Контакты
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ
ТОП-дайджест  Хроника  Эксклюзив  Фоторепортажи  Личное мнение  Погода  Комментарии  Поиск  RSS  Интернет-радио  
 Топ 20 сегодня Топ 20 сегодня 
В Италии мать забыла девочку в машинеВ Италии мать забыла девочку в машине
Google теряет рекламодателей из-за экстремистского видеоGoogle теряет рекламодателей из-за экстремистского видео
Катар продолжает импортировать газ своим соседямКатар продолжает импортировать газ своим соседям
далее топ дня...
 Фотожурнал: фото-топ за месяц, галерея всех фото Фотожурнал 
 Новости партнеров
 Топ новости разделов сегодня Топ новости разделов 
В Астане проходит саммит ШОСВ Астане проходит саммит ШОС
Катар продолжает импортировать газ своим соседямКатар продолжает импортировать газ своим соседям
В Марокко были найдены самые старые останки Homo sapiensВ Марокко были найдены самые старые останки Homo sapiens
Шельфовый ледник в Антарктиде трещит по швамШельфовый ледник в Антарктиде трещит по швам
Apple представила новые умные колонки HomePodApple представила новые умные колонки HomePod
В Италии мать забыла девочку в машинеВ Италии мать забыла девочку в машине
В Индии вспыхнули беспорядки из-за убийства фермеровВ Индии вспыхнули беспорядки из-за убийства фермеров
Google теряет рекламодателей из-за экстремистского видеоGoogle теряет рекламодателей из-за экстремистского видео
Дружба с экс-возлюбленными вызывает психические расстройстваДружба с экс-возлюбленными вызывает психические расстройства
Ариана Гранде и другие звезды выступили в МанчестереАриана Гранде и другие звезды выступили в Манчестере
далее...
 Личное мнение Личное мнение 

 Новости о знаменитостях Знаменитости 
Новость: 22 июля 09:00: Родион Газманов устроил "Самый яркий день"Родион Газманов устроил "Самый яркий день"

Новость: 12 августа 13:59: Театр МДМ будет ставить "Призрака Оперы"Театр МДМ будет ставить "Призрака Оперы"


 Заплатим за ваше мнение!
Получайте до 1,5 долларов за каждую заполненную анкету!



 Новости науки и техники Новости науки и техники 
12 февраля, 19:34

Математики научились считать раскраски карт

Новости науки и техники: Математики научились считать раскраски карт
Новости по теме:
Группа ученых из США и Германии разработала новый алгоритм подсчета раскрасок графа с фиксированным числом цветов, который может применяться в самом широком круге задач физики и математики.

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

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

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

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

Новое открытие может применяться и в физике. В антиферромагнетиках магнитные моменты атомов располагаются так, что у соседних по решетке атомов моменты имеют противоположное направление. Подобное состояние, аналогично карте, легко кодируется с помощью графа.
[Читать все комментарии] [Напечатать новость]
LENTA.RU http://lenta.ru
  Комментарии к новости 
[Добавить комментарий]

Комментариев к этой новости пока нет. Добавьте первым свой комментарий!
[Добавить комментарий]
 Хроника новостей: Новости науки и техники Хроника новостей 
Земле угрожают огромное количество комет

26 июля 16:50
Огромный ледник в Антарктиде раскололся изнутри

6 июля 16:54
Запуск новой ракеты-носителя в Китае закончился неудачно

3 июля 13:35
Япония планирует доставить человека на луну в 2030 году

29 июня 14:42
SpaceX провела два успешных запуска за выходные

26 июня 12:30
В парижском пригороде Ле Бурже открылся аэрокосмический салон

20 июня 16:58
Шельфовый ледник в Антарктиде трещит по швам

2 июня 11:42
Microsoft впервые показала крупнейший самолёт-носитель

1 июня 09:41
Российские ученые создали новый эталон килограмма

27 апреля 16:52
Cassini прошел сквозь кольца Сатурна

27 апреля 10:52
Астероид 2014 JO25 прошел на минимальном расстоянии от Земли

20 апреля 16:49
В Египте обнаружены 8 мумий

19 апреля 12:47
Гидротермальные жерла на Энцеладе могут хранить в себе жизнь

18 апреля 10:46
SpaceX запустила ракетоноситель

31 марта 13:36
В Петрозаводске возобновились испытания новейшего экраноплана

27 марта 15:36
На автомобиль установили первую систему "ЭРА-ГЛОНАСС"

23 марта 15:42
Тайна гибели первой советской подлодки "Декабрист" будет раскрыта

22 марта 16:53
К испытанию готовится самолет дальнего управления А-100 "Премьер"

17 марта 14:38
SpaceX отправит на Луну двух туристов

28 февраля 14:05
"Прогресс" успешно стартовал с космодрома Байконур

22 февраля 14:21
На МКС отправлен космический корабль "Дракон"

20 февраля 13:37
50-летие отмечает подземная Баксанская обсерватория

8 февраля 16:57
В Мордовии ученые научились выращивать искусственные кристаллы карбида кремния

7 февраля 16:48
Телескоп Хаббл запечатлел смерть звезды

7 февраля 12:31
Астрономы нашли причины загадочно быстрого движения Галактики

1 февраля 10:51
Астероид BH30 прошел на жутко близком расстоянии от Земли

31 января 13:23
Ученые обнаружили 40 неизвестных науке астероидов

26 января 16:20
На дорогах России в скором времени появятся беспилотные грузовики

23 января 11:30
НАСА: Мы не готовы к столкновению астероида с Землей

15 декабря 13:35
Морская авиация получила первый арктический Ми-8

23 ноября 16:11
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 >> 936
 Главная новость дня Главная новость дня 
Тысячи венесуэльцев начали двухдневную забастовку против Мадуро Тысячи венесуэльцев начали двухдневную забастовку против Мадуро
 
 Эксклюзив Эксклюзив 
Пора ли продавать акции Apple? Пора ли продавать акции Apple?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Опубликованы снимки первой зарубежной военной базы Китая
Натали рассекретила внешность младшего сына (фото)
Анджелина Джоли с детьми переехала в новый дом
Джастину Биберу запретили выступать на сцене в Пекине
Егор Холявин рискует своей жизнью ради пластики
 Новости партнеров
 Новости дня Новости дня 
 
  Copyright © RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ