Gráfico de ciclo

Gráfico de ciclo
VS8{\ displaystyle C_ {8}}
Avaliação	VSnão{\ displaystyle C_ {n}}
Número de vértices	não{\ displaystyle n}
Número de arestas	não{\ displaystyle n}
Distribuição de graus	2-regular
Diâmetro	n / 2 se n par ( n - 1) / 2 caso contrário
Propriedades	Hamiltoniano Euleriano Planar Distância-unidade Symmetric Cayley gráfico

Os ciclos de gráficos ou n -define formam uma família de gráficos . O gráfico do ciclo é composto de um único ciclo elementar de comprimento n (para ). É um gráfico conectado não orientado de ordem n com n arestas. É 2-regular, ou seja, cada um de seus vértices é de grau 2. VSnão{\ displaystyle C_ {n}}não≥3{\ displaystyle n \ geq 3}

Terminologia

Muitos termos são utilizados para designar o gráfico de ciclo: N -Ciclo, polígono e n -gone. O termo gráfico cíclico é algumas vezes usado, mas é problemático porque normalmente se opõe a gráfico acíclico .

Propriedades fundamentais

• Número cromático . O número cromático do ciclo é igual a 3 se n for ímpar, a 2 caso contrário. Em outras palavras, é bipartido se e somente se n for par.VSnão{\ displaystyle C_ {n}}VSnão{\ displaystyle C_ {n}}
• Conectividade . Por construção está conectado. É fácil ver que ele está conectado a 2 vértices (ou seja, ele deixa de estar conectado apenas quando 2 vértices são removidos dele). Ele também é conectado por 2 bordas .VSnão{\ displaystyle C_ {n}}
• Hamiltonicidade . O único ciclo contido é um ciclo hamiltoniano. O gráfico do ciclo é, portanto, hamiltoniano .VSnão{\ displaystyle C_ {n}}
• Planaridade . é um gráfico planar .VSnão{\ displaystyle C_ {n}}
• Eulerian . Sendo 2-regular, o ciclo é Euleriano pelo teorema de Euler-Hierholzer.VSnão{\ displaystyle C_ {n}}
• Gráfico de linha . O gráfico de linha de é isomórfico a .VSnão{\ displaystyle C_ {n}}VSnão{\ displaystyle C_ {n}}

Aspectos algébricos

O gráfico do ciclo pode ser desenhado como um polígono regular com n vértices. As isometrias desse polígono, então, acabam sendo automorfismos de . Disto segue a transitividade de borda e a transitividade de topo. é, portanto, um gráfico simétrico . Todos os seus vértices e arestas desempenham a mesma função em termos de isomorfismo de grafos. VSnão{\ displaystyle C_ {n}}VSnão{\ displaystyle C_ {n}}VSnão{\ displaystyle C_ {n}}

É fácil ver que apenas as isometrias desse polígono são automorfismos válidos de . O grupo de automorfismos do gráfico do ciclo é, portanto, isomórfico ao das isometrias do polígono regular com n vértices, ou seja, o grupo diédrico , grupo de ordem 2n . VSnão{\ displaystyle C_ {n}}VSnão{\ displaystyle C_ {n}} Dnão{\ displaystyle D_ {n}}

O gráfico do ciclo é um gráfico de Cayley com: VSnão{\ displaystyle C_ {n}}

G=ZnãoZ{\ displaystyle G = {\ frac {\ mathbb {Z}} {n {\ mathbb {Z}}}}} e S={1,não-1}{\ displaystyle S = \ {1, n-1 \}}

O polinômio característico da matriz de adjacência do gráfico de ciclo é (todas as raízes são duplas, exceto 2 e possivelmente -2). VSnão{\ displaystyle C_ {n}}∏k=0não-1(x-2porque⁡(2kπ/não)){\ displaystyle \ prod _ {k = 0} ^ {n-1} (x-2 \ cos (2k \ pi / n))}

Casos especiais

• VS3{\ displaystyle C_ {3}}é o gráfico do triângulo .
• VS4{\ displaystyle C_ {4}}é o gráfico quadrado, é isomorfo ao hipercubo ou à grade G (2,2) .Q3{\ displaystyle Q_ {3}}
• VS6{\ displaystyle C_ {6}}é isomórfico ao gráfico de Kneser .KG3,1{\ displaystyle KG_ {3,1}}

Galeria

• VS3{\ displaystyle C_ {3}}

• VS4{\ displaystyle C_ {4}}

• VS5{\ displaystyle C_ {5}}

• VS6{\ displaystyle C_ {6}}

Referências

1. (em) Eric W. Weisstein , "  Cycle Graph  " on MathWorld
2. Kenneth H. Rosen, John G. Michaels. Handbook of Discrete and Combinatorial Mathematics. CRC Press, 2000.
3. Em teoria: Personagens e Expansão 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;">