Wikipedia:Reference desk/Archives/Mathematics/2013 December 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 2

Creating Regions from a complete graph with weighted edges.

I'm looking for information on creating Regions on a complete graph G with weighted edges. Regions are mutually exclusive subsets of vertices (R1-RN) covering the entire graph and the cost of a set of Regions is the sum of the weighted edges where both vertices on an edge are in the same Region and I'm looking to minimize cost. I'm probably using the wrong terminology, can someone give me the right terminology and help me find any reference works or programs to calculated them? — Preceding unsigned comment added by Naraht (talk • contribs)

From your definition, the cost of a region with only a single node in it would appear to be 0 - so what prevents you minimising cost by dividing the graph into single node regions ? Is a region perhaps constrained to include at least two nodes ? Gandalf61 (talk) 11:08, 2 December 2013 (UTC)

The number of Regions is constrained. I might have 60 vertices and need to split into only 5 regions.Naraht (talk) 04:24, 3 December 2013 (UTC)

This looks like a cluster analysis problem with your regions being the clusters. While exhaustive search is typically prohibitive for large numbers of vertices and clusters, there are approximate clustering algorithms to find possible acceptable solutions. A greedy algorithm like agglomerative hierarchical clustering could be useful here, where one adds vertices one at a time to existing clusters to build up a solution. Start with 5 random points for the 5 clusters and at each stage, pick the (vertex, cluster) pair that increases the total cost the least amount, untill all vertices are assigned clusters. --Mark viking (talk) 22:19, 3 December 2013 (UTC)