Célula (teoría de grafos)
Una celda n es un gráfico cúbico de circunferencia n con el menor número posible de vértices. Un grafo se dice cúbico si de cada uno de sus vértices salen 3 aristas. La circunferencia de un gráfico es la longitud del ciclo más pequeño en él.
Por cada 2 < n < 9 hay una celda n única, y todos estos gráficos son altamente simétricos ( unitransitivos ). Además, cuando se representan en un plano, a menudo dan un número extremo de autointersecciones, en lo sucesivo denominado índice .
- 3 celdas - K 4 , columna vertebral de un tetraedro , 4 vértices.
- 4 celdas - K 3,3 , uno de los dos gráficos mínimos no planos , 6 vértices.
- Gráfico de Petersen de 5 celdas , 10 vértices. Gráfico cúbico mínimo con índice de autointersección 2.
- Gráfico de Heawood de 6 celdas , 14 vértices. Descompuesto en factores de 1 (es decir, color de borde), cualquier suma de dos factores forma un ciclo hamiltoniano . Gráfico cúbico mínimo con índice de autointersección 3.
- 7 celdas - Count McGee , 24 vértices. Gráfico cúbico mínimo con índice de autointersección 8.
- 8 celdas - Count Tatta - Coxeter , 30 vértices.
Definición generalizada
( r , n )-cell es un gráfico regular de grado r (es decir, cada vértice tiene exactamente r aristas) y circunferencia n con el menor número posible de vértices.
familias triviales
- Las celdas (2, n ) son obviamente gráficos cíclicos C n
- ( r -1,3)-las celdas son grafos completos K r de r vértices
- Las celdas ( r ,4) son gráficos bipartitos completos К r , r , que tienen r vértices en cada parte
Representantes no triviales
- (7,5) celdas: gráfico de Hoffman-Singleton , 50 vértices.
Se conocen algunas células más. La siguiente tabla muestra el número de vértices en ( r , n )-celdas de grado 3≤ r ≤7 y circunferencia 3≤ n ≤12 . Las celdas para estos y r y n más grandes se describen aquí: [1] (en inglés).
| n : | 3 | cuatro | 5 | 6 | 7 | ocho | 9 | diez | once | 12 |
| r = 3: | cuatro | 6 | diez | catorce | 24 | treinta | 58 | 70 | 112 | 126 |
|---|---|---|---|---|---|---|---|---|---|---|
| r = 4: | 5 | ocho | 19 | 26 | 67 | 80 | 275 | 384 | 728 | |
| r = 5: | 6 | diez | treinta | 42 | 152 | 170 | 2730 | |||
| r = 6: | 7 | 12 | 40 | 62 | 294 | 312 | 7812 | |||
| r = 7: | ocho | catorce | cincuenta | 90 |
Condes de Moore
El número de vértices en la celda ( r , n ) es mayor o igual que
para n impar y incluso para.
Si se cumple la igualdad, entonces el gráfico correspondiente se llama gráfico de Moore . Si bien existe una celda para cualquier r > 2 y n > 2, hay muchos menos gráficos de Moore no triviales. De las celdas anteriores, los gráficos de Moore son el gráfico de Petersen , el gráfico de Heawood , el gráfico de Tutt-Coxeter y el gráfico de Hoffman-Singleton. Se ha probado [1] [2] [3] que todos los casos impares se agotan en n = 5, r = 2, 3, 7 y posiblemente 57, y los casos pares en n = 6, 8, 12.
Notas
- ↑ Bannai, E. e Ito, T. "Sobre los gráficos de Moore". Fac. J. ciencia Universidad tokio ser. A 20, 191-208, 1973
- ↑ Damerell, R.M. "Sobre los gráficos de Moore". proc. Filosofía de Cambridge. soc. 74, 227-236, 1973
- ↑ Hoffman, AJ y Singleton, RR "Sobre los gráficos de Moore de diámetro 2 y 3". IBM J.Res. Desarrollar. 4, 497-504, 1960
Literatura
- F. Teoría de grafos de Harari . - M .: URSS , - 2003. - 300 s - ISBN 5-354-00301-6 .
Enlaces
- Weisstein, Eric W. Cell Graph en Wolfram MathWorld .
- https://web.archive.org/web/20090224031515/http://people.csse.uwa.edu.au/gordon/cages/ _