Двойственно хордальный граф: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Двойственно хордальный граф''' (''Dually chordal graph'') - Пусть <math>N[v]</math> --- замкнута...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Двойственно хордальный граф''' (''Dually chordal graph'') | '''Двойственно хордальный граф''' (''[[Dually chordal graph]]'') — Пусть <math>N[v]</math> — | ||
Пусть <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_{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</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>G</math> называется ''двойственно хордальным'', если | [[Граф]] <math>G</math> называется ''двойственно хордальным'', если <math>G</math> допускает упорядочение максимального соседства. | ||
<math>G</math> допускает упорядочение максимального соседства. | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 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.