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.

Текущая версия от 16:31, 23 октября 2018

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

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

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

Литература

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