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

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

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

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

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

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

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

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

 

Новости Красноярска: Разработка красноярских ученых повысит эффективность лечения и реабилитации онкобольных

Разработка красноярских ученых повысит эффективность лечения и реабилитации онкобольных

26 Ноября 2020 г.
Они нашли способ повысить противоопухолевую активность клеток врожденного иммунитета
Новости Красноярска: Фестиваль науки увлечет опытами и лекциями мировых светил науки

Фестиваль науки увлечет опытами и лекциями мировых светил науки

24 Ноября 2020 г.
Сегодня стала известна программа ежегодного праздника науки
Новости Красноярска: На базе СФУ пройдёт юбилейный Всероссийский фестиваль науки «NAUKA 0+»

На базе СФУ пройдёт юбилейный Всероссийский фестиваль науки «NAUKA 0+»

18 Ноября 2020 г.
Главная тема фестиваля - «Физика будущего»
Новости Красноярска: Регистрация школьников на мейкертон «Политех#Делайснами — 2020»

Регистрация школьников на мейкертон «Политех#Делайснами — 2020»

10 Ноября 2020 г.
Школьников ждёт командная работа и очень много практики
Новости Красноярска: Сибирский федеральный университет поднялся в двух рейтингах THE Subject

Сибирский федеральный университет поднялся в двух рейтингах THE Subject

2 Ноября 2020 г.
Рост случился по физическим и инженерным наукам
Новости Красноярска: Сбер проведёт первую в России онлайн-конференцию AI Journey Junior для школьников

Сбер проведёт первую в России онлайн-конференцию AI Journey Junior для школьников

28 Октября 2020 г.
Мероприятие откроется открытым уроком по AI
САМОЕ ЧИТАЕМОЕ
Новости Красноярска: Красноярские сантехники – в топ-10 России

Красноярские сантехники – в топ-10 России

27 Ноября 2020 г.
Наши заняли шестое место из 100 команд
Новости Красноярска: Мама. Дороже золота

Мама. Дороже золота

27 Ноября 2020 г.
О главной женщине в жизни любого человека
Rss_45