РЕКЛАМА

Загрузка...
Последовательность "синий-красный-красный-синий-красный-красный-синий-красный-красный" приведет в желтую вершину из любой другой вершины. Изображение 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
1502
11 февраля 2008
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь. Мы рекомендуем Вам зарегистрироваться либо зайти на сайт под своим именем.
Смотрите также
Флаги - краткое повествование цветовФлаги - краткое повествование цветов

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

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

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

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

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

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

Tugcrereled
17 июня 2011 21:52
Когда вы решитесь скачать торрент клиент , постарайтесь быть готовым к возможным
испытаниям, начиная от забравшегося в ваш компьютер вируса и заказнчивая
настырным стуком в вашу дверь от милицейского патруля, который имеет ордер, чтобы конфискавать
ваш лаптоп и проверить его на наличие ворованных программных копий.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Суббота, 23 Сентября
USD 1.9366
EUR 2.3198
RUB 0.0336
Vardisodo 4 минут назад
Цитата: Mab
я не ненавижу женщин.

ага) Ты даже на банане с девчонками ведешь себя очень сдержанно, я бы сказал разговариваешь сквозь зубы.
BiggiN 5 минут назад Spencer, сразу видно, что опытная
zootechnik_ua 38 минут назад
Цитата: sam po sebe
У меня почти такиеже

А у меня не почти - а такие же
так что я в тренде!!!!
Только ее нужно перекрасить в брюнетку, ей светлые волосы не идут
zootechnik_ua 41 минут назад Грязная... Mab 54 минут назад Vardisodo, я не ненавижу женщин. Я не понимаю зачем пиарить педофилок. Педофилов почему-то не пиарят. Vardisodo 56 минут назад
Цитата: Mab
Господи. Опять педофилка!

Серый, а ты всех женщин ненавидишь, или только натуралок?
Bym 119 минут назад В этом году впервые. Весной, когда было ещё холодно алкаш ночью пытался попасть через зоомагазин к себе домой (подъезд с другой стороны дома - запасной). С разбегу разгонялся и бился головой в закрытую дверь. Пару минут смотрел на сие действие, но потом он как-то неудачно оступился и разбил себе всё же личико. Вот тогда я вызвал нашу милицию.
Кстати приехали через 5 минут.
Spencer 137 минут назад Нда, стойка на коленках у неё неплохая...
Новости от партнеров
Сейчас на сайте
11 пользователей, 3051 гость