Grafo ciclo

Grafo ciclo Cn
	; ciclo C6
Vértices	n
Aristas	n
Cintura	n
Automorfismos	2n (Dn)
Número cromático	2 si n es par; 3 si n es impar;
Índice cromático	2 si n es par; 3 si n es impar;
Propiedades	2-conexo por vértices; 2-conexo por aristas; 2-regular; Euleriano; Hamiltoniano; orientable;
	[editar datos en Wikidata]

En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un polígono 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 C_n. El número de vértices en un grafo C_n es igual al número de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene al menos dos aristas incidentes.

si $G(V,A)\,$ es un ciclo C_n, el grafo tiene n vértices $V=\{v_{1},v_{2},...,v_{n}\}\,$ y n aristas formadas de la siguiente manera:

A=\{\{v_{i},v_{i+1}\}|i=1,...,n-1\}\cup \{v_{n},v_{1}\}

Propiedades

Un grafo ciclo es:

2-conexo

En efecto, si tomamos 2 vértices cualquiera, siempre hay 2 caminos disjuntos (sin vértices comunes a excepción de los vértices extremos) que los conectan. Luego, por el Teorema de Whitney (1932), los ciclos tienen índice de conexión: $\kappa \,(C_{n})=2$ .

Los ciclos son también 2-conexo por aristas, en efecto, dado 2 vértices 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: $\kappa _{a}\,(C_{n})=2$ .

Los ciclos al tener el índice de arista conexión igual a 2 carecen de aristas puentes.

2-regular

Es claro que los ciclos son 2-regulares, ya que dado un ciclo de n vértices, todos sus grados son iguales a dos: $\delta (v_{i})=2\,$ con i=1,...,n

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.

Hamiltoniano

Es fácil ver que también contienen un ciclo hamiltoniano.

Coloración

$\chi (C_{n})={\begin{cases}2,&{\mbox{si }}n{\mbox{ es par}}\\3,&{\mbox{si }}n{\mbox{ es impar}}\end{cases}}$

Coloración por aristas

$\chi '(C_{n})={\begin{cases}2,&{\mbox{si }}n{\mbox{ es par}}\\3,&{\mbox{si }}n{\mbox{ es impar}}\end{cases}}$

Algoritmo para determinar si se forman ciclos

Algoritmo: Para determinar si al agregar una arista a una grafo se forma algún ciclo

//Siendo una arista nueva con nodos adyacentes A y B

1. Tomamos cualquier nodo adyacente a la arista que vamos a generar (Por ejemplo A)

2. Verificamos que no tenga aristas hacia B, y de ser así lo marcamos

3. Repetimos el proceso (2) con cada uno de los nodos adayacentes al nodo A y hasta marcar todos los nodos conectados.

4. Si en todo el recorrido no encontró ninguna arista hacia B, entonces no se generan ciclos al agregar la arista nueva.

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.

$\delta _{s}(x)=\delta _{e}(x)=1\,$

Véase también

Enlaces externos

Weisstein, Eric W. «Cycle Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. . (MathWorld discusses both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams in the same article.)
Luca Trevisan, Characters and Expansion.

Datos: Q622506
Multimedia: Cycle graphs / Q622506