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

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

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

Литература

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