Cut-set matrix is defined by kij, i=1..(n-1), j=1..m, where n=number of vertices and m=number of arcs of a directed graph with kij=+1 if the i-th cut-set includes the j-th arch with the same orientation as the branch of this set, kij=-1 if the i-th cut-set includes the j-th arch with the opposite orientation as the branch of this set and 0 otherwise.
Thanks for your response, Peter. I am not aware if there is such question have been posted in Research Gate (the search on such question does not produce anything).
I know how to get the cut sets manually from the network by finding the (minimal) proper subset of nodes that when removed divides a graph into two disconnected halves but my question is more about "efficient ways on how to get cut-set matrix from adjacency matrix" such that we can do that kind of transformation automatically using computer rather than manual checking on the network graph. Do you know if any of such algorithm exist and if the answer is yes (I need a reference), what is the algorithm efficiency in term of computational time and space? This is more of searching for a research question on how to improve such algorithm.
Max flow min cut of Ford-Fulkerson only provides the optimum cut set, not the cut-set matrix.
Cut set matrix consists of multiple cut sets, not only the minimum one.
As long as I know this matrix was proposed by D.F. Robinson and L. R. Foulds in 1980's in their book on Digraphs: theory and techniques.
You are right that the current algorithm is to try every possible cut sets. Having a large network (in term of number of nodes and arcs), more efficient algorithm is necessary. Any thought?
I think you are getting closer to understand this problem. Yes, I am asking is there any better algorithm than exhaustive search to produce cut-set matrix.
I have put the definition above. Here I repeat again: Cut-set matrix is defined by kij, i=1..(n-1), j=1..m, where n=number of vertices and m=number of arcs of a directed graph with kij=+1 if the i-th cut-set includes the j-th arch with the same orientation as the branch of this set, kij=-1 if the i-th cut-set includes the j-th arch with the opposite orientation as the branch of this set and 0 otherwise.
In simple term, as you may have known, a cut is a partition of the nodes of a graph into two unconnected sub-graphs that are joined by at least one arc. A cut-set is a set of arcs whose end nodes are in different subsets of the partition. A cut-set matrix is a matrix that indicates a cut-set on each row and arc of the directed graph on each column.
I am more interested in cut space rather than in min-cut-set (i.e. max flow) or max cut set.
The minimal cut sets of a graph are known as cocircuits in matroid theory. Because graphic matroids are regular, these cocircuits are obtained from the support-minimal {-1,0,1}-vectors in the real cut space (i.e. the rowspace of the signed vertex-edge incidence matrix N) by forgetting about signs. The real cut space is also spanned by the rows of the Laplacian of the graph which is the symmetric square matrix L = D - A, where A is the adjacency matrix and D is the diagonal matrix with D(i,i) = degree of vertex i. So checking the literature for algorithms computing cocircuits of matroids in general (or for regular matroids, or for graphical matroids) is a good place to start.
Thanks. Do you have any recommendation on easy to understand books on Matroid?
Oxley's "Matroid Theory" is a good reference and Chapters 1 and 5 are good springboards into the general theory from the graph theory viewpoint.
i'm also waiting for same type of algorithm for my work. but i don't want matrix but only all possible cut sets
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs