Constructing Quotient Graphs

[BigBaz]

If we have a graph G=(N,E), where N is the set of nodes, and E is the
set of edges. If we partition N into k parts (partition 1, 2,3...k).
And this partition is given by an array, with the node number as the
index. For example, C[x]=a means node x is belongs to partition a.

We define the "Quotient graph" with respect to the above partition as:

A simple graph with no multiple edges. With the set of nodes 1 to K,
and the set of edges (i,j) such that for each each edge (u,v) in E
(the original set of edges in G), there is C=i and C[v]=j.

In English, the quotient graph is a graph with all the K partition
numbers as the edges.

How can I give an algorithm to construct a Quotient Graph from G, with
running time O(size(N)+size(E)).

 

[Kai-Uwe Bux]

If we have a graph G=(N,E), where N is the set of nodes, and E is the
set of edges. If we partition N into k parts (partition 1, 2,3...k).
And this partition is given by an array, with the node number as the
index. For example, C[x]=a means node x is belongs to partition a.

We define the "Quotient graph" with respect to the above partition as:

A simple graph with no multiple edges. With the set of nodes 1 to K,
and the set of edges (i,j) such that for each each edge (u,v) in E
(the original set of edges in G), there is C=i and C[v]=j.

In English, the quotient graph is a graph with all the K partition
numbers as the edges.

How can I give an algorithm to construct a Quotient Graph from G, with
running time O(size(N)+size(E)).

a) This is off-topic since it is unrelated to C++.

b) It also smells like homework.

c) When posting to a more topical group, you also might want to specify the
data structure for the graph. If the edges are described as an incidence
matrix, then the input is a size(N) x size(N) matrix and the result is a
size(K) x size(K) matrix. So input and output alone will be worse than
O(size(N)+size(E)).

d) A book on graph algorithms might be a good start.


Best

Kai-Uwe Bux