Ball number

Материал из WikiGrapp
Перейти к:навигация, поиск

Ball numberшаровое число (графа).

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

Let \,a_{1}, a_{2} be two solid balls. If an end of a chain is tangent to \,a_{1}, and the other end of the chain is tangent to \,a_{2}, then the chain is said to connect \,a_{1}, a_{2}. Let \,G = (V,E) be a finite graph. Take a family of red solid balls a_{i}, \; i \in V. Connect each non-tangent pair \,a_{i}, a_{j} (i,\;j \in E) by a chain of blue solid balls so that no two distinct chains share a blue ball. Then we have a family {\mathcal F} consisting of solid balls a_{i}, \;
i \in V, and the solid balls making the chains. This family is called a representation of \,G. The ball number \,b(G) of \,G is the minimum number of balls necessary to make a representation of \,G. For example, \,b(K_{6}) = 8, \,b(K_{7}) = 13.


  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.