series-parallel networks problem - Article and Reference from OnPedia.com

Series-parallel Networks Problem

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

Indistinguishable edges

When the edges are indistinguishable, we look for the number of topologically different networks on, say 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=\left\{\begin{matrix} 1, & \mbox{if }n\mbox{ is 1} \\ 2b_n, & \mbox{otherwise}\end{matrix}\right.

b_n

can be found out by enumerating the partitions of

n

. Consider a partition,

\{p_i\}

of n:

\sum_i{ip_i}=n.

Consider the essentially series networks whose components correspond to the partition above. That is the number of components with i edges is

a_i

. The number of such networks can be computed as

\prod_{i}

. Hence

b_n=\sum_{p_i}{\prod_{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. Generating Function for

a_n

b_n

are explained in the external links.''

External links

On-Line Encyclopedia of Integer Sequences

$a_n$ A000084
$b_n$ A000669

* Asymptotic behavior of two-terminal series-parallel networks

Word Browser

peristome
visual audio sensory theater
pauline johnson collegiate & vocational school
nyirtet
i5
eiffel 65 (album)
yos sudarso
imperium (game)
imperium (traveller)
algebraic syntax
list of military units in the warsaw uprising

cleon i
the dream academy
imperium (book)
aleksandr panayotov aleksandrov
aleksandr pavlovich aleksandrov
stanel vi
timeline of asimov's foundation series
tehiya
derecho
ibm p5
vladimir lyakhov

reform school
al tv
kirby's pinball land
viktor savinykh
ow prolog
mike grell
list of notable derecho events
anatoli levchenko
harding university
lifesaving medal
muhammed faris

serpent (constellations)
serpent (instrument)
aleksandr laveykin
serpent (disambiguation)
leonid kizim
live peace in toronto
shawn crawford
vladimir vasyutin
karakoram highway
saint hunger
igor volk

Copyright 2005-2009 OnPedia.com. All Rights Reserved