РЕКЛАМА

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

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

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

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

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

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

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

Tugcrereled
17 июня 2011 21:52
Когда вы решитесь скачать торрент клиент , постарайтесь быть готовым к возможным
испытаниям, начиная от забравшегося в ваш компьютер вируса и заказнчивая
настырным стуком в вашу дверь от милицейского патруля, который имеет ордер, чтобы конфискавать
ваш лаптоп и проверить его на наличие ворованных программных копий.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Суббота, 21 Января
USD 1.9423
EUR 2.0754
RUB 0.0326
SabakaZ 44 минут назад
Цитата: basalt155
маньяка садиста нашёл бля.
Возможно, возможно. Все предпосылки имеются. Трансформация. Нужна трансформация. И ты близко к ней, очень близко.

Цитата: basalt155
мне моя жизнь и здоровье дороги.
Все серийники любят свою жизнь, тут нет ничего странного. Некоторые разочаровываются в своем существовании, как сами пытаются убедить окружающих. Но это от скуки. Да и наигранно. Но ты же скучать не собираешься. Твои руки не для скуки. Твои руки для орудия. Для вендетты обществу.

Цитата: basalt155
ещё в тюрьме не хватало сидеть.
Ты же знаешь, что тебя не споймают. По крайней мере, сразу. Средняя продолжительность охоты серийника длиться пару-тройку лет. Но ты продержишься дольше, ты знаешь. Ты же особенный.

Цитата: basalt155
всех не убьёшь ведь
Всех и не надо. Это слишком тривиально и прямолинейно. Нет филиграна, нет идеи, нет замысла. Ты же не какой-то массовый, желающий положить за раз как можно больше народу. Бездумно. Ради ничего. Пфф! Дилетантство! Ты не такой. Твои цели жестко определены, действия отточены, движения выверенны.
Охотник. Охота. Сайгак не должен подозревать ничего. Сайгак должен сам идти к тебе. Сайгак должен раскрыться пред тобой. И ты ему в этом поможешь. Ты его раскроешь. Ты внедришься. В тепло. Разрывая пошлые оковы сущности в виде кожного покрова. Проникая в хитросплетение мягкой пульсирующей плоти. Погружаясь в суть. Изнутри разрывая жалкие, немощные связи, приводящие этот организм в бессмысленное повторение одной и той же обыденной мерзости. Ибо только так сайгак сможет ощутить толику твоего необъятного внутреннего мира, сокрытого от других, пока не попавших под твое орудие милости. В этом твоя задача. В этом твое предназначение. В этом твой манифест.
В
ЭТОМ
ТВОЙ
ЗАМЫСЕЛ
Artiby 93 минут назад Помогите выбрать лучшую штукатурку... Главный калибр 115 минут назад очень неплохо, даже почти отлично! впервые рад за наших, что не фуфло, НО
1. в тройку не войдет, бо надо на англ петь
2. над номером надо хорошенько поработать.
3. слишком поздно ударились в народные мотивы. мода уже прошла на евро в этом направлении.
4. слегка хоббитонские мотивы. там про кельтов напомнили - имеет место быть.
в топ 10 выйдет, если без политики
Flint 144 минут назад Еще с довольно необычной хyйней по имени "гиталеле" пляшет индивид походу мужского пола (маликов походу имел машину времени?)). И что за кельтские напевы? Для полного пиздеца девченке надо было волынку дать, а заодно килт одеть. Но не такой аля лесби, а мудацкий такой, шотландский для дядькаф без трусов)) gimnast 149 минут назад Все дело в подставках Trend 177 минут назад Когда вижу новости про евровидение хочу чтоб оно быстрее прошло и закончилось submariner 201 минут назад Больше цыганщины товарищи цыгане. alexi.by 230 минут назад а мне нра
Новости от партнеров

ИНТЕРЕСНОЕ:

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