Расширенный нечетный граф: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Расширенный нечетный граф''' (''[[Extended odd graph]]'') -
'''Расширенный нечетный граф''' (''[[Extended odd graph]]'')
[[граф]] <math>E_{k}</math> <math>k \geq 2</math>, с множеством [[вершина|вершин]]
[[граф]] <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]
* Mulder H.M.  The  interval  function  of a graph,  Mathematical Centre Tracts 132. — Amsterdam, 1980.

Навигация