Relación entre puntos de articulación y el puente de los bordes

Question

¿Cuál es la relación de buques entre los puntos de articulación y puentes de un gráfico.

En concreto, si no hay puntos de articulación de un grafo es necesario que no habrá puente de los bordes.

Answer 1

Supongamos que una gráfica tiene un borde del puente. A continuación, considere uno de sus puntos finales. Mediante la eliminación de ese vértice, también estamos eliminando esa ventaja y, por tanto, la desconexión de la gráfica. Así que una gráfica tiene un borde del puente implica que tiene un punto de articulación.

Tenga en cuenta que esta prueba tiene un defecto menor. No se considera el caso cuando uno de los componentes conectados obtiene después de eliminar el borde tiene un solo vértice. Así que la afirmación anterior no se produce cuando la gráfica está a sólo dos vértices y un borde entre ellos (o si el gráfico está desconectado, este es un componente conectado). De hecho este es el único caso en que la declaración anterior es falso.

Y podemos ver ejemplos sencillos que a la inversa, el gráfico tiene punto de articulación implica que ha borde del puente, no es cierto.