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

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

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

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

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

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

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

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

 

Новости Красноярска: Красноярские ученые на форуме в «Сколково» предложили создать единую систему мониторинга научных проектов

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

19 Октября 2018 г.
Это поможет оптимизировать процессы принятия управленческих решений
Новости Красноярска: Красноярские ученые разработали инновационную мобильную энергоустановку

Красноярские ученые разработали инновационную мобильную энергоустановку

19 Октября 2018 г.
Она работает на основе альтернативных источников энергии
Новости Красноярска: Археологи из Минусинска нашли древнее захоронение в разрытом карьере

Археологи из Минусинска нашли древнее захоронение в разрытом карьере

6 Октября 2018 г.
На одной из плит видны изображения тагарской эпохи
Новости Красноярска: Свыше 500 студентов Красноярска прокачают свои «гибкие навыки»

Свыше 500 студентов Красноярска прокачают свои «гибкие навыки»

4 Октября 2018 г.
В СФУ пройдет масштабный тренинг
Новости Красноярска: На притоках Енисея обнаружили «следы» тропического моря

На притоках Енисея обнаружили «следы» тропического моря

3 Октября 2018 г.
Оно существовало 450 млн лет назад
Новости Красноярска: Красноярские ученые научились получать из опилок лекарство от тромбов

Красноярские ученые научились получать из опилок лекарство от тромбов

3 Октября 2018 г.
Эти соединения используются в медицине, фармацевтике и пищевой промышеленности
САМОЕ ЧИТАЕМОЕ
Новости Красноярска: Губернатор Красноярского края озвучил новый состав правительства

Губернатор Красноярского края озвучил новый состав правительства

22 Октября 2018 г.
В краевой администрации произошли значительные кадровые перестановки
Новости Красноярска: В Красноярске выбрали подрядчика для ремонта Театральной площади

В Красноярске выбрали подрядчика для ремонта Театральной площади

19 Октября 2018 г.
Реконструкцию выполнит компания «Красноярскдорремстрой»
Новости Красноярска: Около автовокзала на Взлетке построят деловой центр

Около автовокзала на Взлетке построят деловой центр

18 Октября 2018 г.
Транспортный узел планируется перенести
Rss_45