Бурятского государственного университета
имени Доржи Банзарова
АвторизацияРУСENG

Вестник БГУ. Математика, информатика

Библиографическое описание:
Цициашвили Г. Ш.
,
Осипова М. А.
АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ОРИЕНТИРОВАННОГО ГРАФА В АЦИКЛИЧЕСКИЙ // Вестник БГУ. Математика, информатика. - 2019. №1. . - С. 13-21.
Заглавие:
АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ОРИЕНТИРОВАННОГО ГРАФА В АЦИКЛИЧЕСКИЙ
Финансирование:
Коды:
DOI: 10.18101/2304-5728-2019-1-13-21УДК: 519.174.5, 519.178
Аннотация:
Совместно с экспертами в разных областях знаний авторами статьи за последние пять лет был решен ряд актуальных задач. Используя элементы теории графов, были построены оригинальные экономичные алгоритмы для исследования рассматриваемых моделей и протестированы на реальных данных. Работа является продолжением исследований в этом направлении и задача, решаемая в ней, поставлена специалистами в области биоинженерии.
На первом этапе в орграфе была проведена факторизация по отношению циклической эквивалентности, и в каждом кластере были выделены входные и выходные вершины (ребер извне и вовне), применяя ранее построенный авторами работы экономичный алгоритм. На втором шаге, используя алгоритм фронта волны, каждый кластер был заменен на его ациклический подграф, соединяющий входные вершины с выходными путями минимальной длины. Да- лее исходный орграф был заменен на ациклический орграф, в котором нет обратных связей, связывающий входные и выходные вершины кластеров.
Ключевые слова:
орграф; циклическая эквивалентность; кластер; частичный порядок; обратная связь; ациклический граф; алгоритм фронта волны; вход- ные вершины; выходные вершины; путь в графе.
Список литературы:
Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Алгоритмы кластеризации графов // Вестник Воронежского государственного университета. Сер.: Физика и математика. 2016. № 1. С. 145–149.

Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S. Hierarchical Classification of Directed Graph Nodes and Application of Protein networks // Biostat. Biometrics Open Acc. J. 2017. V. 1, iss. 4. P. 555–567. DOI: 10.19080/BBOAJ.2017.01.555567.

Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S. Hierarchical classification of directed graph with cyclically equivalent nodes // Applied Mathematical Sciences. 2016. V. 10, No. 51. P. 2529–2536.

Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S., Osipova M. A., Kharchenko Yu. N. Analysis of Hubs Loads in Biological Networks // Reliability: Theory and Ap- plications. 2014. V. 9, No. 2. P. 7–10.

Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S., Osipova M. A., Kharchenko Yu. N. Construcion of subgraph from graph shortest way // Applied Mathematical Sci- ences. 2015. V. 9, No. 79. P. 3911–3916.

Tsitsiashvili G., Bulgakov V., Losev A. Replacement of Directed Graph by Acyclic Directed Graph and Its Application in Biostatistics// Journal of Biometrics & Biostatistics. 2018. V. 9, No. 1. P. 390. DOI: 10.4172/2155-6180.1000390