gráfico Biconnected - Biconnected graph

Em teoria gráfico , um gráfico biconnected é um ligado e "nonseparable" gráfico , o que significa que se houver um vértice eram para ser removido, o gráfico vai permanecer ligado. Portanto um gráfico biconnected não tem vértices de articulação .

A propriedade de ser 2-ligado é equivalente a biconnectivity, com a ressalva de que o gráfico completo de dois vértices é por vezes considerada como biconnected mas não 2-ligado.

Esta propriedade é especialmente útil na manutenção de um gráfico com uma dupla redundância , para evitar a desconexão mediante a remoção de uma única aresta (ou ligação).

O uso de biconnected gráficos é muito importante no campo das redes (ver fluxo de rede ), por causa desta propriedade de redundância.

Definição

Um biconnected gráfico não dirigida é um gráfico ligado que não é quebrado em partes desconexas excluindo qualquer único vértice (e as suas arestas incidentes).

Um biconnected grafo orientado é uma tal que para quaisquer dois vértices de v e w existem dois caminhos dirigidos a partir de v para W que não têm vértices no outro comum que v e w .

Nonseparable (ou 2-ligados) ou gráficos (blocos), com n nós (sequência A002218 no OEIS )
vértices Número de possibilidades
1 0
2 1
3 1
4 3
5 10
6 56
7 468
8 7123
9 194066
10 9743542
11 900969091
12 153620333545
13 48432939150704
14 28361824488394169
15 30995890806033380784
16 63501635429109597504951
17 244852079292073376010411280
18 1783160594069429925952824734641
19 24603887051350945867492816663958981

Exemplos

  • Um gráfico biconnected em quatro vértices e quatro arestas

  • Um gráfico que não é biconnected. A remoção do vértice x desconectaria do gráfico.

  • Um gráfico biconnected em cinco vértices e seis bordas

  • Um gráfico que não é biconnected. A remoção do vértice x desconectaria do gráfico.

Veja também

Referências

links externos