# How to partition a graph with optimal number of groups?

I have a graph with $$N=12$$ nodes. Some node may not have any edge between them. every edge has a weight. How to find the optimal partitioning of the graph so that total weight in the system is maximised.

Let the weight matrix is given by $$W$$ of size $$Ntimes N$$. The diagonal elements of $$W$$ are ones, therefore, if there is no edge between two nodes, the corresponding element in $$W$$ is 1..

Each partition can have maximum 3 nodes and minimum 1 node. I want to find to optimal number of partitions, and the nodes belonging to each partition.

The x and y coordinates of the nodes are give as

`````` xcord={154.780094065851,   302.747331652902,   348.235746943268,   959.228504576796,   1021.26721027296,   1114.13365936238,   358.208241883160,   181.741156296042,   838.759299985938,   906.502702816486,   662.579285251179,   536.372745335719};

ycord={347.543166449207,   461.536311618993,   261.753095520236,   431.778284592051,   250.920713280060,   432.113192132818,   1044.66583584371,   1044.70069210915,   1135.19457237168,   984.121301679063,   792.153882418914,   708.946190878097};
``````

Also, these are the edges connecting the nodes.

``````Edges={{1,2},{1,3},{1,8},{1,11},{1,12},{2,3},{2,4},{2,7},{2,8},{2,11},{2,12},{3,4},{3,5},{3,11},{3,12},{4,5},{4,6},{4,10},{4,11},{4,12},{5,6},{5,11},{5,12},{6,10},{6,11},{6,12},{7,8},{7,9},{7,10},{7,11},{7,12},{8,9},{8,11},{8,12},{9,10},{9,11},{9,12},{10,11},{10,12},{11,12}};
``````

Let the weights are uniformly distributed as

``````SeedRandom[1];
ew = Round[ RandomReal[1, Length@Edges], .01];
``````

I want to find the partitions that gives the maximum total weights sum.

If there is only one node in a portion, its weight sum is one.

If there are two nodes in a partition, then the weight some is 1+1+weight between the nodes.

If there are three nodes in a partition, then the weight some is 1+1+1+weights among the nodes.