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

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


Граф <math>G</math> называется ''строго хордальным'',
[[Граф]] <math>\,G</math> называется ''строго хордальным'',
если <math>G</math> допускает строго элиминирующий порядок.
если <math>\,G</math> допускает строго элиминирующий порядок.
==Литература==
==Литература==
[Евстигнеев/98]
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.

Текущая версия от 15:26, 9 сентября 2011

Строго хордальный граф (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] допускает строго элиминирующий порядок.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.