Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Двойственно хордальный граф''' (''[[Dually chordal graph]]'') - Пусть <math>N[v]</math> ---
'''Двойственно хордальный граф''' (''[[Dually chordal graph]]'') Пусть <math>N[v]</math>
[[замкнутая окрестность]] [[вершина|вершины]] <math>v</math>. Вершина <math>u \in N[v]</math> называется ''[[максимальный сосед|максимальным соседом]]'' вершины <math>v</math>, если для всех <math>w \in N[v]</math> имеет место включение <math>N[w] \subseteq N[u]</math> (заметим, что <math>u = v</math> не исключается).
[[замкнутая окрестность]] [[вершина|вершины]] <math>v</math>. Вершина <math>u \in N[v]</math> называется ''[[максимальный сосед|максимальным соседом]]'' вершины <math>v</math>, если для всех <math>w \in N[v]</math> имеет место включение <math>N[w] \subseteq N[u]</math> (заметим, что <math>u = v</math> не исключается).
Упорядочение <math>(v_{1}, \ldots, v_{n})</math>называется ''[[упорядочение максимального соседства|упорядочением максимального соседства]]'', если для всех <math>i \in \{1, \ldots, n\}</math> существует максимальный сосед <math>u_{i} \in N_{i}[v_{i}]</math> т.е. для всех <math>w \in N_{i}[v_{i}]</math> имеет место <math>N_{i}[w] \subseteq N_{i}[u_{i}]</math>
Упорядочение <math>(v_{1}, \ldots, v_{n})</math>называется ''[[упорядочение максимального соседства|упорядочением максимального соседства]]'', если для всех <math>i \in \{1, \ldots, n\}</math> существует максимальный сосед <math>u_{i} \in N_{i}[v_{i}]</math> т.е. для всех <math>w \in N_{i}[v_{i}]</math> имеет место <math>N_{i}[w] \subseteq N_{i}[u_{i}]</math>
Строка 5: Строка 5:
[[Граф]] <math>G</math> называется ''двойственно хордальным'', если <math>G</math> допускает упорядочение максимального соседства.
[[Граф]] <math>G</math> называется ''двойственно хордальным'', если <math>G</math> допускает упорядочение максимального соседства.
==Литература==
==Литература==
[Евстигнеев/98]
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.