# Graph reduction to complete subgraphs

This topic is 3212 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
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!

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by alvaroI 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?

##### Share on other sites
Quote:
Original post by Buttacup
Quote:
 Original post by alvaroI 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.

##### Share on other sites
Quote:
 Original post by ButtacupCan 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."

##### Share on other sites
Quote:
Original post by Emergent
Quote:
 Original post by ButtacupCan 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

Canonical form of a matrix, for planarity testing <=== ahhhhhh

[Edited by - Buttacup on February 25, 2010 11:47:07 AM]

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633682
• Total Posts
3013314
×