Бывший российский математик доказал "недоступную" теорему

Главная Наука
В мире
08:02 9 Февраля 2008
Источник: lenta.ru
версия для печати Ico_print

63-летний израильский математик Авраам Трахтман, эмигрировавший из России в начале девяностых, доказал теорему, которая оставалась без доказательства 38 лет.

В настоящее время Трахтман работает в университете Бар-Илана, занимается алгеброй, конечными автоматами, формальными языками.

Теорема о раскраске дорог была сформулирована израильскими математиками в 1970 году.

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

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

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

 

Новости Красноярска: Китайские ученые изучают генетику деревьев в Ергаках

Китайские ученые изучают генетику деревьев в Ергаках

10 Июля 2018 г.
Исследователи выясняют, как меняются жизненные процессы в столетних лиственницах
Новости Красноярска: Школьница из Красноярска предложила технологию строительства «вечных» дорог

Школьница из Красноярска предложила технологию строительства «вечных» дорог

17 Июня 2018 г.
Предложение школьницы получило грантовую поддержку
Новости Красноярска: СФУ бьет рекорды по попаданию в рейтинги

СФУ бьет рекорды по попаданию в рейтинги

8 Июня 2018 г.
Три достижения за два дня
Новости Красноярска: СФУ поднялся в Национальном рейтинге университетов

СФУ поднялся в Национальном рейтинге университетов

7 Июня 2018 г.
СФУ в Национальном рейтинге университетов занял 13 позицию
Новости Красноярска: Красноярские ученые нашли способ ускоренного заживления ожогов

Красноярские ученые нашли способ ускоренного заживления ожогов

26 Мая 2018 г.
Первые эксперименты провели на крысах
САМОЕ ЧИТАЕМОЕ
Новости Красноярска: Крупного застройщика в Красноярске подозревают в неуплате налогов на 24 млн рублей

Крупного застройщика в Красноярске подозревают в неуплате налогов на 24 млн рублей

17 Июля 2018 г.
Уголовное дело завели на исполнительного директора компании
Новости Красноярска: Дядя Леша. Лучший болельщик ФК «Енисей»

Дядя Леша. Лучший болельщик ФК «Енисей»

16 Июля 2018 г.
Ушел из жизни Алексей Курников
Новости Красноярска: Под Красноярском в ДТП с грузовиком погиб водитель иномарки

Под Красноярском в ДТП с грузовиком погиб водитель иномарки

19 Июля 2018 г.
Пассажир легкового автомобиля пострадал
Rss_45