The problem is to realize or find a graph (i.e. say adjacency matrix) given one fundamental cut-set matrix. I know that this problem is not complete, since we run into the problem of 2-isomorphism, hence uniqueness cannot be guaranteed.
Is there any method by which I can easily realize at least one possible/compatible graph?
This broadly falls under graph realization problem, which had some activity till the late 1980s but seems dead after that. I was also not able to find any comprehensive algorithm to do this task. If anyone can help me out, it would be great. Thanks!
Dear Aravind,
You please check the following link and read the article: http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%2010.PDF
In this document, the relation between reduced incidence matrix, the fundamental cycle matrix, and the fundamental cut-set matrix has been explained (see page 282-283). Using this relation, we can form an idea about the graph concerned.
Dear Sudev,
Many thanks for your reply. I did peruse that book chapter, in fact it was the first reference I tried. This is what it has to say (page 283)
" If either Bf and Cf is given, then Af in general cannot be determined completely"
In the chapter notation, B and C are the cut-set and loop matrices respectively, and A is the incidence matrix. What I want is precisely a method for doing this. The closest solution I was able to find was the following:
Fujishige, S. (1980). An efficient PQ-graph algorithm for solving the graph-realization problem. Journal of Computer and System Sciences, 21(1), 63-86.
However, even this solution is incomplete, and after 1980, there hasn't been any work on this problem to the extent of my knowledge. If you have some algorithm in mind, or have read some relevant papers, please let me know. Thank you again.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs