Расширенный нечетный граф: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Расширенный нечетный граф''' (''Extended odd graph'') - граф <math>E_{k}</math> <math>k \geq 2</math>, с ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Расширенный нечетный граф''' (''Extended odd graph'') - | '''Расширенный нечетный граф''' (''[[Extended odd graph]]'') - | ||
граф <math>E_{k}</math> <math>k \geq 2</math>, с множеством вершин | [[граф]] <math>E_{k}</math> <math>k \geq 2</math>, с множеством [[вершина|вершин]] | ||
<math>V(E_{k}) = \{A \, | \, | <math>V(E_{k}) = \{A \, | \, A \subseteq \{1, 2, \ldots, 2K-1\}, \; |A| \leq k-1\}</math> и множеством ребер | ||
A \subseteq \{1, 2, \ldots, 2K-1\}, \; |A| \leq k-1\}</math> | <math>E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1</math> или <math>|A \triangle A'| = 2k-2\},</math> | ||
где <math>\triangle</math> --- симметрическая | |||
|A \triangle A'| = 2k-2\},</math> | |||
разность составляющих подмножеств. | разность составляющих подмножеств. | ||
Для <math>k =2 | Для <math>k =2</math> или <math>3</math> наименьшие расширенные нечетные графы --- это | ||
полный <math>K_{4} \cong E_{2}</math>и ''граф Гринвуда | полный <math>K_{4} \cong E_{2}</math> и ''[[граф Гринвуда-Глисона]]'' <math>E_{3}</math> | ||
Граф <math>E_{k}</math>является дистанционно-транзитивным. Наименьший нечетный | Граф <math>E_{k}</math>является [[дистанционно-транзитивный граф|дистанционно-транзитивным]]. Наименьший нечетный | ||
цикл в <math>E_{k}</math>имеет длину <math>2k-1</math>. | [[цикл]] в <math>E_{k}</math>имеет [[длина цепи|длину]] <math>2k-1</math>. | ||
==Литература== | ==Литература== | ||
[Mulder] | [Mulder] | ||
Версия от 16:21, 15 января 2010
Расширенный нечетный граф (Extended odd graph) - граф [math]\displaystyle{ E_{k} }[/math] [math]\displaystyle{ k \geq 2 }[/math], с множеством вершин [math]\displaystyle{ V(E_{k}) = \{A \, | \, A \subseteq \{1, 2, \ldots, 2K-1\}, \; |A| \leq k-1\} }[/math] и множеством ребер [math]\displaystyle{ E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1 }[/math] или [math]\displaystyle{ |A \triangle A'| = 2k-2\}, }[/math] где [math]\displaystyle{ \triangle }[/math] --- симметрическая разность составляющих подмножеств.
Для [math]\displaystyle{ k =2 }[/math] или [math]\displaystyle{ 3 }[/math] наименьшие расширенные нечетные графы --- это полный [math]\displaystyle{ K_{4} \cong E_{2} }[/math] и граф Гринвуда-Глисона [math]\displaystyle{ E_{3} }[/math]
Граф [math]\displaystyle{ E_{k} }[/math]является дистанционно-транзитивным. Наименьший нечетный цикл в [math]\displaystyle{ E_{k} }[/math]имеет длину [math]\displaystyle{ 2k-1 }[/math].
Литература
[Mulder]