Gráfico de ciclo - Cycle graph
| Gráfico de ciclo | |
|---|---|
 Um gráfico de ciclo de comprimento 6
| |
| Vértices | n |
| Arestas | n |
| Cilha | n |
| Automorfismos | 2 n ( D n ) |
| Número cromático | 3 se n for ímpar 2 caso contrário |
| Índice cromático | 3 se n for ímpar 2 caso contrário |
| Espectro | {2 cos (2 k π / n ); k = 1, ..., n } |
| Propriedades |
2-regular Vértice-transitivo Edge-transitivo Unidade de distância Hamiltoniana Euleriana |
| Notação | |
| Tabela de gráficos e parâmetros | |
Na teoria dos grafos , um gráfico de ciclo ou gráfico circular é um gráfico que consiste em um único ciclo , ou seja, algum número de vértices (pelo menos 3, se o gráfico for simples ) conectados em uma cadeia fechada. O gráfico do ciclo com n vértices é denominado C n . O número de vértices em C n é igual ao número de arestas , e cada vértice tem grau 2; isto é, cada vértice tem exatamente duas arestas incidentes com ele.
Terminologia
Existem muitos sinônimos para "gráfico de ciclo". Incluem gráfico de ciclo simples e gráfico cíclico , embora o último termo seja menos usado, porque também pode se referir a gráficos que simplesmente não são acíclicos . Entre os teóricos dos grafos, ciclo , polígono ou n -gon também são usados com frequência. O termo n -ciclo às vezes é usado em outros ambientes.
Um ciclo com um número par de vértices é chamado de ciclo par ; um ciclo com um número ímpar de vértices é chamado de ciclo ímpar .
Propriedades
Um gráfico de ciclo é:
- Colorível de 2 arestas , se e somente se tiver um número par de vértices
- 2-regular
- 2 vértices coloríveis , se e somente se tiver um número par de vértices. De maneira mais geral, um gráfico é bipartido se e somente se não tiver ciclos ímpares ( Kőnig , 1936).
- Conectado
- Euleriana
- Hamiltoniano
- Um gráfico de distância unitária
Além do que, além do mais:
- Como os gráficos de ciclo podem ser desenhados como polígonos regulares , as simetrias de um n- ciclo são iguais às de um polígono regular com n lados, o grupo diédrico de ordem 2 n . Em particular, existem simetrias levando qualquer vértice a qualquer outro vértice, e qualquer aresta a qualquer outra aresta, então o n- ciclo é um gráfico simétrico .
Da mesma forma que os gráficos platônicos , os gráficos de ciclo formam os esqueletos do dihedra . Seus duais são os gráficos dipolares , que formam os esqueletos do hosoedra .
Gráfico de ciclo direcionado
Um gráfico de ciclo direcionado é uma versão direcionada de um gráfico de ciclo, com todas as arestas sendo orientadas na mesma direção.
Em um gráfico direcionado , um conjunto de arestas que contém pelo menos uma aresta (ou arco ) de cada ciclo direcionado é chamado de conjunto de arco de feedback . Da mesma forma, um conjunto de vértices contendo pelo menos um vértice de cada ciclo direcionado é chamado de conjunto de vértices de feedback .
Um gráfico de ciclo direcionado tem grau 1 uniforme e grau 1 externo uniforme.
Os gráficos de ciclo direcionado são gráficos de Cayley para grupos cíclicos (ver, por exemplo, Trevisan).
Veja também
Referências
links externos
- Weisstein, Eric W. "Cycle Graph" . MathWorld .(discussão de ambos os gráficos de ciclo 2 regulares e o conceito teórico de grupo de diagramas de ciclo )
- Luca Trevisan , Personagens e Expansão .