Строго хордальный граф: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Строго хордальный граф''' (''Strongly chordal graph'') - Пусть <math>N(v)</math> --- окрестность ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Строго хордальный граф''' (''Strongly chordal graph'') - | '''Строго хордальный граф''' (''[[Strongly chordal graph]]'') - | ||
Пусть <math>N(v)</math> - | Пусть <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] | [Евстигнеев/98] | ||
Версия от 12:17, 2 февраля 2010
Строго хордальный граф (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] допускает строго элиминирующий порядок.
Литература
[Евстигнеев/98]