biconncomp

Componentes biconexos (blocos) de um grafo não direcionado.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

bins = biconncomp(G)

[bins, cut] = biconncomp(G)

Descrição

Um componente biconexo é um conjunto maximal de arestas em que quaisquer duas estão em um ciclo comum, de modo que o componente sobrevive à remoção de qualquer nó. Componentes podem compartilhar um vértice de articulação, mas nunca uma aresta, e por isso os rótulos pertencem a arestas e não a nós.

Uma aresta que não está em nenhum ciclo, como uma ponte, forma um bloco sozinha.

Argumentos de entrada

G

Um graph não direcionado.

Argumentos de saída

bins

Um inteiro por aresta, na ordem de G.Edges. Arestas com o mesmo rótulo estão no mesmo bloco.

cut

Índices dos vértices de articulação (pontos de articulação).

Exemplo

Blocos de um triângulo com cauda

G = graph([1 2 3 3 4 5], [2 3 1 4 5 6]);
[bins, cut] = biconncomp(G);
fprintf('%d blocks\n', max(bins))
disp(cut)

4 blocks
     3     4     5

Veja também

bctree conncomp hascycles cyclebasis