Совершенный граф: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Совершенный граф''' (''Perfect graph'') - граф, обладающий тем свойством, что хромат...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Совершенный граф''' (''Perfect graph'') -
'''Совершенный граф''' (''[[Perfect graph]]'')
граф, обладающий тем свойством, что хроматическое число и плотность
[[граф]], обладающий тем свойством, что [[хроматическое число]] и [[плотность]]
равны не только у самого графа, но и у каждого его
равны не только у самого графа, но и у каждого его
подграфа (порожденного подграфа).
[[подграф|подграфа]] ([[порожденный подграф|порожденного подграфа]]).


См. также ''Гипотеза Бержа''.
==См. также ==
* ''[[Гипотеза Бержа]].''
==Литература==
==Литература==
[Лекции],  
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
 
[Golumbic]
* Golumbic M.C. Algorithmic graph theory and perfect graphs. —  New York: Academic Press, 1980.

Текущая версия от 13:39, 9 сентября 2011

Совершенный граф (Perfect graph) — граф, обладающий тем свойством, что хроматическое число и плотность равны не только у самого графа, но и у каждого его подграфа (порожденного подграфа).

См. также

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Golumbic M.C. Algorithmic graph theory and perfect graphs. — New York: Academic Press, 1980.