Rahul Sharma (Editor)

Series parallel networks problem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In combinatorial mathematics, the series-parallel networks problem asks for the number of series-parallel networks that can be formed using a given number of edges. The edges can be distinguishable or indistinguishable.

Contents

Indistinguishable edges

When the edges are indistinguishable, we look for the number of topologically different networks on n edges.

Solution

The idea is to break-down the problem by classifying the networks as essentially series and essentially parallel networks.

  • An essentially series network is a network which can be broken down into two or more subnetworks in series.
  • An essentially parallel network is a network which can be broken down into two or more subnetworks in parallel.

    • By the duality of networks, it can be proved that the number of essentially series networks is equal to the number of essentially parallel networks. Thus for all n > 1, the number of networks in n edges is twice the number of essentially series networks. For n = 1, the number of networks is 1.

    Define

  • a n as the number of series-parallel networks on n indistinguishable edges.
  • b n as the number of essentially series networks.

    • Then

    a n = { 1 , if  n  is 1 2 b n , otherwise

    b n can be found out by enumerating the partitions of n .

    Consider a partition, { p i } of n:

    ∑ i i p i = n .

    Consider the essentially series networks whose components correspond to the partition above. That is the number of components with i edges is p i . The number of such networks can be computed as

    ∏ i ( b i + p i − 1 p i ) .

    Hence

    b n = ∑ p i ∏ i ( b i + p i − 1 p i )

    where the summation is over all partitions, p i of n except for the trivial partition consisting of only n.

    This gives a recurrence for computing b n . Now a n can be computed as above.

    [TODO: Generating function for a n and b n are explained in the external links.]

    References

    Series-parallel networks problem Wikipedia
    (Text) CC BY-SA


    Similar Topics