Gráfico de ciclo

Gráfico de ciclo
VS8{\ Displaystyle C_ {8}}
Clasificación	VSno{\ Displaystyle C_ {n}}
Número de vértices	no{\ Displaystyle n}
Numero de aristas	no{\ Displaystyle n}
Distribución de titulaciones	2-regular
Diámetro	n / 2 si n par ( n - 1) / 2 en caso contrario
Propiedades	Unidad de distancia planar euleriana hamiltoniana Gráfica de Cayley simétrica

Los ciclos de gráficos o n- ciclos forman una familia de gráficos . El gráfico de ciclo se compone de un solo ciclo elemental de longitud n (para ). Es un gráfico conectado no orientado de orden n con n aristas. Es regular 2, es decir, cada uno de sus vértices es de grado 2. VSno{\ Displaystyle C_ {n}}no≥3{\ Displaystyle n \ geq 3}

Terminología

Se utilizan muchos términos para designar el gráfico de ciclo: n- ciclo, polígono y n -gone. El término gráfico cíclico se utiliza a veces, pero es problemático porque normalmente se opone al gráfico acíclico .

Propiedades fundamentales

• Número cromático . El número cromático del ciclo es igual a 3 si n es impar, a 2 en caso contrario. En otras palabras, es bipartito si y solo si n es par.VSno{\ Displaystyle C_ {n}}VSno{\ Displaystyle C_ {n}}
• Conectividad . Por construcción está conectado. Es fácil ver que está conectado por 2 vértices (es decir, deja de estar conectado sólo cuando se le quitan 2 vértices). También está relacionado con 2 aristas .VSno{\ Displaystyle C_ {n}}
• Hamiltonicidad . El único ciclo que contiene es un ciclo hamiltoniano. Por tanto, el gráfico del ciclo es hamiltoniano .VSno{\ Displaystyle C_ {n}}
• Planaridad . es un gráfico plano .VSno{\ Displaystyle C_ {n}}
• Euleriano . Al ser 2-regular, el ciclo es euleriano según el teorema de Euler-Hierholzer.VSno{\ Displaystyle C_ {n}}
• Gráfico de líneas . La gráfica lineal de es isomórfica a .VSno{\ Displaystyle C_ {n}}VSno{\ Displaystyle C_ {n}}

Aspectos algebraicos

El gráfico de ciclo se puede dibujar como un polígono regular con n vértices. Las isometrías de este polígono resultan ser automorfismos de . De aquí se sigue la transitividad de borde y la transitividad superior. es por tanto un gráfico simétrico . Todos sus vértices y aristas juegan el mismo papel en términos de isomorfismo de grafos. VSno{\ Displaystyle C_ {n}}VSno{\ Displaystyle C_ {n}}VSno{\ Displaystyle C_ {n}}

Es fácil ver que solo las isometrías de este polígono son automorfismos válidos de . El grupo de automorfismos del gráfico de ciclo es, por tanto, isomorfo al de las isometrías del polígono regular con n vértices, es decir, el grupo diedro , grupo de orden 2n . VSno{\ Displaystyle C_ {n}}VSno{\ Displaystyle C_ {n}} Dno{\ Displaystyle D_ {n}}

El gráfico de ciclo es un gráfico de Cayley con: VSno{\ Displaystyle C_ {n}}

GRAMO=ZnoZ{\ Displaystyle G = {\ frac {\ mathbb {Z}} {n {\ mathbb {Z}}}}} y S={1,no-1}{\ Displaystyle S = \ {1, n-1 \}}

El polinomio característico de la matriz de adyacencia del gráfico de ciclo es (todas las raíces de las cuales son dobles excepto 2 y posiblemente -2). VSno{\ Displaystyle C_ {n}}∏k=0no-1(X-2porque⁡(2kπ/no)){\ Displaystyle \ prod _ {k = 0} ^ {n-1} (x-2 \ cos (2k \ pi / n))}

Casos particulares

• VS3{\ Displaystyle C_ {3}}es el gráfico triangular .
• VS4{\ Displaystyle C_ {4}}es el gráfico cuadrado, es isomorfo al hipercubo oa la cuadrícula G (2,2) .Q3{\ Displaystyle Q_ {3}}
• VS6{\ Displaystyle C_ {6}}es isomorfo al gráfico de Kneser .KGRAMO3,1{\ Displaystyle KG_ {3,1}}

Galería

• VS3{\ Displaystyle C_ {3}}

• VS4{\ Displaystyle C_ {4}}

• VS5{\ Displaystyle C_ {5}}

• VS6{\ Displaystyle C_ {6}}

Referencias

1. (en) Eric W. Weisstein , "  Cycle Graph  " en MathWorld
2. Kenneth H. Rosen, John G. Michaels. Manual de Matemática Discreta y Combinatoria. Prensa CRC, 2000.
3. En teoría: Personajes y expansión de Luca Trevisan

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">