4624
правки
Дважды хордальный граф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Дважды хордальный граф''' (''[[Doubly chordal graph]]'') | '''Дважды хордальный граф''' (''[[Doubly chordal graph]]'') — | ||
Пусть <math>N[v]</math> | Пусть <math>N[v]</math> — замкнутая [[окрестность вершины]] <math>v</math>. [[Вершина]] <math>u \in N[v]</math> называется ''[[максимальный сосед|максимальным соседом]]'' вершины <math>v</math>, если для всех <math>w \in N[v]</math> имеет место включение <math>N[w] \subseteq N[u]</math> (заметим, что <math>u = v</math> не исключается). Вершина <math>v</math> называется ''[[дважды симплициальная вершина|дважды симплициальной]]'' (''[[doubly simplicial]]''),если она [[симплициальная вершина|симплициальна]] (т.е. для нее <math>N[v]</math> — [[клика]]) и имеет [[максимальный сосед|максимального соседа]]. Упорядочение <math>(v_{1}, \ldots, | ||
v_{n})</math>называется ''[[дважды совершенное упорядочение|дважды совершенным упорядочением]]'' (''[[doubly perfect ordering]]''), если каждая вершина <math>v_{i}</math> | v_{n})</math>называется ''[[дважды совершенное упорядочение|дважды совершенным упорядочением]]'' (''[[doubly perfect ordering]]''), если каждая вершина <math>v_{i}</math> | ||
дважды симплициальна в <math>G_{i}</math>. [[Граф]] называется ''дважды хордальным'', если | дважды симплициальна в <math>G_{i}</math>. [[Граф]] называется ''дважды хордальным'', если | ||
он допускает дважды совершенное упорядочение. | он допускает дважды совершенное упорядочение. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | |||