Punto de articulación

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de julio de 2021; la verificación requiere 1 edición .

Un punto de articulación en la teoría de grafos es un vértice de un gráfico , al eliminarlo, aumenta el número de componentes conectados . Los términos "vértice separador" y "bisagra" también se utilizan para denotar este concepto.

Definiciones

Un vértice de un grafo se llama bisagra si el subgrafo obtenido del grafo quitando el vértice y todas las aristas incidentes en él consta de más componentes conectadas que el grafo original . $v$ $GRAMO$ $G_{1}$ $GRAMO$ $v$ $GRAMO$

La noción de biconectividad también está relacionada con la noción de bisagra. Un grafo doblemente conexo es un grafo conexo que no contiene bisagras. El componente biconectado es el subgrafo doblemente conectado máximo (por inclusión) del gráfico original. Los componentes biconectados a veces se denominan bloques.

El borde análogo de la bisagra es el puente . Un puente es un borde de un gráfico cuya eliminación da como resultado un aumento en el número de componentes conectados en el gráfico.

Encontrar bisagras

Una solución eficiente al problema de encontrar todas las bisagras de un gráfico se basa en el algoritmo de búsqueda primero en profundidad .

Sea dada una gráfica . Denote por el conjunto de todos los vértices del gráfico adyacentes a . Supongamos que hemos escaneado el gráfico en profundidad, comenzando desde algún vértice arbitrario. Enumeramos todos los vértices del gráfico en el orden en que los ingresamos y asignamos un número correspondiente a cada vértice . Si primero llegamos al vértice desde el vértice , entonces llamaremos al vértice el descendiente de y el antepasado de . El conjunto de todos los descendientes de un vértice se denota por . Denotar por el número mínimo entre todos los vértices adyacentes y con esos vértices a los que llegamos a lo largo del camino que pasa . $GRAMO$ $Adj(v)$ $v$ $v$ ${\ estilo de visualización n (v)}$ $tu$ $v$ $tu$ $v$ $v$ $tu$ $v$ $Ch(v)$ ${\ estilo de visualización bajo (v)}$ $v$ $v$

Es claro que el valor se puede calcular recursivamente, directamente en el proceso de recorrido en profundidad: si en el momento en que se está considerando el vértice , y es imposible pasar de él a un vértice que aún no ha sido visitado (es decir, necesita volver al antepasado , o detener el recorrido, si es el vértice inicial), entonces para todos sus descendientes ya se ha calculado y, por lo tanto, para él, es posible realizar los cálculos correspondientes utilizando la fórmula ${\ estilo de visualización bajo (v)}$ $v$ $v$ $v$ ${\ estilo de visualización bajo}$

$Low(v)=\min \left\{\min_{x\in Ch(v)}Low(x),\min_{y\in Adj(v)/Ch(v)}n( y)\derecho\}.$

Conociendo el valor de todos los vértices del gráfico, es posible determinar de forma única todas sus bisagras de acuerdo con las siguientes dos reglas: ${\ estilo de visualización bajo (v)}$

El vértice inicial (es decir, desde el que comenzamos el recorrido) es una bisagra si y solo si tiene más de un hijo.
Un vértice que no sea el vértice inicial es una bisagra si y solo si tiene un hijo u tal que . $v$ $Bajo(u)=n(v)$

Como ejemplo, considere la aplicación del algoritmo descrito al gráfico que se muestra en la figura de la derecha. Los números que marcan los vértices corresponden a una de las posibles variantes de la búsqueda en profundidad. En este orden, cada uno de los vértices tiene exactamente un hijo, excepto el vértice 6, que no tiene hijos. El vértice inicial 1 tiene un solo hijo, por lo que no es una bisagra. Para los vértices restantes, calculamos los valores de la función que nos interesa:

$Bajo(6)=5,Bajo(5)=2,Bajo(4)=2,Bajo(3)=2,Bajo(2)=1$ .

El vértice 2 tiene un hijo 3 y el 5 tiene un hijo 6; en ambos casos, se cumple la relación deseada . Por lo tanto, 2 y 5 son bisagras. No hay otras bisagras en este gráfico. $Bajo(u)=n(v)$

Véase también

Componente de conectividad de un gráfico

Literatura

V. E. Alekseev, V. A. Talanov. Gráficos y algoritmos. Estructuras de datos. Modelos de computación. — M. : BINOM. Laboratorio de conocimiento, 2006. - ISBN 5-94774-543-7 .