Broadcast graph

Материал из WEGA
Версия от 14:16, 24 февраля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Broadcast graph''' --- граф широковещания. Let us first consider the full-duplex model (See ''Broadcasting problem''.) Let <math>G</math> be a …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

Let us first consider the full-duplex model (See Broadcasting problem.) Let [math]\displaystyle{ G }[/math] be a graph modeling an interconnection network. We will denote by [math]\displaystyle{ b(v) }[/math] the broadcast time of [math]\displaystyle{ v }[/math], that is the time to achieve broadcasting from a vertex [math]\displaystyle{ v }[/math] of [math]\displaystyle{ G }[/math] in the network. Moreover, [math]\displaystyle{ b(G) }[/math], the broadcast time of [math]\displaystyle{ G }[/math], is defined as follows:

[math]\displaystyle{ b(G) = \max\{b(v)| \; v \in V(G)\}. }[/math]

If we consider a complete graph of order [math]\displaystyle{ n }[/math], [math]\displaystyle{ K_{n} }[/math], it is not difficult to see that [math]\displaystyle{ b(K_{n}) = \lceil\log_{2}(n)\rceil }[/math]. Any graph [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ b(G) = b(K_{n}) = \lceil\log_{2}(n)\rceil }[/math] is called a broadcast graph. We call a minimum broadcast graph of order [math]\displaystyle{ n }[/math] any broadcast graph [math]\displaystyle{ G }[/math] having the minimum number of edges. This number is denoted by [math]\displaystyle{ B(n) }[/math].

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