Ciclo (teoria dos gráficos) - Cycle (graph theory)

Um gráfico com arestas coloridas para ilustrar o caminho HAB (verde), caminho fechado ou caminho com um vértice repetido BDEFDCB (azul) e um ciclo sem aresta repetida ou vértice HDGH (vermelho).

Na teoria dos grafos , um ciclo em um gráfico é uma trilha não vazia na qual os únicos vértices repetidos são o primeiro e o último vértices. Um ciclo direcionado em um gráfico direcionado é uma trilha direcionada não vazia na qual os únicos vértices repetidos são o primeiro e o último vértices.

Um gráfico sem ciclos é denominado gráfico acíclico . Um gráfico direcionado sem ciclos direcionados é chamado de gráfico acíclico direcionado . Um gráfico conectado sem ciclos é chamado de árvore .

Definições

Circuito, ciclo

  • Um circuito é uma trilha não vazia na qual o primeiro vértice é igual ao último vértice ( trilha fechada ).
Seja G = ( V , E , ϕ ) um gráfico. Um circuito é uma trilha não vazia ( e 1 , e 2 ,…, e n ) com uma sequência de vértices ( v 1 , v 2 ,…, v n , v 1 ) .
  • Um ciclo ou circuito simples é um circuito em que o único vértice repetido é o primeiro / último vértice.
  • O comprimento de um circuito ou ciclo é o número de arestas envolvidas.

Circuito direcionado, ciclo

  • Um circuito direcionado é uma trilha direcionada não vazia na qual o primeiro vértice é igual ao último.
Seja G = ( V , E , ϕ ) um gráfico direcionado. Um circuito direcionado é uma trilha direcionada não vazia ( e 1 , e 2 ,…, e n ) com uma sequência de vértices ( v 1 , v 2 ,…, v n , v 1 ) .
  • Um ciclo direcionado ou circuito direcionado simples é um circuito direcionado no qual o único vértice repetido é o primeiro / último vértice.

Ciclos sem acordes

Neste gráfico, o ciclo verde (ABCDEFA) não tem cordas, enquanto o ciclo vermelho (GHIJKLG) não. Isso ocorre porque a borda KI é um acorde.

Um ciclo sem corda em um gráfico, também chamado de furo ou ciclo induzido, é um ciclo tal que não há dois vértices do ciclo conectados por uma aresta que não pertença ao ciclo. Um anti-furo é o complemento de um furo gráfico. Ciclos sem corda podem ser usados ​​para caracterizar gráficos perfeitos : pelo teorema do gráfico perfeito forte , um gráfico é perfeito se e somente se nenhum de seus orifícios ou anti-furos tiver um número ímpar de vértices maior que três. Um gráfico de cordas , um tipo especial de gráfico perfeito, não tem buracos de nenhum tamanho maior que três.

A circunferência de um gráfico é o comprimento de seu ciclo mais curto; este ciclo é necessariamente sem acordes. As gaiolas são definidas como os menores gráficos regulares com determinadas combinações de grau e circunferência.

Um ciclo periférico é um ciclo em um gráfico com a propriedade de que cada duas arestas que não estão no ciclo podem ser conectadas por um caminho cujos vértices internos evitam o ciclo. Em um gráfico que não é formado pela adição de uma aresta a um ciclo, um ciclo periférico deve ser um ciclo induzido.

Ciclo de espaço

O termo ciclo também pode se referir a um elemento do espaço do ciclo de um gráfico. Existem muitos espaços de ciclo, um para cada campo de coeficiente ou anel. O mais comum é o espaço binário do ciclo (geralmente chamado simplesmente de espaço do ciclo ), que consiste nos conjuntos de arestas que têm graus pares em cada vértice; ele forma um espaço vetorial sobre o campo de dois elementos . Pelo teorema de Veblen , cada elemento do espaço do ciclo pode ser formado como uma união de aresta disjunta de ciclos simples. Uma base de ciclo do gráfico é um conjunto de ciclos simples que formam a base do espaço do ciclo.

Usando ideias da topologia algébrica , o espaço do ciclo binário generaliza para espaços vetoriais ou módulos sobre outros anéis , como inteiros, números racionais ou reais, etc.

Detecção de ciclo

A existência de um ciclo em gráficos direcionados e não direcionados pode ser determinada se a pesquisa em profundidade (DFS) encontra uma aresta que aponta para um ancestral do vértice atual (ela contém uma aresta posterior ). Todas as bordas traseiras que o DFS salta fazem parte dos ciclos. Em um gráfico não direcionado, a aresta para o pai de um nó não deve ser contada como uma aresta posterior, mas encontrar qualquer outro vértice já visitado indicará uma aresta posterior. No caso de gráficos não direcionados, apenas o tempo O ( n ) é necessário para encontrar um ciclo em um gráfico de n- vértices, uma vez que no máximo n  - 1 arestas podem ser arestas de árvores.

Muitos algoritmos de ordenação topológica também detectarão ciclos, uma vez que esses são obstáculos para a existência de ordem topológica. Além disso, se um gráfico direcionado foi dividido em componentes fortemente conectados , os ciclos existem apenas dentro dos componentes e não entre eles, uma vez que os ciclos são fortemente conectados.

Para gráficos direcionados, algoritmos baseados em mensagens distribuídas podem ser usados. Esses algoritmos baseiam-se na ideia de que uma mensagem enviada por um vértice em um ciclo retornará a si mesma. Os algoritmos de detecção de ciclo distribuído são úteis para processar gráficos em grande escala usando um sistema de processamento de gráfico distribuído em um cluster de computador (ou supercomputador).

As aplicações de detecção de ciclo incluem o uso de gráficos de espera para detectar deadlocks em sistemas concorrentes.

Gráficos de cobertura por ciclos

Em seu artigo de 1736 sobre as Sete Pontes de Königsberg , amplamente considerado o nascimento da teoria dos grafos, Leonhard Euler provou que, para um gráfico não direcionado finito ter um passeio fechado que visita cada aresta exatamente uma vez, é necessário e suficiente que ele ser conectado, exceto para vértices isolados (ou seja, todas as arestas estão contidas em um componente) e ter grau par em cada vértice. A caracterização correspondente para a existência de um passeio fechado visitando cada aresta exatamente uma vez em um grafo direcionado é que o grafo está fortemente conectado e tem um número igual de arestas de entrada e saída em cada vértice. Em ambos os casos, a caminhada resultante é conhecida como ciclo de Euler ou passeio de Euler. Se um grafo finito não direcionado tem grau par em cada um de seus vértices, independentemente de estar conectado, então é possível encontrar um conjunto de ciclos simples que juntos cobrem cada aresta exatamente uma vez: este é o teorema de Veblen . Quando um grafo conectado não atende às condições do teorema de Euler, um passeio fechado de comprimento mínimo cobrindo cada aresta pelo menos uma vez pode ser encontrado em tempo polinomial resolvendo o problema de inspeção de rota .

O problema de encontrar um único ciclo simples que cubra cada vértice exatamente uma vez, em vez de cobrir as arestas, é muito mais difícil. Esse ciclo é conhecido como ciclo hamiltoniano e determinar se ele existe é NP-completo . Muitas pesquisas foram publicadas sobre classes de gráficos que podem conter ciclos hamiltonianos; um exemplo é o teorema de Ore de que um ciclo hamiltoniano pode sempre ser encontrado em um gráfico para o qual cada par de vértices não adjacentes tem graus que somam pelo menos o número total de vértices no gráfico.

A conjectura da cobertura dupla do ciclo afirma que, para cada gráfico sem ponte , existe um multiconjunto de ciclos simples que cobre cada aresta do gráfico exatamente duas vezes. Provar que isso é verdade (ou encontrar um contra-exemplo) permanece um problema em aberto.

Classes de gráficos definidas por ciclos

Várias classes importantes de gráficos podem ser definidas ou caracterizadas por seus ciclos. Esses incluem:

Veja também

Referências