Аноним

Broadcast graph: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Broadcast graph''' --- граф широковещания. Let us first consider the full-duplex model (See ''Broadcasting problem''.) Let <math>G</math> be a …»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Broadcast graph''' --- граф широковещания.  
'''Broadcast graph''' — ''[[граф широковещания]].''


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


<math>b(G) = \max\{b(v)| \; v \in V(G)\}.</math>
:::::<math>b(G) = \max\{b(v)| \; v \in V(G)\}.</math>


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


Similarly, a '''broadcast digraph''' is defined, using the
Similarly, a '''broadcast digraph''' is defined, using the half-duplex model.
half-duplex model.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.