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, cierto número de vértices (al menos 3, si el grafo 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, cada vértice tiene exactamente dos aristas incidentes con él.
Gráfico de ciclo | |
---|---|
Vértices | norte |
Bordes | norte |
Circunferencia | norte |
Automorfismos | 2 n ( D n ) |
Número cromático | 3 si n es impar 2 en caso contrario |
Índice cromático | 3 si n es impar 2 en caso contrario |
Espectro | {2 cos (2 k π / n ); k = 1, ..., n } [1] |
Propiedades | 2- Vertex regular -transitivo Edge-transitivo Unidad de distancia Hamiltoniano Euleriano |
Notación | |
Tabla de gráficos y parámetros |
Terminología
Hay muchos sinónimos de "gráfico de ciclo". Estos incluyen gráfico de ciclo simple y gráfico cíclico , aunque este ú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 ciclos , polígonos o n -gon . El término ciclo n se utiliza a veces en otros entornos. [2]
Un ciclo con un número par de vértices se denomina ciclo par ; un ciclo con un número impar de vértices se denomina ciclo impar .
Propiedades
Un gráfico de ciclo es:
- Coloreable de 2 bordes , si y solo si tiene un número par de vértices
- 2-regular
- Colorable 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 ciclos se pueden dibujar como polígonos regulares , las simetrías de un ciclo n son las mismas que las de un polígono regular con 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 borde a cualquier otro borde, por lo que el ciclo n es un gráfico simétrico .
De manera similar a las gráficas platónicas , las gráficas cíclicas forman los esqueletos del dihedra . Sus duales son los gráficos dipolares , que forman los esqueletos del hosohedra .
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 (ver, por ejemplo, Trevisan).
Ver también
Referencias
- ^ Algunos espectros de gráficos simples . win.tue.nl
- ^ "Problema 11707". Amer. Matemáticas. Mensual . 120 (5): 469–476. Mayo de 2013. doi : 10.4169 / amer.math.monthly.120.05.469 . JSTOR 10.4169 / amer.math.monthly.120.05.469 .
enlaces externos
- Weisstein, Eric W. "Gráfico de ciclo" . MathWorld .(discusión de los gráficos de 2 ciclos regulares y el concepto teórico de grupo de los diagramas de ciclos )
- Luca Trevisan , Personajes y Expansión .