1
$\begingroup$

I'm currently learning about graphs and I have some questions regarding adjacency matrices. Given an arbitrary adjacency matrix:

enter image description here

Is there any way to tell if that matrix represents a hierarchal graph structure? Obviously in the above case it's not.

Something like:

enter image description here

I know the rows of and i x i adjacency matrix represent the out-degree of ith vertex and columns represent the in-degree of the ith vertex. But is there any way to tell just by looking at the general structure of the adjacency matrix if the graph is hierarchical (At least, for smaller matrices as above) ?

$\endgroup$
  • 2
    $\begingroup$ Welcome to CS.SE! Can you give a self-contained definition of what a "hierarchical graph structure" is? Do you mean a tree (or forest)? $\endgroup$ – D.W. Mar 16 '17 at 16:34
1
$\begingroup$

By definition you can check if a graph is a tree (regardless of its representation) with these facts:

  1. The graph does not have cycles.
  2. It only has a single connected component.

The first condition can be checked with a simple DFS checking if there is a back edge. The connected components can be counted using either DFS or BFS.

Regarding to an adjacency matrix, every tree is a bipartite graph. See this, but keep in mind that proving that a a graph is bipartite does not mean it is a tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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