cyclebasis

Um conjunto de ciclos independentes a partir do qual se podem construir todos os ciclos de um grafo.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

cycles = cyclebasis(G)

Descrição

O número de ciclos independentes de um grafo é numedges(G) - numnodes(G) + c, em que c é o número de componentes conexos. cyclebasis devolve essa quantidade de ciclos, cada um formado por uma aresta fora da árvore e pelo caminho da árvore entre suas pontas. Qualquer outro ciclo é uma combinação destes, com as arestas compartilhadas se cancelando.

Um grafo sem ciclos devolve um cell array vazio.

Argumentos de entrada

G

Um graph não direcionado.

Argumentos de saída

cycles

Cell array com uma célula por ciclo da base. Cada célula lista os nós do ciclo, em ordem.

Exemplo

Dois triângulos com uma aresta em comum

G = graph([1 1 2 2 3], [2 3 3 4 4]);
c = cyclebasis(G);
fprintf('%d independent cycles\n', numel(c))

2 independent cycles

Veja também

allcycles hascycles minspantree biconncomp