"Записки научных семинаров ПОМИ"
Том 504, стр. 21-46
Преобразования сборного числа 4-регулярного графа
А. Э. Гутерман, E. М. Крейнес, Н. В. Остроухова
Московский гос. университет
им. М. В. Ломоносова, Москва, 119991, Россия,
Московский центр фундаментальной и прикладной
математики, Москва, 119991, Россия,
Московский физико-технический институт,
Долгопрудный, 141701, Россия
guterman@list.ru
Московский гос. униветститет им. М. В. Ломоносова,
Москва, 119991, Россия,
Московский центр фундаментальной и прикладной
математики, Москва, 119991, Россия
elena.kreines@gmail.com
Московский гос. университет им. М. В. Ломоносова,
Москва, 119991, Россия
natosova@gmail.com
- Аннотация:
Простые сборные графы характеризуют процесс рекомбинации ДНК у простейших.
Важными характеристиками этих графов являются сборное число, количество различных гамильтоновых множеств полигональных путей, односторонняя и двусторонняя аддитивность графа. В работе исследуются преобразования простых сборных графов, позволяющие увеличивать сборное число или получать двусторонне аддитивные графы. Определено минимальное число петель, которые необходимо добавить на ребра петельного графа, чтобы увеличить его сборное число на~1.
Библ. -- 7 назв.
- Ключевые слова:сборные графы, 2-слова, сборное число
[assembly graphs, doubly occurrence words, assembly number]
Полный текст(.pdf)