Перейти к основному содержанию

Теорема Трахтмана

Теорема ТрахтманаМатематик Авраам Трахтман, между прочим, ранее проживавший в России, а ныне в Израиле, в возрасте 63 лет сумел найти доказательство теоремы (Road colouring theorem/problem), которая была сформулирована в 70-ых. годах израильскими математиками и до недавнего времени не доказана.

Математик в настоящее время преподает алгебру в университете Бар-Илана. После эмиграции не сразу смог устроиться по специальности и приходилось подрабатывать сторожем.

Наглядный вариант теоремы выглядит следующим образом:
человеку необходимо попасть в назначенное место, но при этом находясь в лабиринте. Каждая тропа окрашена определенным цветом, причем можно пройти только по тропам от перекрестка. Человеку может быть дана подсказка свыше о последовательном выборе цвета троп для достижения поставленной цели. Однако помощнику свыше неизвестно о местонахождении человека. Иные разновидности лабиринтов приводят человека в нужное место, не смотря на выбранную последовательность троп. Задаче же состоит в определении подобной возможности для иных разновидностей лабиринтов.

Иллюстрированный пример это как раз отображает, а именно:
восемь вершин, из которых исходит и входит по два ребра, окрашенных в синий и красный цвета соответственно. Передвигаться допустимо только по указателям – стрелкам, в обратном же направлении – запрещено. Например, человеку необходимо достигнуть желтой цели, тогда свыше ему приходит помощь в виде последовательности передвижений: синий-красный-красный-синий-красный-красный-синий-красный-красный. И не смотря на местонахождение, человек в любом случае окажется у желтой цели.

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

Между прочим, можно самими попробовать найти последовательности достижения зеленой цели. Не желаете ли попытаться? ,)

Можно-можно, а

Аватар пользователя katena

Можно-можно, а вот нужно ли... или больше тридцати лет на доказательство этой теоремы мало?!

Блин, мот я

Аватар пользователя Марио

Блин, мот я что-то не так делаю, но я по подсказке, указанной в статье, прошла до жёлтой цели и без трёх последних стрелок...мде, я - блондинко :тупняк:

направления.

Аватар пользователя Студент

направления. учла?

------------------------------------
- К черту статистику, нам нужны имена, адреса, телефоны!

Сейчас тоже

Аватар пользователя Ю_ЗвЕРь

Сейчас тоже гляну.

А ведь интересно очень. Катя, а разве не приятно ощущать, что приложил усилия в чем-то особенном? Загадочность, необычность движет. ИМХо ,)

Она движет как

Аватар пользователя katena

Она движет как прогрессом, так и полным застоем.