-4
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ If we know it is connected then count number of edges in the graph. It will be tree iff n-1 edges are there. Otherwise, First check if it is connected. If not clearly not a tree. $\endgroup$
    – Root
    Mar 20, 2020 at 19:12
  • $\begingroup$ @Root how would we check if it is connected through code? $\endgroup$
    – stuckyp
    Mar 20, 2020 at 23:45

1 Answer 1

0
$\begingroup$

I believe the easiest method is to first check if the number of vertices and edges align with $m = n - 1$ (if they don't definitely not a tree). Now we conclude either our graph is a tree or is disconnected but contains a cycle. So either we look for a cycle or look for connectivity, both methods are equivalent. To check for cycles, the most efficient method is to run DFS and check for back-edges, and either DFS or BFS can provide a statement for connectivity (assuming the graph is undirected).

You are looking for something that employs the characteristics of the adjacency matrix itself, however, which I think is much more inefficient since we already have methods that can decipher an adjacency matrix particularly with edge traversals (DFS and BFS). If you don't want to do something with edge traversals with the given adjacency matrix, then you either need to find another linear method of processing it, or you need to take higher powers of the matrix which becomes a cubic time operation.

However, for adjacency matrices of smaller graphs (like your example of order 4), you could find certain patterns that signify the presence of a cycle or if the graph is connected.

Hope this helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.