Перейти к:навигация, поиск

Let us first consider the full-duplex model (See Broadcasting problem.) Let $\,G$ be a graph modeling an interconnection network. We will denote by $\,b(v)$ the broadcast time of $\,v$, that is the time to achieve broadcasting from a vertex $\,v$ of $\,G$ in the network. Moreover, $b(G)$, the broadcast time of $G$, is defined as follows:
$b(G) = \max\{b(v)| \; v \in V(G)\}.$
If we consider a complete graph of order $\,n$, $\,K_{n}$, it is not difficult to see that $b(K_{n}) = \lceil\log_{2}(n)\rceil$. Any graph $G$ such that $b(G) = b(K_{n}) = \lceil\log_{2}(n)\rceil$ is called a broadcast graph. We call a minimum broadcast graph of order $\,n$ any broadcast graph $\,G$ having the minimum number of edges. This number is denoted by $\,B(n)$.