Алгоритм преобразования ориентированного графа в ациклический

Автор: Цициашвили Гурами Шалвович, Осипова Марина Анатольевна

Журнал: Вестник Бурятского государственного университета. Математика, информатика @vestnik-bsu-maths

Рубрика: Дискретная математика

Статья в выпуске: 1, 2019 года.

Бесплатный доступ

Совместно с экспертами в разных областях знаний авторами статьи за последние пять лет был решен ряд актуальных задач. Используя элементы теории графов, были построены оригинальные экономичные алгоритмы для исследования рассматриваемых моделей и протестированы на реальных данных. Работа является продолжением исследований в этом направлении и задача, решаемая в ней, поставлена специалистами в области биоинженерии. На первом этапе в орграфе была проведена факторизация по отношению циклической эквивалентности, и в каждом кластере были выделены входные и выходные вершины (ребер извне и вовне), применяя ранее построенный авторами работы экономичный алгоритм. На втором шаге, используя алгоритм фронта волны, каждый кластер был заменен на его ациклический подграф, соединяющий входные вершины с выходными путями минимальной длины. Далее исходный орграф был заменен на ациклический орграф, в котором нет обратных связей, связывающий входные и выходные вершины кластеров.

Еще

Орграф, циклическая эквивалентность, кластер, частичный порядок, обратная связь, ациклический граф, алгоритм фронта волны, входные вершины, выходные вершины, путь в графе

Короткий адрес: https://sciup.org/148308923

IDR: 148308923   |   DOI: 10.18101/2304-5728-2019-1-13-21

Список литературы Алгоритм преобразования ориентированного графа в ациклический

  • Цициашвили Г. Ш., Осипова М. А., Лосев А. С. Алгоритмы кластеризации графов // Вестник Воронежского государственного университета. Сер.: Физика и математика. 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 ofdirected 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 Applications. 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 Sciences. 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
Еще
Статья научная