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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Гипотеза Брэттона''' (''Conjecture of Bratton'') - У всякого сильно связного графа без ...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии 2 участников)
Строка 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, \\
2q+1\mbox{ при } r = 1, \\ 2q+2\mbox{ при } r \geq 2.
2q+1\mbox{ при } r = 1, \\ 2q+2\mbox{ при } r \geq 2.
Строка 10: Строка 7:
Гипотеза решена М.Гольдбергом в 1966 г. (См. Докл. АН СССР, Т. 170, N 4, 1966).
Гипотеза решена М.Гольдбергом в 1966 г. (См. Докл. АН СССР, Т. 170, N 4, 1966).
==Литература==
==Литература==
[Берж]
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.

Текущая версия от 13:27, 9 декабря 2010

Гипотеза Брэттона (Conjecture of Bratton) — У всякого сильно связного графа без петель с [math]\displaystyle{ m }[/math] дугами и [math]\displaystyle{ n }[/math] вершинами диаметр больше или равен [math]\displaystyle{ \delta(m,n)-1 }[/math], где [math]\displaystyle{ \delta(m,n) }[/math] определяется следующим образом. Пусть [math]\displaystyle{ q }[/math] — частное, а [math]\displaystyle{ r }[/math] — остаток от деления [math]\displaystyle{ n-1 }[/math] на [math]\displaystyle{ \nu = m-n+1 }[/math]. Тогда

[math]\displaystyle{ \delta(m,n) = \left\{ \begin{array}{l} 2q\mbox{ при } r = 0, \\ 2q+1\mbox{ при } r = 1, \\ 2q+2\mbox{ при } r \geq 2. \end{array} \right. }[/math]

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

Литература

  • Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.