Diferencia entre revisiones de «Vértice de corte»

De Wikipedia, la enciclopedia libre
Contenido eliminado Contenido añadido
Dinamik-bot (discusión · contribs.)
m r2.6.5) (robot Modificado: en:Biconnected component
Ninguna de las acepciones de la palabra "remover" que aparece en el DRAE parece cuajar con el uso dado aquí
Línea 1: Línea 1:
[[Archivo:UndirectedChain.jpg|thumb|120px|Un grafo no dirigido con ''n''=5 vértices y ''n''-2=3 vértices de corte; los vértices de corte son aquellos que no son puntos finales.]]
[[Archivo:UndirectedChain.jpg|thumb|120px|Un grafo no dirigido con ''n''=5 vértices y ''n''-2=3 vértices de corte; los vértices de corte son aquellos que no son puntos finales.]]
[[Archivo:Undirected.svg|thumb|125px|Grafo no dirigido sin vértices de corte.]]
[[Archivo:Undirected.svg|thumb|125px|Grafo no dirigido sin vértices de corte.]]
En [[teoría de grafos]], un '''vértice de corte''' o '''punto de articulación''' es un [[Vértice (teoría de grafos)|vértice]] de un [[grafo]] tal que al removerlo de éste se produce un incremento en el número de [[Componente fuertemente conexo|componentes conexos]]. Si el grafo estaba conectado antes de retirar el vértice, entonces pasará a desconectarse. Cualquier [[grafo conexo]] con un vértice de corte tiene una conectividad de 1.
En [[teoría de grafos]], un '''vértice de corte''' o '''punto de articulación''' es un [[Vértice (teoría de grafos)|vértice]] de un [[grafo]] tal que al eliminarlo de éste se produce un incremento en el número de [[Componente fuertemente conexo|componentes conexos]]. Si el grafo estaba conectado antes de retirar el vértice, entonces pasará a desconectarse. Cualquier [[grafo conexo]] con un vértice de corte tiene una conectividad de 1.


A pesar de que estén bien definidos para grafos dirigidos, los vértices de corte se usan principalmente en los grafos no dirigidos. En general, un grafo conexo, no dirigido y con ''n'' vértices, puede tener no más que ''n''-2 vértices de corte. Naturalmente, un grafo puede no tener ningún vértice de corte.
A pesar de que estén bien definidos para grafos dirigidos, los vértices de corte se usan principalmente en los grafos no dirigidos. En general, un grafo conexo, no dirigido y con ''n'' vértices, puede tener no más que ''n''-2 vértices de corte. Naturalmente, un grafo puede no tener ningún vértice de corte.


Una [[arista de corte]] o puente, es una [[arista (teoría de grafos)|arista]] análoga a un vértice de corte; es decir, una que al removerla incrementa el número de componentes conexos del grafo.
Una [[arista de corte]] o puente, es una [[arista (teoría de grafos)|arista]] análoga a un vértice de corte; es decir, una que al eliminarla incrementa el número de componentes conexos del grafo.


En un [[árbol (teoría de grafos)|árbol]], cada vértice con [[grado (teoría de grafos)|grado]] mayor que 1 es un vértice de corte.
En un [[árbol (teoría de grafos)|árbol]], cada vértice con [[grado (teoría de grafos)|grado]] mayor que 1 es un vértice de corte.
Línea 15: Línea 15:
:a = número de componentes en G (encontrar usando [[Búsqueda en profundidad|DFS]]/[[Búsqueda en anchura|BFS]])
:a = número de componentes en G (encontrar usando [[Búsqueda en profundidad|DFS]]/[[Búsqueda en anchura|BFS]])
:para cada i en V con aristas incidentes
:para cada i en V con aristas incidentes
::remover i de V
::eliminar i de V
::b = número de componentes en G con i removido
::b = número de componentes en G con i removido
::si b > a
::si b > a

Revisión del 22:14 17 oct 2011

Un grafo no dirigido con n=5 vértices y n-2=3 vértices de corte; los vértices de corte son aquellos que no son puntos finales.
Grafo no dirigido sin vértices de corte.

En teoría de grafos, un vértice de corte o punto de articulación es un vértice de un grafo tal que al eliminarlo de éste se produce un incremento en el número de componentes conexos. Si el grafo estaba conectado antes de retirar el vértice, entonces pasará a desconectarse. Cualquier grafo conexo con un vértice de corte tiene una conectividad de 1.

A pesar de que estén bien definidos para grafos dirigidos, los vértices de corte se usan principalmente en los grafos no dirigidos. En general, un grafo conexo, no dirigido y con n vértices, puede tener no más que n-2 vértices de corte. Naturalmente, un grafo puede no tener ningún vértice de corte.

Una arista de corte o puente, es una arista análoga a un vértice de corte; es decir, una que al eliminarla incrementa el número de componentes conexos del grafo.

En un árbol, cada vértice con grado mayor que 1 es un vértice de corte.

Buscando vértices de corte

Un algoritmo trivial de complejidad O(nm) es el siguiente:

a = número de componentes en G (encontrar usando DFS/BFS)
para cada i en V con aristas incidentes
eliminar i de V
b = número de componentes en G con i removido
si b > a
i es un vértice de corte
restaurar i

Existe un algoritmo con tiempo de ejecución de orden O(n+m) que utiliza la búsqueda en profundidad.

Véase también