Macavity писал(а):
Среди Ваших статей есть одна о применении графов де Брюна (де Брейна). Прямо в заголовок вынесено "Colored de Bruijn Graphs and the Genome Halving Problem". Они действительно бывают colored или это один из результатов Вашей работы?
Ну графы де Брюна - это сейчас уже некий тип графов, нежели название конкретного графа. Так, в той работе я рассматриваю некий особый класс таких графов, ребра которых раскрашены в три цвета, и демонстрирую их применение в биоинформатике.
Macavity писал(а):
Вашу статью ещё не прочитал, попробую, но боюсь, что тематика мне будет неясна...
На самом деле статья самодостаточная - для ее понимая не придется обращаться к другим источникам. При условии, конечно, что в некоторые (цитируемые) вещи придется поверить на слово.
Macavity писал(а):
Меня интересуют графы де Брюна может посоветуете, что-нибудь почитать? В частности наибольший интерес для меня имеют следующие вопросы.
Ну вот так прямо по графам де Брюна монографий не знаю. Но они часто встречаются в приложениях, и там исследуются нужные свойства. И я не уверен, что они сами по себе представляют интерес.
Macavity писал(а):
1. Существуют алгоритмы построения графов де Брюна, вопрос о сложности этих алгоритмов по отношению к количеству вершин (NP-полные или менее сложные, тогда степень сложности). Существуют ли оценки этой сложности?
2. Использование этих графов в теории кодирования и/или криптографии?
Чтобы ответить на первый вопрос, нужно сначала определить, что такое "построение" и о каких конкретно графах де Брюна идет речь.
На второй вопрос - ответ "да", гугл подскажет конкретные работы.
