En la teoría de grafos , un gráfico biconexas es un "no separable" conectado y gráfico , lo que significa que si cualquier vértice iban a ser eliminado, el gráfico permanecerá conectado. Por lo tanto, un gráfico biconectado no tiene vértices de articulación .
La propiedad de estar 2 conectados es equivalente a la biconnectividad, excepto que la gráfica completa de dos vértices generalmente no se considera como 2 conectados.
Esta propiedad es especialmente útil para mantener un gráfico con una redundancia doble , para evitar la desconexión al eliminar un solo borde (o conexión).
El uso de gráficos biconectados es muy importante en el campo de las redes (ver Flujo de red ), debido a esta propiedad de redundancia.
Definición
A biconexas grafo no dirigido es un gráfico conectado que no se rompe en trozos desconectados mediante la supresión de cualquier vértice único (y sus bordes incidentes).
A biconexas gráfico dirigido es uno de tal manera que para cualquier par de vértices v y w hay dos caminos dirigido desde v a w que no tienen vértices en común distinta v y w .
Vértices | Numero de posibilidades |
---|---|
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 |
dieciséis | 63501635429109597504951 |
17 | 244852079292073376010411280 |
18 | 1783160594069429925952824734641 |
19 | 24603887051350945867492816663958981 |
Ejemplos de
Un gráfico biconectado en cuatro vértices y cuatro bordes
Un gráfico que no está biconectado. La eliminación del vértice x desconectaría la gráfica.
Un gráfico biconectado en cinco vértices y seis aristas.
Un gráfico que no está biconectado. La eliminación del vértice x desconectaría la gráfica.
Ver también
Referencias
- Eric W. Weisstein. "Gráfico biconectado". De MathWorld — Un recurso web de Wolfram. http://mathworld.wolfram.com/BiconnectedGraph.html
- Paul E. Black, "gráfico biconnectado", en Dictionary of Algorithms and Data Structures [en línea], Paul E. Black, ed., Instituto Nacional de Estándares y Tecnología de EE. UU. 17 de diciembre de 2004. (consultado HOY) Disponible en: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html
enlaces externos
- El árbol de la implementación de Java de componentes biconectados en la biblioteca jBPT (ver clase BCTree).