График Де Брёйна

В теории графов , - мерный Де Бреен граф из символов является ориентированным графом , представляющий перекрытие между последовательностями символов. Он имеет вершины , состоящие из всевозможных последовательностей длины данных символов; один и тот же символ может появляться несколько раз в последовательности. Для набора символов набор вершин:${\ displaystyle n}$${\ displaystyle m}$${\ Displaystyle м ^ {п}}$ ${\ displaystyle n}$${\ displaystyle m}$${\ Displaystyle S = \ {s_ {1}, \ dots, s_ {m} \}}$

$${\ displaystyle V = S ^ {n} = \ {(s_ {1}, \ dots, s_ {1}, s_ {1}), (s_ {1}, \ dots, s_ {1}, s_ {2) }), \ dots, (s_ {1}, \ dots, s_ {1}, s_ {m}), (s_ {1}, \ dots, s_ {2}, s_ {1}), \ dots, ( s_ {m}, \ dots, s_ {m}, s_ {m}) \}.}.$$

Если одну из вершин можно выразить как другую вершину, сдвинув все ее символы на одну позицию влево и добавив новый символ в конце этой вершины, то последняя имеет направленное ребро к первой вершине. Таким образом, набор дуг (то есть направленных ребер) равен

$${\displaystyle E=\{((t_{1},t_{2},\dots ,t_{n}),(t_{2},\dots ,t_{n},s_{j})):t_{i}\in S,1\leq i\leq n,1\leq j\leq m\}.}$$

Хотя графы Де Брёйна названы в честь Николааса Говера де Брёйна , они были независимо открыты как Де Брёйном ^{[1], так} и Ай Дж. Гудом . ^[2] Намного раньше Камилла Флай Сент-Мари ^[3] неявно использовала их свойства.

Свойства [ править ]

• Если тогда условие для любых двух вершин, образующих ребро, выполняется вакуумно, и, следовательно, все вершины соединены, образуя сумму ребер.${\displaystyle n=1}$${\displaystyle m^{2}}$
• Каждая вершина имеет ровно входящие и исходящие ребра.${\displaystyle m}$${\displaystyle m}$
• Каждый -мерный De Бройн граф является линия орграфом из - мерной Де Брейна графы с тем же набором символов. ^[4]${\displaystyle n}$${\displaystyle (n-1)}$
• Каждый граф Де Брейна эйлеров и гамильтонов . Циклы Эйлера и гамильтоновы циклы этих графов (эквивалентные друг другу посредством построения линейного графа) являются последовательностями Де Брёйна .

Построение линейного графа трех наименьших двоичных графов Де Брёйна изображено ниже. Как видно на иллюстрации, каждая вершина -мерного графа Де Брёйна соответствует ребру -мерного графа Де Брёйна, а каждое ребро в -мерном графе Де Брёйна соответствует двухреберному пути в -мерном графе Де Брёйна. График Де Брёйна.${\displaystyle n}$${\displaystyle (n-1)}$${\displaystyle n}$${\displaystyle (n-1)}$

Динамические системы [ править ]

Бинарные графы Де Брёйна можно нарисовать таким образом, чтобы они напоминали объекты из теории динамических систем , такие как аттрактор Лоренца :

Аттрактор Лоренца

Эту аналогию можно сделать строгой: -мерный -символ граф Де Брёйна является моделью отображения Бернулли.${\displaystyle n}$${\displaystyle m}$

$${\displaystyle x\mapsto mx\ {\bmod {\ }}1.}$$

Карта Бернулли (также называемый 2x моды 1 карты для ) является эргодично динамической системой, которая может быть понята как единый сдвиг из м -адического числа . ^[5] Траектория этой динамической системы соответствует слоям в графе Де Брейно, где соответствие задается путем отображения каждого вещественного в интервале до вершины , соответствующей первых цифры в базе - представление . Эквивалентно, блуждания в графе Де Брёйна соответствуют траекториям одностороннего поддвига конечного типа .${\displaystyle m=2}$${\displaystyle x}$${\displaystyle [0,1)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle x}$

Ориентированные графы из двух B  (2, 3) де Брейна последовательностей и B  (2, 4) последовательности. В B (2,3). каждая вершина посещается один раз, тогда как в B (2,4) каждое ребро обходится один раз.

Вложения, похожие на это, можно использовать, чтобы показать, что двоичные графы Де Брёйна имеют очередь номер 2 ^[6] и что они имеют толщину книги не более 5. ^[7]

Использует [ редактировать ]

• Некоторые топологии грид-сети представляют собой графы Де Брейна.
• Распределенная хэш - таблица протокола Koorde использует граф Де Брейна.
• В биоинформатике графики Де Брейна используются для сборки de novo считываний секвенирования в геном . ^{[8] [9] [10] [11] [12]}

См. Также [ править ]

• Тор де Брёйна
• Граф Хэмминга
• Граф Каутца

Ссылки [ править ]

Внешние ссылки [ править ]

• Вайстейн, Эрик В. «График Де Брейна» . MathWorld .
• Учебное пособие по использованию графов Де Брейна в биоинформатике от Homolog.us