Broadcast graph

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

Broadcast graphграф широковещания.

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).

Similarly, a broadcast digraph is defined, using the half-duplex model.


  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.