CODEWITHSUNDEEP
algorithmgraphtreegraph-theorytraversal
utkm
utkm

Reputation: 53

Distinguish Graph from Tree using Adjacency Matrix

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!

Upvotes: 2

Views: 3933

Answers (1)

aeternalis1
aeternalis1

Reputation: 675

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.

Upvotes: 1

Related Questions