Гипотеза Брэттона: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 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>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, \\
Строка 9: Строка 5:
\end{array} \right.</math>
\end{array} \right.</math>


Гипотеза решена М.Гольдбергом в 1966 г. (См. Докл. АН СССР, Т. 170, N 4, 1966).
Гипотеза решена М.Гольдбергом в 1966 г. (См. [[Докл. АН СССР, Т. 170, N 4, 1966]]).
==Литература==
==Литература==
[Берж]
[Берж]

Навигация