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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Гипотеза Бержа''' (''[[Conjecture of Berge]]'') - [[Граф]] <math>G</math> является ''совершенным'' тогда и только тогда, когда ни он, ни его дополнение <math>\bar{G}</math>не содержат ''[[порожденный подграф|порожденных подграфов]]'' вида <math>G_{2k+1}, k \geq 2</math>.
'''Гипотеза Бержа''' (''[[Conjecture of Berge]]'') [[Граф]] <math>G</math> является ''совершенным'' тогда и только тогда, когда ни он, ни его дополнение <math>\bar{G}</math>не содержат ''[[порожденный подграф|порожденных подграфов]]'' вида <math>G_{2k+1}, k \geq 2</math>.


Эта гипотеза, высказанная в 1962 г. и не доказанная до сих пор (но и не опровергнутая), сыграла большую роль в исследовании [[совершенный граф|совершенных графов]].
Эта гипотеза, высказанная в 1962 г. и не доказанная до сих пор (но и не опровергнутая), сыграла большую роль в исследовании [[совершенный граф|совершенных графов]].
==Литература=
==Литература==
[Лекции]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

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

Гипотеза Бержа (Conjecture of Berge) — Граф [math]\displaystyle{ G }[/math] является совершенным тогда и только тогда, когда ни он, ни его дополнение [math]\displaystyle{ \bar{G} }[/math]не содержат порожденных подграфов вида [math]\displaystyle{ G_{2k+1}, k \geq 2 }[/math].

Эта гипотеза, высказанная в 1962 г. и не доказанная до сих пор (но и не опровергнутая), сыграла большую роль в исследовании совершенных графов.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.