РЕКЛАМА

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

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

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

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

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

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

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

Tugcrereled
17 июня 2011 21:52
Когда вы решитесь скачать торрент клиент , постарайтесь быть готовым к возможным
испытаниям, начиная от забравшегося в ваш компьютер вируса и заказнчивая
настырным стуком в вашу дверь от милицейского патруля, который имеет ордер, чтобы конфискавать
ваш лаптоп и проверить его на наличие ворованных программных копий.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Понедельник, 29 Мая
USD 1.8598
EUR 2.0868
RUB 0.0328
Himley1 2 минут назад
Цитата: Papasha69
Не пытайтесь спорить с DIANEST

А кто с этим зимбабвийским усосом спорит?
qackso858 2 минут назад Народ, сoврeмeнный oбрaз жизни убивaет нaс: тoксичнaя срeдa, нeздоровaя eдa, трансжиры и кaнцерогены, aлкoголь и курeниe и многoe другоe приводит к накoплeнию TOКCИНOВ и ПAPAЗИTOВ в нашeм организмe. Нeдaвно oбнаружили что причиной рaковых oпухолeй и 93% смeртельных болeзней - тoксины и пaрaзиты внутри нас. Вoт почитайтe как с ними бороться --- http://upl.pp.ua/eda qackso858 3 минут назад Народ, сoврeмeнный oбрaз жизни убивaет нaс: тoксичнaя срeдa, нeздоровaя eдa, трансжиры и кaнцерогены, aлкoголь и курeниe и многoe другоe приводит к накoплeнию TOКCИНOВ и ПAPAЗИTOВ в нашeм организмe. Нeдaвно oбнаружили что причиной рaковых oпухолeй и 93% смeртельных болeзней - тoксины и пaрaзиты внутри нас. Вoт почитайтe как с ними бороться --- http://upl.pp.ua/eda Его Малая 4 минут назад Меня опять преследует свинина по обычной городской цене. Вот только на этот раз все мясо без косточки, сала и шкурки.

Тазобедренная часть
Она же
Лопаточная часть
Полендвица!!!

Фото сделано минут 30 назад, очереди ноль, центр Минска. На ценнике видно названия магазина. Так что господа особо упоротые, перестаньте истерично скулить как сучки и го за мясом!
Juvikont 6 минут назад Надо детей того кто это сделал накормить этим. Margasan 6 минут назад Мамаша не знала, что у них есть автомобиль? Заглянули в него только по запаху?
Полицаи тоже решили не проверять машину?
Бред какой-то!
Himley1 9 минут назад
Цитата: dianest
беларусы сейчас на Украину на закупы?

Ну да - сейчас денег нет.
Цитата: dianest
ты с утра чего ебнул наркоша?

Диарест, долбишь из нас двоих только ты. Друзья из Лугандона видать подгоняют регулярно.
Цитата: dianest
я понимаю, что ты дальше дивана никуда не ездил

Плохо понимаешь. Хотя куда тебе ущербу зимбабвийскому.
Цитата: dianest
или максимум с посещения туристического Львова или Киева

Самое смешное - там я и не был практически.
Цитата: dianest
Но кабы ты проехал немного по стране,

А вот по стране ездил
Цитата: dianest
ты бы не писал подобную херь

Да помню-помню - у тебя на это копирайт. Приходится правду писать.
Цитата: dianest
стыдно было бы

Стыдно с умным видом пересказывать высеры кремлядских поцреотов, как это делаешь ты.
cube.by 16 минут назад Дуре просто повезло. Был один случай, парень с девушкой взяли лодку, романтически плавали вечером, потом хотели пустить ракетницу не соблюдая ТБ. Девушке заряд попадает в живот, т.к. температура очень высокая, сами понимаете что произошло.
Новости от партнеров