Дважды хордальный граф

Материал из WEGA
Версия от 11:57, 13 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Дважды хордальный граф''' (''Doubly chordal graph'') - Пусть <math>N[v]</math>~--- замкнутая окр...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Дважды хордальный граф (Doubly chordal graph) - Пусть [math]\displaystyle{ N[v] }[/math]~--- замкнутая окрестность вершины [math]\displaystyle{ v }[/math]. Вершина [math]\displaystyle{ u \in N[v] }[/math] называется максимальным соседом вершины [math]\displaystyle{ v }[/math], если для всех [math]\displaystyle{ w \in N[v] }[/math] имеет место включение [math]\displaystyle{ N[w] \subseteq N[u] }[/math] (заметим, что [math]\displaystyle{ u = v }[/math] не исключается). Вершина [math]\displaystyle{ v }[/math] называется дважды симплициальной (doubly simplicial),если она симплициальна (т.е. для нее [math]\displaystyle{ N[v] }[/math] --- клика) и имеет максимального соседа. Упорядочение [math]\displaystyle{ (v_{1}, \ldots, v_{n}) }[/math]называется дважды совершенным упорядочением (doubly perfect ordering), если каждая вершина [math]\displaystyle{ v_{i} }[/math] дважды симплициальна в [math]\displaystyle{ G_{i} }[/math] Граф называется дважды хордальным, если он допускает дважды совершенное упорядочение.

Литература

[Евстигнеев/98]