Gráfica de ciclo

En teoría de grafos , un grafo de ciclo o grafo circular es un grafo que consta de un solo ciclo , o en otras palabras, un cierto número de vértices (al menos 3, si el grafo es simple ) conectados en una cadena cerrada. El grafo de ciclo con n vértices se llama 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.

Existen muchos sinónimos para "gráfico de ciclo". Entre ellos se incluyen el gráfico de ciclo simple y el gráfico cíclico , aunque el último término se utiliza con menos frecuencia, ya que 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 ciclo , polígono o n -gono . El término n -ciclo se utiliza 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 de ciclo es:

• Coloreable de 2 aristas , si y solo si tiene un número par de vértices
• 2-regular
• Coloreable de 2 vértices , si y solo si tiene un número par de vértices. En términos más generales, 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 de ciclos pueden dibujarse 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 diedro 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 n -ciclo es un grafo simétrico .

De manera 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 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 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 gráfico de ciclo dirigido tiene un grado de entrada uniforme de 1 y un grado de salida uniforme de 1.

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

• Grafo bipartito completo
• Gráfica completa
• Gráfico circulante
• Gráfica de ciclos (álgebra)
• Gráfico nulo
• Gráfico de ruta

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

• Weisstein, Eric W. "Gráfico de ciclo". MundoMatemático .(Discusión de los gráficos de ciclos 2-regulares y del concepto teórico de grupos de los diagramas de ciclos )
• Luca Trevisan , Personajes y Expansión.