Grafo ciclo
| Grafo ciclo | |
|---|---|
 Um grafo ciclo de comprimento 6 | |
| vértices | n |
| arestas | n |
| Cintura | n |
| Automorfismos | 2n (Dn) |
| Número cromático | 3 se n é ímpar 2 se n é par |
| Índice cromático | 3 se n é ímpar 2 se n é par |
| Propriedades | 2-regular vértice-transitivo aresta-transitivo grafo distância-unidade Euleriano Hamiltoniano |
| Notação | |
Em teoria dos grafos um grafo ciclo ou grafo circular é um grafo que consiste de um único ciclo, ou em outras palavras, um número de vértices´ conectados em uma rede fechada. O grafo ciclo com n vértices é chamado Cn. O número de vértices em um Cn se iguala ao número de arestas, e cada vértice tem grau 2; isto é, cada vértice tem exatamente duas arestas incidentes a ele.
Terminologia
[editar | editar código-fonte]Há muitos sinônimos para "grafo ciclo". Estes incluem grafo ciclo simples e grafo cíclico, embora o último termo seja utilizado com menos freqüência, pois ele também pode se referir a grafos que são meramente não acíclicos. Entre os teóricos de grafos, ciclo, polígono, ou n-gono são também frequentemente utilizados. 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
[editar | editar código-fonte]Um grafo ciclo é:
- Conectado
- 2-regular
- Euleriano
- Hamiltoniano
- 2-vértices colorível, se e somente se ele tiver um número par de vértices. Mais genericamente, um grafo é bipartido se e somente se não tem ciclos ímpares (Kőnig, 1936).
- 2-arestas colorível, se e somente se ele tiver um número par de vértices
- 3-vértices colorível e 3-arestas colorível, para quelquer número de vértices
- Um grafo distância-unidade
Além disso:
- Como os grafos ciclo podem ser desenhados como polígonos regulares, as simetrias de um n-ciclo são as mesmas de um polígono regular com n lados, o grupo diedro de ordem 2n. Em particular, existem simetrias tomando qualquer vértice para qualquer outro vértice, e qualquer aresta a qualquer outra aresta, de modo que o n-ciclo é um grafo simétrico.
Grafo ciclo dirigido
[editar | editar código-fonte]
Um grafo ciclo dirigido é uma versão orientada de um grafo ciclo, com todas as arestas sendo orientadas na mesma direção.
Em um grafo dirigido, um conjunto de arestas que contém pelo menos uma aresta (ou arco) de cada ciclo dirigido é chamado um conjunto de arcos de retroalimentação (feedback arc set). Da mesma forma, um conjunto de vértices que contenha pelo menos um vértice de cada ciclo dirigido é chamado de conjunto de vértices de retroalimentação (feedback vertex set).
Um grafo ciclo dirigido tem graus de entrada uniformes 1 e graus de saída uniformes 1.
Grafos ciclo dirigidos são os grafos de Cayley para grupos cíclicos (ver por exemplo Trevisan).
Ligações externas
[editar | editar código-fonte]- Weisstein, Eric W. «Cycle Graph». MathWorld (em inglês) (discussão de ambos os grafos ciclo 2-regular e do conceito do grupo de teoria dos diagrams de ciclo)
- Luca Trevisan, Personagens e Expansão.