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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Дважды хордальный граф''' (''Doubly chordal graph'') - Пусть <math>N[v]</math>~--- замкнутая окр...)
 
Нет описания правки
Строка 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,
замкнутая окрестность вершины <math>v</math>. Вершина <math>u \in N[v]</math> называется
v_{n})</math>называется ''[[дважды совершенное упорядочение|дважды совершенным упорядочением]]'' (''[[doubly perfect ordering]]''), если каждая вершина <math>v_{i}</math>
''максимальным соседом'' вершины <math>v</math>, если для всех <math>w \in N[v]</math>
дважды симплициальна в <math>G_{i}</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>
дважды симплициальна в <math>G_{i}</math> Граф называется
''дважды хордальным'', если
он допускает дважды совершенное упорядочение.
он допускает дважды совершенное упорядочение.
==Литература==
==Литература==
[Евстигнеев/98]
[Евстигнеев/98]

Навигация