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

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

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

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

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

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

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

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

 

Новости Красноярска: Красноярск станет завершающим городом для мероприятий Всероссийского Фестиваля науки «NAUKA 0+» в 2017 году

Красноярск станет завершающим городом для мероприятий Всероссийского Фестиваля науки «NAUKA 0+» в 2017 году

1 Декабря 2017 г.
«Норникель» продолжает в этом году поддержку самого большого научного форума в стране
Новости Красноярска: Ученые из Красноярска научились перерабатывать человеческие отходы в космосе

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

27 Ноября 2017 г.
Отходы жизнедеятельности превращают в питательные вещества для растений
Новости Красноярска: Красноярские школьники изобрели робота для мытья окон

Красноярские школьники изобрели робота для мытья окон

2 Ноября 2017 г.
На изобретение робота ушло 6 месяцев
Новости Красноярска: «Норникель» проведет в заполярных городах фестиваль научных открытий

«Норникель» проведет в заполярных городах фестиваль научных открытий

18 Октября 2017 г.
Праздник пройдет в Норильске и Мончегорске
Новости Красноярска: В Красноярском крае снизился уровень развития науки и новых технологий

В Красноярском крае снизился уровень развития науки и новых технологий

17 Октября 2017 г.
Регион оказался на 22 месте среди 85 субъектов РФ
САМОЕ ЧИТАЕМОЕ
Новости Красноярска: 89-летнюю красноярку задержали в супермаркете по подозрению в краже

89-летнюю красноярку задержали в супермаркете по подозрению в краже

11 Декабря 2017 г.
Женщину держали в магазине около четырех часов
Новости Красноярска: Красноярск может получить статус столичного города

Красноярск может получить статус столичного города

7 Декабря 2017 г.
Это позволит изменить подходы к финансированию и управлению городом
Новости Красноярска: В трех районах Красноярска новостройки оказались на треть дешевле вторичного жилья

В трех районах Красноярска новостройки оказались на треть дешевле вторичного жилья

7 Декабря 2017 г.
Больше всего за год подешевели квартиры в новых домах Железнодорожного, Свердловского и Центрального районов
Rss_45