Grafo en ciclo

En teoría de grafos, un grafo en ciclo o ciclo es un gráfico que consta de un solo ciclo, o en otras palabras, un número de vértices (al menos 3, si el gráfico es simple) conectados en una cadena cerrada. El gráfico de ciclo con n vértices se llama C _n. El número de vértices en C _n es igual al número de aristas, y cada vértice tiene grado 2; es decir, todo vértice tiene exactamente dos aristas incidentes con él.

Terminología

Hay muchos sinónimos para "gráfico de ciclo". Estos incluyen gráfico de ciclo simple y gráfico cíclico, aunque el último término se usa con menos frecuencia, porque también puede referirse a gráficos que simplemente no son acíclicos. Entre los teóricos de grafos, también se utilizan a menudo el ciclo, el polígono o el n -ágono. El término n -ciclo se utiliza a veces en otros contextos.

Un ciclo con un número par de vértices se llama ciclo par; un ciclo con un número impar de vértices se llama ciclo impar.

Propiedades

Un gráfico de ciclo es:

• Coloreable de 2 aristas, si y solo si tiene un número par de vértices
• 2-regulares
• Coloreable de 2 vértices, si y solo si tiene un número par de vértices. De manera más general, un gráfico es bipartito si y solo si no tiene ciclos impares (Kőnig, 1936).
• Conectado
• Euleriano
• hamiltoniano
• Un gráfico de unidad de distancia

Además:

• Como los gráficos de ciclo se pueden dibujar como polígonos regulares, las simetrías de un n -ciclo son las mismas que las de un polígono regular con n lados, el grupo diédrico de orden 2 n. En particular, existen simetrías que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista, por lo que el ciclo n es un grafo simétrico.

De manera similar a los gráficos platónicos, los gráficos de ciclo forman los esqueletos de los diedros. Sus duales son los gráficos dipolares, que forman los esqueletos de los hosoedros.

Gráfico de ciclo dirigido

Un gráfico de ciclo dirigido es una versión dirigida de un gráfico de ciclo, con todos los bordes orientados en la misma dirección.

En un gráfico dirigido, un conjunto de aristas que contiene al menos una arista (o arco) de cada ciclo dirigido se denomina conjunto de arcos de retroalimentación. De manera similar, un conjunto de vértices que contiene al menos un vértice de cada ciclo dirigido se denomina conjunto de vértices de retroalimentación.

Un gráfico de ciclo dirigido tiene un grado de entrada uniforme 1 y un grado de salida uniforme 1.

Los gráficos de ciclo dirigido son gráficos de Cayley para grupos cíclicos (véase, por ejemplo, Trevisan).