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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

  • Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. — С.5 — 27.