Аноним

Ball number: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Ball number''' --- шаровое число (графа). By a family of solid balls in <math>R^{3}</math>, we mean a family of balls no two of which penetrate…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Ball number''' --- шаровое число (графа).  
'''Ball number''' — ''[[шаровое число (графа)]].''


By a family of solid balls in <math>R^{3}</math>, we mean a family of balls no
By a family of solid balls in <math>\,R^{3}</math>, we mean a family of balls no
two of which penetrate each other. A chain is a finite sequence of
two of which penetrate each other. A chain is a finite sequence of
solid balls <math>b_{1}, b_{2}, \ldots, b_{n}</math> in which each consecutive
solid balls <math>b_{1}, b_{2}, \ldots, b_{n}</math> in which each consecutive
pair of balls is tangent. The two balls <math>b_{1}, b_{n}</math> are called the
pair of balls is tangent. The two balls <math>\,b_{1}, b_{n}</math> are called the
end balls of the chain.
end balls of the [[chain]].


Let <math>a_{1}, a_{2}</math> be two solid balls. If an end of a chain is tangent
Let <math>\,a_{1}, a_{2}</math> be two solid balls. If an end of a chain is tangent
to <math>a_{1}</math>, and the other end of the chain is tangent to <math>a_{2}</math>, then
to <math>\,a_{1}</math>, and the other end of the chain is tangent to <math>\,a_{2}</math>, then
the chain is said to connect <math>a_{1}, a_{2}</math>. Let <math>G = (V,E)</math> be a
the chain is said to connect <math>\,a_{1}, a_{2}</math>. Let <math>\,G = (V,E)</math> be a
finite graph. Take a family of red solid balls <math>a_{i}, \; i \in V</math>.
[[finite graph]]. Take a family of red solid balls <math>a_{i}, \; i \in V</math>.
Connect each non-tangent pair <math>a_{i}, a_{j}</math> (<math>ij \in E</math>) by a chain
Connect each non-tangent pair <math>\,a_{i}, a_{j}</math> (<math>i,\;j \in E</math>) by a chain
of blue solid balls so that no two distinct chains share a blue ball.
of blue solid balls so that no two distinct chains share a blue ball.
Then we have a family <math>{\mathcal F}</math> consisting of solid balls <math>a_{i}, \;
Then we have a family <math>{\mathcal F}</math> consisting of solid balls <math>a_{i}, \;
i \in V</math>, and the solid balls making the chains. This family is called
i \in V</math>, and the solid balls making the chains. This family is called
a representation of <math>G</math>. The '''ball number''' <math>b(G)</math> of <math>G</math> is the
a representation of <math>\,G</math>. The '''ball number''' <math>\,b(G)</math> of <math>\,G</math> is the
minimum number of balls necessary to make a representation of <math>G</math>. For
minimum number of balls necessary to make a representation of <math>\,G</math>. For
example, <math>b(K_{6}) = 8</math>, <math>b(K_{7}) = 13</math>.
example, <math>\,b(K_{6}) = 8</math>, <math>\,b(K_{7}) = 13</math>.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.