Строго хордальный граф

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

Строго хордальный граф (Strongly chordal graph) — Пусть \,N(v)окрестность вершины \,v и пусть N[v] = N(v) \cup
\{v\} — замкнутая окрестность вершины \,v. Пусть G_{i} = G(\{v_{i},
\ldots, v_{n}\}), тогда \,N_{i}[v] есть замкнутая окрестность \,v в \,G_{i}. Упорядочение вершин (v_{1}, \ldots, v_{n}) называется строго элиминирующим порядком, если для всех i
\in \{1, \ldots, n\} имеет место включение N_{i}[v_{j}] \subseteq
N_{i}[v_{k}], когда v_{j}, \, v_{k} \in N_{i}[v_{i}] и \,j < k.

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

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.