V Всероссийская научная конференция «Омские научные чтения» - ● Математика

Решение задач о связности на графах с помощью возмущений элементов их матриц смежности

Пролубников А. В.

Аннотация

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

Комментарии

Комментарии отсутствуют

Вопросы по докладу

Вопросы отсутствуют