Двойственно хордальный граф

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

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

Граф G называется двойственно хордальным, если G допускает упорядочение максимального соседства.

Литература

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