1294
правки
Ball number: различия между версиями
Материал из WEGA
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Ball number''' --- шаровое число (графа). By a family of solid balls in <math>R^{3}</math>, we mean a family of balls no two of which penetrate…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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> | 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. | |||
