Distinguish Graph from Tree using Adjacency Matrix

1
votes

Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle).

For example, given the adjacency matrix:

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

This is not a tree since there is a cycle between Vertex 1, Vertex 2 and Vertex 4.

Whereas given the adjacency matrix:

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

This is a tree since there is no cycle.

One way to approach this is to perform a BFS but I think there might be a visual difference between an adjacency matrix of a graph and of a tree.

Any help would be appreciated!

1
algorithmgraphtreegraph-theorytraversal
This looks like the matrix of an undirected graph. For an undirected graph, the entries on the main diagonal are always all 0, and the other entries are mirrored across the main diagonal. Taking that into consideration, the two matrices can be simplified to this and this (without any loss of information). With that in mind, I conjecture that there won't be an obvious visual difference when the matrix is larger, and the connections are not so simple. - user3386109
There's no obvious visual characteristic. Pick a row with only a single 1. That's a leaf. Then search breadth or depth first maintaining a set of already-visited vertices. If you encounter the same node more than once, it's not a tree. Note that the matrix might not represent a single component. In that case you need an outer loop that searches for the next leaf. - Gene

1 Answers

1
votes

You can use the fact that a tree with N nodes has exactly N-1 edges. Any adjacency matrix representing a tree will have exactly 2(N-1) 1's, since each edge sets two bits in the matrix (with no 1's on the diagonal, since trees have no self-edges). Furthermore, since the tree must be connected, there must be at least one 1 per row and column. If you're allowed to make the assumption of symmetry across the diagonal (i.e. it's a valid adjacency matrix) then it suffices to check at least one 1 per row.

However, these are only preliminary checks and I don't believe there's an easy way to actually show connectivity without a BFS or something similar.