Ball number

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

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.