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

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


==См. также ==
==См. также ==
''[[Гипотеза Бержа]]''.
* ''[[Гипотеза Бержа]].''
==Литература==
==Литература==
[Лекции],  
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 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.