РЕКЛАМА

Загрузка...
Последовательность "синий-красный-красный-синий-красный-красный-синий-красный-красный" приведет в желтую вершину из любой другой вершины. Изображение Wikimedia Commons, созданное пользователем Quuxplusone.
63-летний израильский математик Авраам Трахтман (Avraham Trahtman), эмигрировавший в начале девяностых из России, доказал теорему, которая оставалась без доказательства 38 лет, сообщает газета The Jerusalem Post.
Доказательство будет опубликовано в Israel Journal of Mathematics. В настоящее время Трахтман работает в университете Бар-Илана, занимается алгеброй, конечными автоматами, формальными языками. Несколько лет после иммиграции Трахтман, однако, не мог устроиться по специальности, подрабатывал сторожем.' />

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

Бывший российский математик доказал "недоступную" теоремуПоследовательность "синий-красный-красный-синий-красный-красный-синий-красный-красный" приведет в желтую вершину из любой другой вершины. Изображение Wikimedia Commons, созданное пользователем Quuxplusone.
63-летний израильский математик Авраам Трахтман (Avraham Trahtman), эмигрировавший в начале девяностых из России, доказал теорему, которая оставалась без доказательства 38 лет, сообщает газета The Jerusalem Post.
Доказательство будет опубликовано в Israel Journal of Mathematics. В настоящее время Трахтман работает в университете Бар-Илана, занимается алгеброй, конечными автоматами, формальными языками. Несколько лет после иммиграции Трахтман, однако, не мог устроиться по специальности, подрабатывал сторожем.
Теорема о раскраске дорог (Road colouring theorem/problem) была сформулирована израильскими математиками в 1970 году.
Упрощенное наглядное представление теоремы может выглядеть следующим образом: путешественник оказывается в лабиринте, ему нужно добраться до определенного места. От каждого перекрестка можно пойти по k дорогам, причем каждая дорога окрашена в один из k возможных цветов. Голос с неба может подсказать путешественнику последовательность цветов, которая укажет ему, по каким дорогам идти, чтобы достичь цели. Но голос с неба не знает, на каком перекрестке стоит путешественник, откуда он пойдет. Для некоторых типов лабиринтов возможна такая последовательность цветов, которая приведет путешественника к цели независимо от того, на каком перекрестке он стоит. Задача состоит в том, чтобы определить, для каких типов лабиринтов это возможно.
На иллюстрации приведен пример такого лабиринта: граф из восьми вершин, из каждой выходит по два ребра (в каждую также входит по два ребра, но идти можно только по исходящим, против стрелочки двигаться нельзя). Ребра окрашены в красный и синий цвет. Если путешественнику надо прийти в желтую вершину, голос с неба должен сказать ему "синий-красный-красный-синий-красный-красный-синий-красный-красный". Где бы ни стоял путешественник, пройдя по этой последовательности, он обязательно окажется в желтой вершине. Читатель может попробовать сам найти последовательность, гарантированно выводящую на зеленую вершину.
Формально теорема, доказанная Трахтманом, звучит следующим образом: каждый конечный сильно связный граф, все длины циклов которого взаимно просты и все вершины которого имеют одинаковое число исходящих ребер, имеет синхронизирующую раскраску. Теорема может применяться в теории графов, а также в теории конечных автоматов.
1
1470
11 февраля 2008
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь. Мы рекомендуем Вам зарегистрироваться либо зайти на сайт под своим именем.
Смотрите также
Флаги - краткое повествование цветовФлаги - краткое повествование цветов

АмерикаКрасный - поддерживающие войну в иракеБелый - не поддерживающиеСиний - не знающие, где находицца ИракКолумбияКрасный - экспорт банановСиний - э...

Красный iPhone 3GКрасный iPhone 3G

В ближайшее время возможно появление iPhone 3G красного цвета. Который собираются выпустить на праздники для увеличения объёма продаж.С учетом того, ч...

Самый популярный цвет автомобилей сменился впервые за 11 летСамый популярный цвет автомобилей сменился впервые за 11 лет

Самым популярным цветом машин в 2011 году стал… белый. Сразу 21% автомобилей, проданных в этом году в мире, было покрашено белым лаком.Ранее одиннадца...

Загрузка...
Комментарии

Tugcrereled
17 июня 2011 21:52
Когда вы решитесь скачать торрент клиент , постарайтесь быть готовым к возможным
испытаниям, начиная от забравшегося в ваш компьютер вируса и заказнчивая
настырным стуком в вашу дверь от милицейского патруля, который имеет ордер, чтобы конфискавать
ваш лаптоп и проверить его на наличие ворованных программных копий.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Суббота, 22 Июля
USD 1.9351
EUR 2.2534
RUB 0.0328
luol 205 минут назад Ужас!!! Jussi 211 минут назад Прокуратор Иудеи,
да? что то не заметил. слабенькие изгибы, с поцентру сделаным бардюром и знаком есть, но даж на фуре, когда вспышку проебешь на 90 км ч проходится на ура. но зато знаешь, что пора притормаживать, поэтому эфектвно относительно, если с головой дружишь
tergo2000 221 минут назад Вид- нимфоманки
Подвид -нимфоманки обыкновенные
Тип- нимфоманки обыкновенные недотрахи)
MegaSchuster 232 минут назад
Цитата: Либерман
Бомбануло? Стыдно всё-таки?

Цитата: Либерман
Влом угадывать, о ком ты.

ну действительно же Шелдон самый натуральный - занудствующий мозгоёб в терминальной стадии
cancer 245 минут назад
Цитата: vitut
Какая же у пороша пропитая отекшая рожа.

А чего у всех страдающих алкоголизмом сложилось мнение что и порох пьющий?
Либерман 248 минут назад
Цитата: MegaSchuster
ой млять на себя посмотри уродец физический и моральный, насеменил всей банане

Бомбануло? Стыдно всё-таки?
Цитата: MegaSchuster
Твой любимый оппонент в тупорылых спорах уже давно спит, а ты только к ночи раскочегариваешься, вам нужно циклы совместить

Влом угадывать, о ком ты.
Mab 251 минут назад
Цитата: Margasan
11.1 - не нарушено. Начат обгон, когда трактор и не думал поворачивать (поворотник).

Для меня нарушено. Регик создал опасность для движения другим учасникам дорожного движения. Как результат ДТП.

Цитата: Margasan
Тут вообще без комментариев.

Что вам без комментариев? Тупые совсем? Или хотите такими казаться?
MegaSchuster 261 минут назад
Цитата: Либерман
Я хотел бы, чтобы люди поменьше демонстрировали искореженное мировоззрение и не так рьяно светили моральным уродством, по аналогии с физическим. Отвратно же.

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