Grafo ciclo

Grafo ciclo
Ciclo Cn
img

C6: Un Grafo Ciclo de longitud 6.
Vertices: n
Aristas: n
Conexión: 2-conexo.
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
otras propiedades:
  • 2-regular
  • Euleriano.
  • Hamiltoniano.
  • Orientable

En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un poligono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices se denota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene dos aristas incidentes.

si G(V,A)\, es un ciclo Cn, el grafo tiene n vertices V= \{v_1 , v_2 , ... , v_n \} \, y n aristas formadas de la siguiente manera:

A=\{\{v_i , v_{i+1}\}|i= 1, ..., n\} \cup \{v_n , v_1\}

Contenido

Propiedades

Un grafo ciclo es:

2-conexo

En efecto, si tomamos 2 vertices cualquiera, siempre hay 2 caminos distintos (sin vertices comunes a excepción de los vertices extremos) que los conectan. Luego, por el Teorema de Whitney (1932), los ciclos tienen índice de conexión: \kappa \,(C_n)=2.

Los ciclos son también 2-conexo por aristas, en efecto, dado 2 vertices 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: \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 vertices, todos sus grados son iguales a dos: \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

\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

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

Un Grafo ciclo dirigido de longitud 8.

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.

\delta_s (x)= \delta_e (x)= 1 \,


Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Ciclo (desambiguación) — Ciclo Serie de fases por las que pasa un fenómeno periódico hasta que se reproduce una fase anterior. una bicicleta (se usa mucho el término ciclo en los reglamentos de conducción) en literatura: Epanadiplosis o ciclo (figura retórica) Ciclo… …   Wikipedia Español

  • Grafo mediano — El mediano de tres vértices en un grafo mediano. En matemática, y más específicamente en la teoría de grafos, un grafo mediano es un grafo no dirigido en que cualesquiera tres vértices a, b, y c tienen un único mediano. Un mediano es un vértice… …   Wikipedia Español

  • Ciclo euleriano — Un ciclo euleriano es aquel camino que recorre todas las aristas de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde… …   Wikipedia Español

  • Grafo perfecto — El grafo Paley de orden 9, coloreado con tres colores, mostrando un clique de tres vértices. En este grafo y cada uno de sus subgrafos inducidos, el número cromático es igual al número de clique, por lo que es un grafo perfecto. En teoría de… …   Wikipedia Español

  • Grafo plano — Grafos de ejemplo Plano No plano …   Wikipedia Español

  • Grafo regular — En Teoría de grafos, un Grafo regular es un grafo donde cada vértice tiene el mismo grado o valencia. Un Grafo regular con vértices de grado k es llamado Grafo k regular o Grafo regular de grado k. Los Grafos regulares de grado hasta 2 son… …   Wikipedia Español

  • Grafo autocomplementario — El estilo de esta traducción aún no ha sido revisado por terceros. Si eres hispanohablante nativo y no has participado en esta traducción puedes colaborar revisando y adaptando el estilo de ésta u otras traducciones ya acabadas …   Wikipedia Español

  • Ciclo euleriano — Un ciclo euleriano es aquel camino que recorre todos los vértices (nodos) de un grafo pasando una y sólo una vez por cada arco (arista) del grafo y regresando al vértice de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de… …   Enciclopedia Universal

  • Grafo acíclico dirigido — Un DAG simple. En ciencias de la computación y matemáticas un grafo acíclico dirigido (o gráfico dirigido acíclico) conocido como DAG por sus siglas en inglés, es un grafo dirigido que no tiene ciclos; esto significa que para cada vértice v, no… …   Wikipedia Español

  • Problema del ciclo hamiltoniano — Saltar a navegación, búsqueda En teoría de grafos, el Problema del ciclo hamiltoniano y el Problema del camino hamiltoniano tratan de determinar si un ciclo hamiltoniano o un camino hamiltoniano existen en un determinado grafo. Existe una íntima… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”