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.