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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Слабо алмазо-свободный граф''' (''Weakly diamond-free graph'') - Пусть вершина <math>V</math> та...)
 
Нет описания правки
Строка 1: Строка 1:
'''Слабо алмазо-свободный граф''' (''Weakly diamond-free graph'') -  
'''Слабо алмазо-свободный граф''' (''[[Weakly diamond-free graph]]'') -  
Пусть вершина <math>V</math> такова, что ее степень не превышает
Пусть [[вершина]] <math>V</math> такова, что ее [[степень вершины|степень]] не превышает
<math>2\omega(G) - 1</math>, где <math>\omega(G)</math> --- ''плотность'' графа
<math>2\omega(G) - 1</math>, где <math>\omega(G)</math> - ''[[плотность |плотность'']] [[граф|графа]]
<math>G</math>, и ''окрестность'' <math>N(v)</math> порождает  
<math>G</math>, и ''[[окрестность вершины|окрестность]]'' <math>N(v)</math> порождает  
''алмазо-свободный'' подграф. Назовем ее WDF-вершиной. Граф
''[[алмазо-свободный граф|алмазо-свободный]]'' [[подграф]]. Назовем ее WDF-вершиной. Граф
называется WDF-графом, если каждый индуцированный подграф
называется WDF-графом, если каждый индуцированный подграф
содержит WDF-вершину. Класс WDF-графов содержит  
содержит WDF-вершину. Класс WDF-графов содержит  
''хордальные'' и ''совершенные реберные'' графы.
[[хордальный граф|''хордальные'']] и ''совершенные реберные'' графы.
==Литература==
==Литература==
[Discrete Math.]
[Discrete Math.]

Версия от 19:18, 1 февраля 2010

Слабо алмазо-свободный граф (Weakly diamond-free graph) - Пусть вершина [math]\displaystyle{ V }[/math] такова, что ее степень не превышает [math]\displaystyle{ 2\omega(G) - 1 }[/math], где [math]\displaystyle{ \omega(G) }[/math] - плотность графа [math]\displaystyle{ G }[/math], и окрестность [math]\displaystyle{ N(v) }[/math] порождает алмазо-свободный подграф. Назовем ее WDF-вершиной. Граф называется WDF-графом, если каждый индуцированный подграф содержит WDF-вершину. Класс WDF-графов содержит хордальные и совершенные реберные графы.

Литература

[Discrete Math.]