Расширенный нечетный граф: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Расширенный нечетный граф''' (''[[Extended odd graph]]'') | '''Расширенный нечетный граф''' (''[[Extended odd graph]]'') — | ||
[[граф]] <math>E_{k} | [[граф]] <math>E_{k},\,k \geq 2,</math> с множеством [[вершина|вершин]] | ||
<math>V(E_{k}) = \{A \, | \, A \subseteq \{1, 2, \ldots, 2K-1\}, \; |A| \leq k-1\}</math> и множеством ребер | :::<math>V(E_{k}) = \{A \, | \, 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> | :::<math>E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1</math> или <math>|A \triangle A'| = 2k-2\},</math> | ||
где <math>\triangle</math> — симметрическая | |||
разность составляющих подмножеств. | разность составляющих подмножеств. | ||
Для <math>k =2</math> или <math>3</math> наименьшие расширенные нечетные графы | Для <math>\,k =2</math> или <math>\,3</math> наименьшие расширенные нечетные графы — это | ||
полный <math>K_{4} \cong E_{2}</math> и ''[[граф Гринвуда-Глисона]]'' <math>E_{3}</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 H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980. | |||
Текущая версия от 11:32, 30 августа 2011
Расширенный нечетный граф (Extended odd graph) — граф [math]\displaystyle{ E_{k},\,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 H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980.