Grafo ciclo
De Wikipedia, la enciclopedia libre
| Ciclo Cn | |
|---|---|
 C6: Un Grafo Ciclo de longitud 6. |
|
| Vertices: | n |
| Aristas: | n |
| Conexión: | 2-conexo. |
| Número cromático: |
|
| índice cromático: |
|
| otras propiedades: |
|
En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un poligono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices se denota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene dos aristas incidentes.
si 
es un ciclo Cn, el grafo tiene n vertices 
y n aristas formadas de la siguiente manera:
Contenido |
[editar] Propiedades
Un grafo ciclo es:
[editar] 2-conexo
En efecto, si tomamos 2 vertices cualquiera, siempre hay 2 caminos distintos (sin vertices comunes a excepción de los vertices extremos) que los conectan. Luego, por el Teorema de Whitney (1932), los ciclos tienen índice de conexión: 
.
Los ciclos son también 2-conexo por aristas, en efecto, dado 2 vertices cualquiera, siempre hay 2 caminos distintos (sin aristas comunes entre ambos) que los conectan. Luego, por el Teorema de Menger (1927), los ciclos tienen índice de arista conexión: 
.
Los ciclos al tener el índice de arista conexión igual a 2 carecen de aristas puentes.
[editar] 2-regular
Es claro que los ciclos son 2-regulares, ya que dado un ciclo de n vertices, todos sus grados son iguales a dos: 
con i=1,...,n
[editar] Euleriano
En efecto, los ciclos al ser conexos y 2-regulares satisfacen el Teorema de Euler(1736)-Hierholzer(1873). Luego, los ciclos contienen un Circuito euleriano.
[editar] Hamiltoniano
[editar] Coloración
[editar] Coloración por aristas
[editar] Grafo ciclo dirigido
Un grafo ciclo dirigido es una versión dirigida de un grafo ciclo, con todas las aristas orientadas hacia una misma dirección.
En un Grafo ciclo dirigido, el grado de salida del vértice es 1 y el de entrada también es 1.
[editar] Véase también
[editar] Enlaces externos
- Eric W. Weisstein, Cycle Graph en MathWorld. (MathWorld discusses both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams in the same article.)
- Luca Trevisan, Characters and Expansion.
