172 дня за решеткой. Катерина Борисевич
Коронавирус: свежие цифры
  1. В чем секрет храма в Будславе и что о нем надо знать. Вопросы и ответы о костеле, пережившем пожар
  2. Прогноз погоды на короткую рабочую неделю
  3. В Green City открывается фудкорт. Первым там заработает «МакДональдс», будет и новый для Минска бренд
  4. Выходец из БРСМ стал новым директором Оперного театра
  5. Остаться одному после 67 лет брака. Поговорили с героем, чья история любви год назад восхитила читателей
  6. Дело Тихановского и Статкевича будет рассматривать Гомельский областной суд
  7. «До переезда я думал, что это типичный Техас с перекати-поле». Белорусы — о жизни в Остине
  8. В Беларуси не хватает почти 84 тысяч работников. Какие кадры в дефиците
  9. Против беззакония и насилия. Девушки в белом гуляют по Минску уже девять месяцев
  10. Семье Ромы, который спас брата из горящего дома, выделили арендное жилье
  11. Эксперт поделился секретами, как легко и эффективно можно почистить газовую плиту
  12. Журналиста TUT.BY Катерину Борисевич перевели из Жодино в СИЗО Могилева
  13. Один из лучших минских спектаклей этого сезона. Почему надо посмотреть «Записки юного врача»
  14. Самое лютое соперничество в женской «фигурке» закончилось нападением. В Голливуде об этом даже сняли кино
  15. В Беларуси — сильная геомагнитная буря
  16. Стрельба в школе в Казани: погибли 9 человек
  17. Парень, который выжил. История 23-летнего Антона, который после ДТП 43 дня провел в коме и выкарабкался
  18. В Могилеве начался суд над Павлом Северинцем и другими, он закрытый. Всех пришедших поддержать выгнали из здания
  19. Многие известные люди поддержали перемены и осудили насилие. Что с ними теперь?
  20. «Боялись последствий со стороны банка». Что говорят в суде над топами Белгазпромбанка взяткодатели
  21. Дерматолог — о влиянии гель-лака на кожу и ногти, тревожных симптомах и противопоказаниях
  22. «Таких цен никогда не было». Древесина ставит рекорды по стоимости во всем мире. А что у нас?
  23. «Общество заточено на «откаты». Откровенный разговор с архитектором о строительстве частных домов
  24. Белорусские сигареты почти на 2 млн долларов задержали в Польше
  25. «С большой вероятностью после Лукашенко не будет преемственности». Эксперты о знаковом декрете
  26. Трехкратный восходитель на Эверест — о рисках, очередях к вершине и коронавирусе на такой высоте
  27. С 13 мая снова дорожает автомобильное топливо
  28. Мэр израильского Лода заявил о полной потере контроля над городом. Нетаньяху ввел режим ЧП
  29. Между израильтянами и палестинцами опять война? Разбираем очередное обострение на Ближнем Востоке
  30. «Парни, подкатывая, просят посоветовать пилу». История лесоруба Вики


фото63-летний израильский математик Авраам Трахтман (Avraham Trahtman), эмигрировавший в начале девяностых из России, доказал теорему, которая оставалась без доказательства 38 лет, сообщает газета The Jerusalem Post.

Доказательство будет опубликовано в Israel Journal of Mathematics. В настоящее время Трахтман работает в университете Бар-Илана, занимается алгеброй, конечными автоматами, формальными языками. Несколько лет после иммиграции Трахтман, однако, не мог устроиться по специальности, подрабатывал сторожем.

Теорема о раскраске дорог (Road colouring theorem/problem) была сформулирована израильскими математиками в 1970 году.

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

На иллюстрации приведен пример такого лабиринта: граф из восьми вершин, из каждой выходит по два ребра (в каждую также входит по два ребра, но идти можно только по исходящим, против стрелочки двигаться нельзя). Ребра окрашены в красный и синий цвет. Если путешественнику надо прийти в желтую вершину, голос с неба должен сказать ему "синий-красный-красный-синий-красный-красный-синий-красный-красный". Где бы ни стоял путешественник, пройдя по этой последовательности, он обязательно окажется в желтой вершине. Читатель может попробовать сам найти последовательность, гарантированно выводящую на зеленую вершину.

Формально теорема, доказанная Трахтманом, звучит следующим образом: каждый конечный сильно связный граф, все длины циклов которого взаимно просты и все вершины которого имеют одинаковое число исходящих ребер, имеет синхронизирующую раскраску. Теорема может применяться в теории графов, а также в теории конечных автоматов.
-5%
-25%
-30%
-35%
-45%
-20%
-50%
-50%