Modular Decomposition - Modular Quotients and Factors

Modular Quotients and Factors

If and are disjoint modules, then it is easy to see that either every member of is a neighbor of every element of, or no member of is adjacent to any member of . Thus, the relationship between two disjoint modules is either adjacent or nonadjacent. No relationship intermediate between these two extremes can exist.

Because of this, modular partitions of where each partition class is a module are of particular interest. Suppose is a modular partition. Since the partition classes are disjoint, their adjacencies constitute a new graph, a quotient graph, whose vertices are the members of . That is, each vertex of is a module of G, and the adjacencies of these modules are the edges of .

In the figure below, vertex 1, vertices 2 through 4, vertex 5, vertices 6 and 7, and vertices 8 through 11 are a modular partition. In the upper right diagram, the edges between these sets depict the quotient given by this partition, while the edges internal to the sets depict the corresponding factors.

The partitions {V} and are the trivial modular partitions. is just the one-vertex graph, while = G. Suppose is a nontrivial module. Then and the one-elements subsets of are a nontrivial modular partition of . Thus, the existence of any nontrivial modules implies the existence of nontrivial modular partitions. In general, many or all members of can be nontrivial modules.

If P is a nontrivial modular partition, then G/P is a compact representation of all the edges that have endpoints in different partition classes of P. For each partition class X in P, the subgraph G induced by X is called a factor and gives a representation of all edges with both endpoints in X. Therefore, the edges of G can be reconstructed given only the quotient graph G/P and its factors. The term prime graph comes from the fact that a prime graph has only trivial quotients and factors.

When G is a factor of a modular quotient G/P, it is possible that G can be recursively decomposed into factors and quotients. Each level of the recursion gives rise to a quotient. As a base case, the graph has only one vertex. Collectively, G can be reconstructed inductively by reconstructing the factors from the bottom up, inverting the steps of the decomposition by combining factors with the quotient at each level.

In the figure below, such a recursive decomposition is represented by a tree that depicts one way of recursively decomposing factors of an initial modular partition into smaller modular partitions.

A way to recursively decompose a graph into factors and quotients may not be unique. (For example, all subsets of the vertices of a complete graph are modules, which means that there are many different ways of decomposing it recursively.) Some ways may be more useful than others.