Ball number: различия между версиями
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 участника) | |||
| Строка 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. | |||
Текущая версия от 16:05, 19 декабря 2011
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.