Consider the Omega network and Butterfly network from $p$ nodes in the leftmost column

to $p$ nodes in the rightmost column for some $p=2^{{?}^{{?}^{?}}}k.$ The Omega network is defined in

Chapter $2$ of the text book such that $Si$ is connected to element $Sj$ if $j=2$i for

$0i\frac{p}{2}-1,$ or $j=2i+1-p$ for $\frac{p}{2}ip-1.$ See Chapter $2$ in text book for its

definition.

The Butterfly network is an interconnection network composed of $logp$

levels $($as the omega network$).$ In a Butterfly network, each switching node $i$ at a level $l$ is

connected to the identically numbered element at level $l+1$ and to a switching node

whose number differs from itself only at the $l$ th most significant bit. Therefore, switching

node $Si$ is connected to element $Sj$ at level $l$ if $j=i$ or $jj=io+2^{(logp)-l}.$

Prove that for each node $Si$ in the leftmost column and a node $Si$ in the rightmost column,

there is a path from $Si$ to $Si$ in the Omega network.

Prove that for each node $Si$ in the leftmost and a node $Si$ in the rightmost, there is a path from

Si to Si in the Butterfly network.