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
- as the number of series-parallel networks on n indistinguishable edges.
- as the number of essentially series networks.
Then
can be found out by enumerating the partitions of .
Consider a partition, of n:
Consider the essentially series networks whose components correspond to the partition above. That is the number of components with i edges is . The number of such networks can be computed as
Hence
where the summation is over all partitions, of n except for the trivial partition consisting of only n.
This gives a recurrence for computing . Now can be computed as above.
Read more about this topic: Series-parallel Networks Problem
Famous quotes containing the word solution:
“The Settlement ... is an experimental effort to aid in the solution of the social and industrial problems which are engendered by the modern conditions of life in a great city. It insists that these problems are not confined to any one portion of the city. It is an attempt to relieve, at the same time, the overaccumulation at one end of society and the destitution at the other ...”
—Jane Addams (1860–1935)
“I herewith commission you to carry out all preparations with regard to ... a total solution of the Jewish question in those territories of Europe which are under German influence.... I furthermore charge you to submit to me as soon as possible a draft showing the ... measures already taken for the execution of the intended final solution of the Jewish question.”
—Hermann Goering (1893–1946)
“Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
—Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)