Gráfico cíclico

En teoría de grafos , un grafo cíclico o circular es un grafo que consta de un solo ciclo , o dicho de otro modo, un cierto número de vértices (al menos 3, si el grafo es simple ) conectados en una cadena cerrada. El grafo cíclico con n vértices se denomina C _n . ^{[ 2 ]} 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, cada vértice tiene exactamente dos aristas incidentes con él.

Gráfico cíclico${\displaystyle C_{1}}$es un bucle aislado . Grafo de ciclo${\displaystyle C_{3}}$es lo mismo que un gráfico completo${\displaystyle K_{3}}$.

Existen muchos sinónimos para "grafo cíclico". Entre ellos se incluyen grafo cíclico simple y grafo cíclico , aunque este último término se usa con menos frecuencia, ya que también puede referirse a grafos que simplemente no son acíclicos . Entre los teóricos de grafos, también se utilizan a menudo los términos ciclo , polígono o n -gono . El término n -ciclo se usa a veces en otros contextos. ^{[ 3 ]}

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 .

Un gráfico cíclico es:

• Coloreable por 2 aristas , si y solo si tiene un número par de vértices.
• 2-regular
• Un grafo es coloreable con dos vértices si y solo si tiene un número par de vértices. De forma más general, un grafo es bipartito si y solo si no tiene ciclos impares ( Kőnig , 1936).
• Conectado
• Euleriano
• Hamiltoniano
• Un gráfico de distancia unitaria

Además:

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

De forma similar a los grafos platónicos , los grafos cíclicos forman los esqueletos de los diedros . Sus duales son los grafos dipolares , que forman los esqueletos de los hosoedros .

Un grafo cíclico dirigido es una versión dirigida de un grafo cíclico, en la que todas las aristas están orientadas en la misma dirección.

En un grafo 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 grafo de ciclo dirigido tiene un grado de entrada uniforme  de 1 y un grado de salida uniforme  de 1.

Los grafos de ciclos dirigidos son grafos de Cayley para grupos cíclicos (véase, por ejemplo, Trevisan).

• Grafo bipartito completo
• Gráfico completo
• Gráfico circulante
• Gráfico cíclico (álgebra)
• Grafo nulo
• Grafo de ruta

• Diestel, Reinhard (2017). Teoría de grafos (5.ª  ed.). Springer . ISBN 978-3-662-53621-6.

• Weisstein, Eric W. "Grafo cíclico" . MathWorld .(discusión sobre los grafos de ciclos 2-regulares y el concepto de diagramas de ciclos en la teoría de grupos )
• Luca Trevisan , Personajes y expansión .