Рубрика «планарные графы»

Два специалиста по информатике нашли в весьма неожиданном месте идею, которая как раз пригодилась им для прорыва в теории графов

Новый алгоритм проверки пересечений в графах прятался на виду - 1

В октябре 2019 Джейкоб Холм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное.

Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад.

Холм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму», — сказал Холм, специалист по информатике из Копенгагенского университета. «Возможно, мы полностью раскрыли этот вопрос».
Читать полностью »

Физик рассчитал, что жизнь всё-таки возможна в 2D-вселенной - 1

Окружающая реальность существует в трёхмерной Вселенной (плюс время), поэтому нам трудно представить Вселенную только с двумя измерениями. Согласно антропному принципу, мы видим Вселенную такой, потому что только в такой Вселенной мог возникнуть наблюдатель, человек. Другими словами, мы наблюдаем заведомо не произвольную область Вселенной, а ту, особая структура которой сделала её пригодной для возникновения и развития жизни.

Соответственно, во Вселенной встречаются разные значения мировых констант, но мы не можем их наблюдать. Впрочем, по расчётам физика Джеймса Скарджилла (James Scargill) из Калифорнийского университета в Дэвисе, двумерная Вселенная всё-таки возможна.

В частности, Скарджилл рассматривает идею жизни в измерениях 2+1, где +1 —это измерение времени.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js