Некоторые методы проверки графа на связность:

• Матричный алгоритм. 2 Матрицу графа последовательно возводят в степень k, элементы получаемых матриц описывают для соответствующих пар вершин число связывающих их цепей «длины» k, которая измеряется числом рёбер. 2 Для связного графа матрица не должна содержать нулевых элементов. 2 Если это не так, то граф не является связным. 2
• Редукционный алгоритм. 2 Все единицы, не лежащие на главной диагонали, заменяют на –1. 2 Затем при отбрасывании любой вершины получают матрицу В[n–1]. 2 Вычисляя значение определителя матрицы В[n–1], определяют, является ли граф связным или нет. 2 Если detВ[n-1] > 0, то граф является связным, если detВ[n-1] ≤ 0, то граф не является связным. 2
• Поиск в глубину. 3 Для проверки неориентированного графа на связность запускают поиск в глубину из любой вершины и после этого проверяют, что побывали во всех вершинах. 3