Слабо алмазо-свободный граф: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Слабо алмазо-свободный граф''' (''Weakly diamond-free graph'') - Пусть вершина <math>V</math> та...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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.] | ||
Текущая версия от 11:06, 9 сентября 2011
Слабо алмазо-свободный граф (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.]