4625
правок
K-Binding number: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Binding number''' --- <math>k</math>-связывающее число. The '''<math>k</math>-binding number''' of <math>G</math> is defined to b…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Binding number''' - | '''<math>k</math>-Binding number''' — ''[[k-Связывающее число|<math>\,k</math>-связывающее число]].'' | ||
The '''<math>k</math>-binding number''' of <math>G</math> is defined to be | The '''<math>\,k</math>-binding number''' of <math>\,G</math> is defined to be | ||
<math>bind^{k}(G) = \min_{X \in \delta^{k-1}(G)} | <math>bind^{k}(G) = \min_{X \in \delta^{k-1}(G)} | ||
| Строка 13: | Строка 13: | ||
Let <math>k \geq 2</math>. The following two properties are obvious. | Let <math>k \geq 2</math>. The following two properties are obvious. | ||
1. Let <math>G</math> be a graph with <math>n</math> vertices. If <math>diam(G) \leq k-1</math>, then | 1. Let <math>\,G</math> be a [[graph, undirected graph, nonoriented graph|graph]] with <math>\,n</math> [[vertex|vertices]]. If <math>diam(G) \leq k-1</math>, then | ||
<math>bind^{k}(G) = n-1</math>. | <math>\,bind^{k}(G) = n-1</math>. | ||
2. If a graph <math>G</math> has at least one isolated vertex, then <math>bind^{k}(G) | 2. If a graph <math>\,G</math> has at least one [[isolated vertex]], then <math>\,bind^{k}(G) | ||
= 0</math>. | = 0</math>. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||