CUT VERTEX

An undirected graph with ''n''=5 vertices and ''n''-2=3 cut vertices; the cut vertices are those not on either end

In mathematics and computer science, a 'cut vertex' or 'articulation point' is a vertex of a graph such that removal of the vertex causes an increase in the number of connected components. If the graph was connected before the removal of the vertex, it will be disconnected afterwards. Any connected graph with a cut vertex has a connectivity of 1.
An undirected graph with no cut vertices

While well-defined for directed graphs, cut vertices are primarily used in undirected graphs. In general, a connected, undirected graph with ''n'' vertices can have no more than ''n''-2 cut vertices. Naturally, a graph may have no cut vertices at all.
A bridge is an edge analogous to a cut vertex; that is, the removal of a bridge increases the number of connected components of the graph.
In a tree, every vertex with degree greater than 1 is a cut vertex.





Contents
Finding Cut vertices
See also

Finding Cut vertices


A trivial ''O''(''nm'') algorithm is as follows:
:a = number of components in G (found using DFS/BFS)
:for each i in V with incident edges

::Remove i from V
::b = number of components in G with i removed
::if b > a
:::i is a cut vertex
::restore i
An algorithm with the much better running time ''O''(''n''+''m'') is known using depth-first search.

See also



★ Connectivity (graph theory)

This article provided by Wikipedia. To edit the contents of this article, click here for original source.

psst.. try this: add to faves
©2009 TripAtlas.com