4194
правки
Гипотеза Брэттона: различия между версиями
Материал из WEGA
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Гипотеза Брэттона''' (''[[Conjecture of Bratton]]'') | '''Гипотеза Брэттона''' (''[[Conjecture of Bratton]]'') — У всякого [[сильно связный орграф|сильно связного графа]] без [[петля|петель]] с <math>m</math> [[дуга|дугами]] и <math>n</math> [[вершина|вершинами]] ''[[диаметр]]'' больше или равен <math>\delta(m,n)-1</math>, где <math>\delta(m,n)</math> определяется следующим образом. Пусть <math>q</math> — частное, а <math>r</math> — остаток от деления <math>n-1</math> на <math>\nu = m-n+1</math>. Тогда | ||
<math>\delta(m,n) = \left\{ \begin{array}{l} 2q\mbox{ при } r = 0, \\ | <math>\delta(m,n) = \left\{ \begin{array}{l} 2q\mbox{ при } r = 0, \\ | ||
| Строка 5: | Строка 5: | ||
\end{array} \right.</math> | \end{array} \right.</math> | ||
Гипотеза решена М.Гольдбергом в 1966 г. (См. | Гипотеза решена М.Гольдбергом в 1966 г. (См. Докл. АН СССР, Т. 170, N 4, 1966). | ||
==Литература== | ==Литература== | ||
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962. | |||
