Оптимальный алгоритм преобразования ациклического орграфа в сильносвязный | Прикладная дискретная математика. 2021. № 54. DOI: 10.17223/20710410/54/4

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