Distin guish График из дерева с использованием матрицы смежности

Question

Учитывая матрицу смежности, есть ли способ определить, будет ли граф деревом или графом (существует ли цикл).

Например, учитывая матрицу смежности:

0 1 0 1
1 0 0 1
0 0 0 1
1 1 1 0

Это не дерево, поскольку существует цикл между вершиной 1, вершиной 2 и вершиной 4.

Принимая во внимание, что с учетом матрицы смежности:

0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0

Это дерево, поскольку цикла нет.

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

Любая помощь будет оценена!

Answer 1

Вы можете использовать тот факт, что дерево с N узлами имеет ровно N-1 ребер. Любая матрица смежности, представляющая дерево, будет иметь ровно 2 (N-1) 1, поскольку каждое ребро устанавливает два бита в матрице (без 1 на диагонали, поскольку деревья не имеют собственных ребер). Кроме того, так как дерево должно быть связано, должен быть по крайней мере один 1 на строку и столбец. Если вам разрешено сделать предположение о симметрии по диагонали (т. Е. Это допустимая матрица смежности), то достаточно проверить хотя бы одну единицу на строку.

Однако это только предварительные проверки, и я не буду не верю, что есть простой способ показать соединение без BFS или чего-то подобного.