Graph reduction to complete subgraphs
Author
Is there a way to perform repeated reduction on a Graph G->G'->G''...to the nth degree such that only strongly connected / complete subgraphs remain?
I can not answer your question, I am now interested though after having looked it up. This seems to have implications in how functional programming, such as Haskel, is implemented as is described by Wiki Graph Reduction! I can not find reference in my reference text but I probably have to look for more specific subjects. I can now add lazy evaluation to my list of needs to be researched; functional programming seems rather novel. May I ask why you are looking and what you are looking to do? If you don't mind!
I think this should do:
* Pick the node with the smallest degree.
* Remove it and all the edges that touch it.
* Rinse, repeat.
In case you are not familiar with the term, the degree of a node is the number of edges that touch it.
* Pick the node with the smallest degree.
* Remove it and all the edges that touch it.
* Rinse, repeat.
In case you are not familiar with the term, the degree of a node is the number of edges that touch it.
Quote:Original post by alvaro
I think this should do:
* Pick the node with the smallest degree.
* Remove it and all the edges that touch it.
* Rinse, repeat.
In case you are not familiar with the term, the degree of a node is the number of edges that touch it.
Can you repeat that in Matrix?
Quote:Original post by ButtacupQuote:Original post by alvaro
I think this should do:
* Pick the node with the smallest degree.
* Remove it and all the edges that touch it.
* Rinse, repeat.
In case you are not familiar with the term, the degree of a node is the number of edges that touch it.
Can you repeat that in Matrix?
I don't understand. I didn't understand your previous post either, so I limited myself to answering the original question.
Quote:Original post by Buttacup
Can you repeat that in Matrix?
Ummmm? You mean this?:
I have an nxn adjacency matrix A. I multiply it by a vector of all ones. This gives me a vector of node degrees. I find which element of this vector is smallest -- say it's the k-th one. Then I delete the kth row and column of the adjacency matrix; this gives me a new (n-1)x(n-1) adjacency matrix.
Granted, I haven't thought at all about whether this algorithm works; all I did was "translate."
Quote:Original post by EmergentQuote:Original post by Buttacup
Can you repeat that in Matrix?
Ummmm? You mean this?:
I have an nxn adjacency matrix A. I multiply it by a vector of all ones. This gives me a vector of node degrees. I find which element of this vector is smallest -- say it's the k-th one. Then I delete the kth row and column of the adjacency matrix; this gives me a new (n-1)x(n-1) adjacency matrix.
Granted, I haven't thought at all about whether this algorithm works; all I did was "translate."
Nice, I will look that over this is pretty new to me!
I think this is where I'm headed. I'm also seeing some answers here to a question I posted in a previous thread elsewhere on how one would formulate a set of algorithms to solve a Chromatic Graph problem such as Sudoku! It would still be nice to know what the original poster was up to :D
[edit]
Canonical form of a matrix, for planarity testing <=== ahhhhhh
[Edited by - Buttacup on February 25, 2010 11:47:07 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
