green_fr (green_fr) wrote,
green_fr
green_fr

Category:

Pour la science № 493 — граф Радо

Статья про совершенно сумасшедший объект в математике :-)

Начинается статья с «универсальных чисел» (я не знаю, как перевести nombre univers) — чисел, десятичная запись которых содержит любое конечное десятичное число. Для простоты цифры записываются после десятичной запятой. Например, постоянная Чемперноуна = 0,1234567891011121314... — это универсальное число.
С универсальными числами связано множество парадоксов: практически любой объект можно представить в виде конечного числа (текст => его побуквенная запись, картинка => попиксельная запись и т.д.), а поскольку универсальное число содержит в себе все конечные числа, то да, в них есть любая когда бы то ни было написанная книга. И ненаписанная тоже. Описание того, что вы будете делать завтра. Фотография вашего пра-пра-прадедушки, несмотря на то, что тогда ещё не было фотоаппаратов. И фотография, где вы рядом с ним. Ну и так далее.
Обычно все эти байки рассказывают про число Пи, но его универсальность пока ещё гипотетическая, она не доказана.

Так вот, универсальных чисел бесконечное количество. А если мы попытаемся перенести вот этот признак универсальности на графы, там будет ровно один универсальный граф — граф Радо.

Сначала, что такое «граф», что такое «равно», и что такое «содержится»?
Графы мы рассматриваем счётные и ненаправленные, то есть как счётный набор вершин (названных или перенумерованных) и счётный набор ненаправленных рёбер между вершинами (ребро [a, b] эквивалентно ребру [b, a]), причём между двумя вершинами не может быть более одного ребра, и ребро не может соединять вершину саму с собой.
Равенство мы будем понимать как изоморфность: то есть, два графа считаются одинаковыми, если можно переименовать / перенумеровать вершины этих графов таким образом, что список вершин и список рёбер у них будет записываться одинаково.
И мы будем считать, что граф A содержится в графе B, если в графе B можно выделить подграф C, включающий часть вершин графа B, а также все рёбра графа B, соединяющие вершины, отобранные для графа C, — и при этом C «равен» A.

Теперь определение графа Радо. Перенумеруем все вершины целыми неотрицательными числами, начиная от 0. Пусть a < b. Между вершинами a и b есть ребро тогда и только тогда, если в двоичной записи числа b a-я цифра не равна нулю (цифры считаются справа налево, начиная с нулевой). Например, 12 записывается как 1100, то есть 12-я вершина связано со 2-й и 3-й, а больше ни с какой вершиной, имеющей меньший номер, не связано.

Совершенно экзотическое определение, но через него крайне легко показать, что этот граф обладает прекрасным свойством расширяемости: для любых двух несвязанных друг с другом подмножеств A и B можно найти вершину X, которая будет связана со всеми вершинами множества A и ни с одной вершиной множества B.
Казалось бы, чем это нам поможет? Но именно через это свойство элементарно показывается, что а) все возможные конечные графы содержатся в графе Радо, назовём это свойство универсальностью; б) все возможные универсальные графы изоморфны графу Радо.

Когда я говорю «элементарно» — это означает, что автор статьи смог привести понятные мне доказательства длиной в несколько строчек. После чего написал параграф в духе «Элементарно, но настолько невероятно, что я несколько раз проверил. И всё равно не до конца верю написанному».

Дальше автор рассказывает о случайных графах: при добавлении каждой новой вершины случайным образом определяется, с кем она будет связана. Бесконечные случайные графы тоже расширяемы, а значит — равняются графу Радо. В этом месте автор цитирует Эрдёша, сожалевшего, что этим фактом закрывается тема бесконечных случайных графов. Это единственная известная ему область, в которой переход от конечного количества элементов к бесконечному радикально упрощает задачу.

А под конец автор показывает удивительную живучесть графа Радо. Если у него убрать конечное число вершин или рёбер, то получившийся граф будет изоморфен графу Радо. Если граф Радо разрезать на две несвязанные друг с другом части, то одна из них будет изоморфна графу Радо.

Отличный объект!


Порадовала библиография статьи. Помимо исторически важных статей, автор цитирует Википедию. Само по себе это уже давно нормально, но до сих пор я видел цитирование как сайта, то есть, с указанием адреса страницы. Здесь же Википедия, наконец-то, цитируется как энциклопедия: «Википедия, „Граф Радо“, 2018».
Tags: pour la science
Subscribe

  • Территориальный спор по поводу Монблана

    Читая очередной Le Monde, с удивлением узнал, что у Франции с Италией есть территориальный спор по поводу Монблана. История просто прекрасная:…

  • Горы по пути домой

    По пути из Lignano завезли ребёнка в лагерь. Вот за что ещё люблю Францию — за какое-то немыслимое изобилие детских лагерей. В этом году у них,…

  • Beaufortain

    Анечка достаточно оперативно разобрала фотографии с нашего неожиданного похода в горы неделю назад! Действительно,…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments