Grafo ciclo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo ciclo
Undirected 6 cycle.svg

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 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 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 é:

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 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[editar | editar código-fonte]

Ver também[editar | editar código-fonte]