bctree

Árvore de blocos e articulações de um grafo não direcionado.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

T = bctree(G)

Descrição

Um bloco é um pedaço maximal do grafo que continua conexo se qualquer nó isolado for removido. Um vértice de articulação é um nó cuja remoção desconecta o grafo. Colar os blocos pelas suas articulações dá uma árvore (uma floresta se G for desconexo), que é a árvore de blocos e articulações.

A árvore mostra de relance onde uma rede é frágil: cada articulação é um ponto único de falha.

Argumentos de entrada

G

Um graph não direcionado.

Argumentos de saída

T

Um grafo com um nó para cada componente biconexo (bloco) e um para cada vértice de articulação. Cada articulação é ligada aos blocos que a contêm.

map

Segunda saída opcional que relaciona os nós de G a nós de T.

Exemplo

Triângulo com uma corrente

G = graph([1 2 3 3 4 5], [2 3 1 4 5 6]);
T = bctree(G);
fprintf('%d nodes, %d edges\n', numnodes(T), numedges(T))

7 nodes, 6 edges

Veja também

biconncomp conncomp minspantree graph