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