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

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

Для двудольного орграфа G , в котором все дуги выходят из первой доли во вторую, решена задача нахождения минимального набора дуг, дополнение которых преобразует его в сильносвязный орграф. Доказано, что минимальное число дополнительных дуг, преобразующих двудольный орграф G в сильносвязный, равно максимуму из числа вершин первой и второй долей. Построен алгоритм определения минимального набора дополнительных дуг, преобразующих данный орграф в сильносвязный. Этот алгоритм основан на выделении минимального рёберного покрытия, как совокупности несвязанных между собой звезд в орграфе G, и на построении дуг, соединяющих эти звезды. Полученный результат использован для нахождения минимального набора дуг, преобразующих произвольный ациклический орграф в сильносвязный орграф путём выделения рёбер, соединяющих звёзды в минимальном рёберном покрытии. Данная задача возникла при анализе биотехнологических решений, повышающих стабильность функционирования белковых сетей за счёт введения в них обратных связей.

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

Связанные документы (рекомендация CORE)

Новости проекта

Новости

Партнеры

Индексация