Broadcast graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Broadcast graph''' --- граф широковещания. Let us first consider the full-duplex model (See ''Broadcasting problem''.) Let <math>G</math> be a …») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 16:31, 23 октября 2018
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.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.