2. A complex software system is usually decomposed into simpler sub-systems called modules. The design for modularity can be considered as a graph partition problem, i.e. we organize the components of the software system into modules, such that the within- module calls can be more coherent, while the between-module calls can be less coupled. We can then represent a system as a graph, with nodes in the graph as components in the system, and links between nodes as calling relations. Given an undirected weighted graph G with six components (1,2,3,4,5,6), each component represented by a node in graph G. Then a link between node i and node j represents there is a call relation between components i and j. Also there are different weights wij over calls between i andj When we decompose the original system into two modules, i is equivalent to seeking bi- partition G into two disjoint subgraphs G1 and G2 by maximizing the within-group calls and minimizing the between-group calls. Questions: (1) How to define a good "cut" on the graph into two subgraphs to ensure the minimization of the between-group calls? Give your formula and justify your answer (2) Give a bi-partition cut to the graph above, so that it can achieve the maximized within-group calls and minimized between-group calls. What are the two modules composed of? (3) Generally a good bi-partition of the graph G(V, E) is usually balanced over two subgraphs; for example, in software engineering you may want the system components to be divided in two modules, so that the coherence of two modules should be as even as possible. Give an example of a system where the formula in (1) will not achievea e a good composition of two modules. Wi5 (4) Can you think of a good bi-partition cut to simultaneously encourage the minimization of the between-module calls and maximization of the within-module calls, yet achieving balanced coherence of the two modules? Give your formula and justify your answer (Hint You may refer to the volume of a subgraph G, defined as the total weight of edges within G', ie, vol(G W The volume can be used to measure the within-module coherence. This is an open answer question.) w12-3 W56 = W452 2 6 4 W23 3 W46 W34