hascycles

Testa se um grafo ou dígrafo contém um ciclo.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

tf = hascycles(G)

Descrição

Em um grafo não direcionado existe ciclo exatamente quando algum componente conexo tem pelo menos tantas arestas quanto nós, isto é, quando o grafo não é uma floresta. Em um dígrafo as arestas devem ser seguidas no seu sentido, então um dígrafo sem ciclos é um DAG e isdag é o teste oposto.

Argumentos de entrada

G

Um graph ou digraph.

Argumentos de saída

tf

Escalar lógico.

Exemplo

Caminho contra triângulo

hascycles(graph([1 2], [2 3]))
hascycles(graph([1 2 3], [2 3 1]))
hascycles(digraph([1 2], [2 3]))

ans = logical
   0
ans = logical
   1
ans = logical
   0

Veja também

isdag allcycles cyclebasis conncomp