(k,g)-Cage: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>(k,g)</math>-Cage''' --- <math>(k,g)</math>-клетка. For a given ordered pair of integers <math>(k,g)</math>, with <math>k \geq 2</math> and <math>g …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>(k,g)</math>-Cage''' - | '''<math>\,(k,g)</math>-Cage''' — ''[[(k,g)-Клетка|<math>\,(k,g)</math>-клетка]].'' | ||
For a given ordered pair of integers <math>(k,g)</math>, with <math>k \geq 2</math> and <math>g | For a given ordered pair of integers <math>\,(k,g)</math>, with <math>k \geq 2</math> and <math>g | ||
\geq 3</math>, a <math>k</math>-regular graph with the smallest cycle length, or girth, | \geq 3</math>, a <math>\,k</math>-[[regular graph]] with the smallest [[cycle]] length, or girth, | ||
equal to <math>g</math> is said to be a <math>(k,g)</math>-graph. A '''<math>(k,g)</math>-cage''' is a | equal to <math>\,g</math> is said to be a <math>\,(k,g)</math>-graph. A '''<math>\,(k,g)</math>-cage''' is a | ||
<math>(k,g)</math>-graph having the least number, <math>f(k,g)</math>, of vertices. We call | <math>\,(k,g)</math>-graph having the least number, <math>\,f(k,g)</math>, of [[vertex|vertices]]. We call | ||
<math>f(k,g)</math> the ''' cage number''' of a <math>(k,g)</math>-graph. One readily | <math>\,f(k,g)</math> the '''[[cage number]]''' of a <math>\,(k,g)</math>-graph. One readily | ||
observes that <math>(2,g)</math>-cages are cycles of length <math>g</math>, and | observes that <math>\,(2,g)</math>-cages are cycles of length <math>\,g</math>, and | ||
<math>(k,3)</math>-cages are complete graphs of order <math>k+1</math>. | <math>\,(k,3)</math>-cages are [[complete graph|complete graphs]] of order <math>\,k+1</math>. | ||
The unique (3,7)-cage known as the '''McGee graph''' is an example of | The unique <math>\,(3,7)</math>-cage known as the '''[[McGee graph]]''' is an example of | ||
a cage that is not transitive. It has 24 vertices and its automorphism | a cage that is not transitive. It has <math>\,24</math> vertices and its automorphism group has order <math>\,32</math>. | ||
group has order 32. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 11:50, 24 апреля 2012
[math]\displaystyle{ \,(k,g) }[/math]-Cage — [math]\displaystyle{ \,(k,g) }[/math]-клетка.
For a given ordered pair of integers [math]\displaystyle{ \,(k,g) }[/math], with [math]\displaystyle{ k \geq 2 }[/math] and [math]\displaystyle{ g \geq 3 }[/math], a [math]\displaystyle{ \,k }[/math]-regular graph with the smallest cycle length, or girth, equal to [math]\displaystyle{ \,g }[/math] is said to be a [math]\displaystyle{ \,(k,g) }[/math]-graph. A [math]\displaystyle{ \,(k,g) }[/math]-cage is a [math]\displaystyle{ \,(k,g) }[/math]-graph having the least number, [math]\displaystyle{ \,f(k,g) }[/math], of vertices. We call [math]\displaystyle{ \,f(k,g) }[/math] the cage number of a [math]\displaystyle{ \,(k,g) }[/math]-graph. One readily observes that [math]\displaystyle{ \,(2,g) }[/math]-cages are cycles of length [math]\displaystyle{ \,g }[/math], and [math]\displaystyle{ \,(k,3) }[/math]-cages are complete graphs of order [math]\displaystyle{ \,k+1 }[/math].
The unique [math]\displaystyle{ \,(3,7) }[/math]-cage known as the McGee graph is an example of a cage that is not transitive. It has [math]\displaystyle{ \,24 }[/math] vertices and its automorphism group has order [math]\displaystyle{ \,32 }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.