Двойственно хордальный граф: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 5: Строка 5:
[[Граф]] <math>G</math> называется ''двойственно хордальным'', если <math>G</math> допускает упорядочение максимального соседства.
[[Граф]] <math>G</math> называется ''двойственно хордальным'', если <math>G</math> допускает упорядочение максимального соседства.
==Литература==
==Литература==
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. — С.5 — 27.

Текущая версия от 16:58, 3 февраля 2011

Двойственно хордальный граф (Dually 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_{1}, \ldots, v_{n}) }[/math]называется упорядочением максимального соседства, если для всех [math]\displaystyle{ i \in \{1, \ldots, n\} }[/math] существует максимальный сосед [math]\displaystyle{ u_{i} \in N_{i}[v_{i}] }[/math] т.е. для всех [math]\displaystyle{ w \in N_{i}[v_{i}] }[/math] имеет место [math]\displaystyle{ N_{i}[w] \subseteq N_{i}[u_{i}] }[/math]

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

Литература

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