Grafo ciclo

Grafo ciclo ${\displaystyle C_{n}}$
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 consiste en un camino simple cerrado, es decir, en el que no se repite ningún vértice, salvo el primero con el último. Un grafo ciclo de n vértices se denota ${\displaystyle C_{n}}$. El número de vértices en un grafo ciclo es igual al número de aristas. En su versión más común, como grafo no dirigido, cada vértice tiene grado 2, por lo que es un grafo 2-regular; en su versión dirigida, en cambio, se trata de un grafo 1-regular.

Definición formal

Si ${\displaystyle G(V,E)\,}$ es un grafo ciclo ${\displaystyle C_{n}}$, el grafo tiene ${\displaystyle n}$ vértices ${\displaystyle V=\{v_{1},v_{2},\ldots ,v_{n}\}}$ y ${\displaystyle n}$ aristas formadas de la siguiente manera:

${\displaystyle E=\{\{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: ${\displaystyle \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: ${\displaystyle \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: ${\displaystyle \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

${\displaystyle \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

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

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.

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

Si las aristas del grafo no están orientadas en una misma dirección, entonces se habla de «semiciclo» en lugar de «ciclo».^[1]​

Grafos ciclo signados

El signo de un grafo ciclo signado o con signos es igual al producto de los signos de las aristas incluidas en el grafo, calculado de acuerdo a una conjunción lógica:^[1]​

• (+)(+) = +
• (+)(–) = –
• (–)(+) = –
• (–)(–) = +

Por lo tanto, un grafo ciclo con un número par de aristas negativas tendrá un signo positivo, y un grafo ciclo con un número impar de aristas negativas, tendrá un signo negativo. Note que todo lo anterior se mantiene para un grafo semiciclo dirigido.^[1]​

Véase también

• Camino (teoría de grafos)
• Grafo bipartito
• Bucle (teoría de grafos)

Referencias

Bibliografía

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

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.

Esta página se editó por última vez el 1 may 2021 a las 11:51.