Kai-Uwe Bux
11/17/2008 10:36:00 PM
BigBaz wrote:
> 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[u]=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