Graph partition

Given a graph G=(V, E), where V is the set of vertex and E the set of edges that determines the connectivity between the nodes. Both vertex and edges can be weighted, where |v| is the weight of a vertex v, and |e| is the weight of edge e. Then, the graph partitioning problem consists on dividing G into k disjoint partitions. The goal is minimize the number of cuts in the edges of the partition, and on the other hand reduce the imbalance of the weight of the subdomains. The weight of a subdomain is the sum of the weights of the vertex allocated in it. All the graphs listed later have |v|=1 for all v in V and |e|=1 for all e in E.