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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Нечетный граф''' (''[[Odd graph]]'') -
'''Нечетный граф''' (''[[Odd graph]]'')
[[граф]] <math>O_{k} = (V(O_{k}), E(O_{k}))</math>, <math>k \geq 2</math>, у которого
[[граф]] <math>\,O_{k} = (V(O_{k}), E(O_{k}))</math>, <math>k \geq 2</math>, у которого
<math>V(O_{k}) = \{A \, | \, A \subseteq \{1,2, \ldots, 2k-1\}, \;
<math>V(O_{k}) = \{A \, | \, A \subseteq \{1,2, \ldots, 2k-1\}, \;
|A| = k-1\}</math>, <math>E(O_{k}) = \{(A,A') \, | \, A \cap A' =
|A| = k-1\}</math>, <math>E(O_{k}) = \{(A,A') \, | \, A \cap A' =
\emptyset\}</math>. Для <math>k=2</math> и <math>k=3</math> наименьшие нечетные графы ---
\emptyset\}</math>. Для <math>\,k=2</math> и <math>\,k=3</math> наименьшие нечетные графы
это треугольник <math>O_{2} \cong K_{3}</math>и граф Петерсена <math>O_{3}
это треугольник <math>O_{2} \cong K_{3}</math>и граф Петерсена <math>O_{3}
\cong P_{10}</math> Для <math>k = 4</math> обхват нечетного графа <math>g(O_{k}) = 6</math>.
\cong P_{10}</math>. Для <math>\,k = 4</math> обхват нечетного графа <math>\,g(O_{k}) = 6</math>.
==Литература==
==Литература==
[Mulder]
* Mulder H.M.  The  interval  function  of a graph,  Mathematical Centre Tracts 132. — Amsterdam, 1980.

Текущая версия от 11:16, 20 мая 2011

Нечетный граф (Odd graph) — граф [math]\displaystyle{ \,O_{k} = (V(O_{k}), E(O_{k})) }[/math], [math]\displaystyle{ k \geq 2 }[/math], у которого [math]\displaystyle{ V(O_{k}) = \{A \, | \, A \subseteq \{1,2, \ldots, 2k-1\}, \; |A| = k-1\} }[/math], [math]\displaystyle{ E(O_{k}) = \{(A,A') \, | \, A \cap A' = \emptyset\} }[/math]. Для [math]\displaystyle{ \,k=2 }[/math] и [math]\displaystyle{ \,k=3 }[/math] наименьшие нечетные графы — это треугольник [math]\displaystyle{ O_{2} \cong K_{3} }[/math]и граф Петерсена [math]\displaystyle{ O_{3} \cong P_{10} }[/math]. Для [math]\displaystyle{ \,k = 4 }[/math] обхват нечетного графа [math]\displaystyle{ \,g(O_{k}) = 6 }[/math].

Литература

  • Mulder H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980.