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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Расширенный нечетный граф''' (''Extended odd graph'') - граф <math>E_{k}</math> <math>k \geq 2</math>, с ...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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 \, | \,
:::<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>
и множеством [[ребро|ребер]]
\noindent и множеством
:::<math>E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1</math> или <math>|A \triangle A'| = 2k-2\},</math>
ребер <math>E(E_{k}) = \{(A,A') \, | \, |A \triangle A'| = 1 \mbox{ или }
 
|A \triangle A'| = 2k-2\},</math>
где <math>\triangle</math> симметрическая
\noindent где <math>\triangle</math> --- симметрическая
разность составляющих подмножеств.
разность составляющих подмножеств.


Для <math>k =2\mbox{ или } 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.

Текущая версия от 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.