allcycles

Encontra todos os ciclos simples de um grafo ou dígrafo.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

cycles = allcycles(G)

Descrição

Um ciclo simples é um percurso fechado que nunca visita um nó duas vezes. Em um grafo não direcionado cada ciclo é informado uma só vez, e não uma vez por sentido ou ponto de partida. Em um dígrafo as direções das arestas devem ser seguidas.

O número de ciclos pode crescer muito rápido com o tamanho do grafo, então use em grafos pequenos. cyclebasis fornece um conjunto compacto de ciclos que gera todos os outros.

Argumentos de entrada

G

Um graph ou digraph.

Argumentos de saída

cycles

Cell array. Cada célula guarda os nós de um ciclo, na ordem em que são visitados. Fica vazio quando G não tem ciclos.

Exemplo

Um triângulo com uma cauda

G = graph([1 2 3 3], [2 3 1 4]);
c = allcycles(G);
numel(c)
c{1}

ans = 1
ans = 1×3

     1     2     3

Veja também

cyclebasis hascycles isdag allpaths