Cut vertex

Cut vertex

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.

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.

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.

Cut vertices in trees

A vertex v of a tree G is a cut vertex of G if and only if the degree of the vertex is greater than 1.

See also

*Connectivity (graph theory)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Vertex (graph theory) — For other uses, see Vertex (disambiguation). A graph with 6 vertices and 7 edges where the vertex number 6 on the far left is a leaf vertex or a pendant vertex In graph theory, a vertex (plural vertices) or node is the fundamental unit out of… …   Wikipedia

  • Vertex pipeline — The function of the vertex pipeline in any GPU is to take geometry data (usually supplied as vector points), work with it if needed with either fixed function processes (earlier DirectX), or a vertex shader program (later DirectX), and create all …   Wikipedia

  • Maximum cut — A maximum cut. For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max cut problem. The problem can be stated simply as follows. One wants a subset… …   Wikipedia

  • Max-flow min-cut theorem — In optimization theory, the max flow min cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity which when removed in a specific way from the network causes the… …   Wikipedia

  • Maximal cut — For a graph, a maximal cut is a cut with the size not smaller than the size of any other cut. The problem of finding a maximal cut is a graph is known as the max cut problem.Max cut problemThe max cut problem is one of Karp s 21 NP complete… …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

Share the article and excerpts

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