词条 | Series-parallel networks problem |
释义 |
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. Indistinguishable edgesWhen the edges are indistinguishable, we look for the number of topologically different networks on n edges. SolutionThe idea is to break-down the problem by classifying the networks as essentially series and essentially parallel networks.
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
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. [TODO: Generating function for and are explained in the external links.] External links
1 : Graph enumeration |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。