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	${\displaystyle C_{n}}$

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 C_n. O número de vértices em um C_n 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

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

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

Um grafo ciclo dirigido de comprimento 8

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

• 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.

Ver também

• Grafo nulo
• Grafo caminho
• Grafo completo
• Grafo bipartido completo