РЕКЛАМА

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

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

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

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

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

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

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

Tugcrereled
17 июня 2011 21:52
Когда вы решитесь скачать торрент клиент , постарайтесь быть готовым к возможным
испытаниям, начиная от забравшегося в ваш компьютер вируса и заказнчивая
настырным стуком в вашу дверь от милицейского патруля, который имеет ордер, чтобы конфискавать
ваш лаптоп и проверить его на наличие ворованных программных копий.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Четверг, 08 Декабря
USD 1.9789
EUR 2.1220
RUB 0.0310
Flint 9 минут назад Филин,
Даже обижать не хочется
Flint 22 минут назад dianest,
Вот чесно скажу, ой как хочется пару аргументов вставить тебе в потдержку, но тут речь про свидомых, а им виднее))сколько мед не говори....
Flint 41 минут назад
Цитата: triangel
Как-то смотрела как этот хрен растят

У нас он вроде как сорняк растет, а вассаби (опятьже у нас) делают путем добавления красителя) Иногда тупо мешают из порошка. Ну дорогая это приправа для наших краёв. Борщь в японии поеште!!!
dianest 41 минут назад
Цитата: Либерман
А что принципиально изменилось с момента крайней публикации?

принципиально нет ибо "идет расследование", но всплыли подробности, которые на случайность ни как не тянут, имхо. Лишь в одном теле мвдешника, расстрелянного в машине почти 40 пуль. Я не могу представить, как можно "случайно" высадить несколько "магазинов" в в ментовскую машину разукрашенную знаками отличия с ног до головы
Flint 49 минут назад Xeops64,
Фотка чикатилы и его действия разные вещи, не?)))тут и первое и второе тупость.
Flint 76 минут назад Mab,
Так едь в иран!))) Ссылки на свои коменты в ризюме только оставь))) Бля, из уважения к украинским бабам не буду статистикой срать....
Мапка запомни! Мертвым похyй, живым тяжко.. Все бы хорошо, только про тупых таже история))))
Mab 96 минут назад
Цитата: dianest
сам придумал сам поржал?

dianest, сам придумал - сам поржал?
Я вообще-то знаю как по-английски почка.
Либерман 113 минут назад
Цитата: Tatur
два способа свалить в город, первый это пойти в армию, а второй поехать учиться в город и получить "городскую" специальность, но один хрен надо было что бы председатель дал справку)

Выглядит попроще, чем поменять цвет кожи.
Новости от партнеров

ИНТЕРЕСНОЕ:

Загрузка...
Сейчас на сайте
20 пользователей, 960 гостей