Vértice de corte

Vértice de corte
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 eliminado
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


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Vértice (teoría de grafos) — Para otros usos de este término, véase vértice. Un grafo con 6 vértices y 7 aristas. En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de… …   Wikipedia Español

  • Arista de corte — Saltar a navegación, búsqueda Un grafo con 6 aristas de corte (marcadas en rojo). En teoría de grafos, un puente, arista de corte o istmo es una arista que al eliminarse de un grafo incrementa el número de componentes cone …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Punto de articulación — Saltar a navegación, búsqueda Para el punto de articulación en un grafo, véase Vértice de corte. Puntos de articulación (activos y pasivos):1. Exolabial, 2. Endolabial, 3. Dental, 4. Alveolar, 5. Postalveolar, 6. Prepalatal, 7. Palatal, 8. Vela …   Wikipedia Español

  • Función cuadrática — En matemáticas, una función cuadrática o función de segundo grado es una función polinómica de grado dos definida como: Gráficas de funciones cuadráticas. en donde a, b y c son números reales (constantes) y a es …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • Controversia de delimitación marítima entre Chile y el Perú — Mapa que destaca la zona o área en controversia, con forma de trapecio, a partir de la intersección de las líneas de base del Perú y Chile. El área contigua se ha denominado Triángulo Exterior en el Perú. La controversia de delimitación marítima… …   Wikipedia Español

  • Esfericón — Saltar a navegación, búsqueda Sólido aproximado a la forma de un Esfericón …   Wikipedia Español

  • Ángulo — (Del lat. angulus, rincón.) ► sustantivo masculino 1 GEOMETRÍA Porción de plano o espacio limitado por dos rectas o por dos planos que se cortan. 2 Encuentro de dos paredes o superficies: ■ en el ángulo oscuro del salón instaló una anaquelería.… …   Enciclopedia Universal

  • Parábola (matemática) — Saltar a navegación, búsqueda Para otros usos de este término, véase parábola. Secciones cónicas …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”