Дважды хордальный граф: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Дважды хордальный граф''' (''Doubly chordal graph'') - Пусть <math>N[v]</math>~--- замкнутая окр...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Дважды хордальный граф''' (''Doubly chordal graph'') | '''Дважды хордальный граф''' (''[[Doubly 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> называется ''[[дважды симплициальная вершина|дважды симплициальной]]'' (''[[doubly simplicial]]''),если она [[симплициальная вершина|симплициальна]] (т.е. для нее <math>N[v]</math> — [[клика]]) и имеет [[максимальный сосед|максимального соседа]]. Упорядочение <math>(v_{1}, \ldots, | ||
замкнутая окрестность вершины <math>v</math>. Вершина <math>u \in N[v]</math> называется | v_{n})</math>называется ''[[дважды совершенное упорядочение|дважды совершенным упорядочением]]'' (''[[doubly perfect ordering]]''), если каждая вершина <math>v_{i}</math> | ||
''максимальным соседом'' вершины <math>v</math>, если для всех <math>w \in N[v]</math> | дважды симплициальна в <math>G_{i}</math>. [[Граф]] называется ''дважды хордальным'', если | ||
имеет место включение <math>N[w] \subseteq N[u]</math> (заметим, что <math>u = v</math> не | |||
исключается). | |||
Вершина <math>v</math> называется ''дважды симплициальной'' | |||
(''doubly simplicial''),если она симплициальна | |||
(т.е. для нее <math>N[v]</math> | |||
Упорядочение <math>(v_{1}, \ldots, | |||
v_{n})</math>называется ''дважды совершенным упорядочением'' (''doubly | |||
perfect ordering''), если каждая вершина <math>v_{i}</math> | |||
дважды симплициальна в <math>G_{i}</math> Граф называется | |||
''дважды хордальным'', если | |||
он допускает дважды совершенное упорядочение. | он допускает дважды совершенное упорядочение. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. — С.5 — 27. | |||
Текущая версия от 16:56, 3 февраля 2011
Дважды хордальный граф (Doubly 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 }[/math] называется дважды симплициальной (doubly simplicial),если она симплициальна (т.е. для нее [math]\displaystyle{ N[v] }[/math] — клика) и имеет максимального соседа. Упорядочение [math]\displaystyle{ (v_{1}, \ldots, v_{n}) }[/math]называется дважды совершенным упорядочением (doubly perfect ordering), если каждая вершина [math]\displaystyle{ v_{i} }[/math] дважды симплициальна в [math]\displaystyle{ G_{i} }[/math]. Граф называется дважды хордальным, если он допускает дважды совершенное упорядочение.
Литература
- Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. — С.5 — 27.