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 even for directed graphs, cut vertices are primarily used in undirected graphs.

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • 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 even 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.
  • 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 removerlo 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 removerla 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.
  • Punkt artykulacji (przegub, wierzchołek rozcinający, wierzchołek rozdzielający, wierzchołek rozspajający) – wierzchołek grafu spójnego, którego usunięcie z grafu rozspójnia go. Według innej definicji jest to taki wierzchołek, którego usunięcie zwiększa liczbę spójnych składowych grafu. Zobacz też: most (teoria grafów)
dbpprop:hasPhotoCollection
dbpprop:reference
rdfs:comment
  • 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 even for directed graphs, cut vertices are primarily used in undirected graphs.
  • 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 removerlo 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.
  • Punkt artykulacji (przegub, wierzchołek rozcinający, wierzchołek rozdzielający, wierzchołek rozspajający) – wierzchołek grafu spójnego, którego usunięcie z grafu rozspójnia go. Według innej definicji jest to taki wierzchołek, którego usunięcie zwiększa liczbę spójnych składowych grafu. Zobacz też: most (teoria grafów)
rdfs:label
  • Cut vertex
  • Vértice de corte
  • Punkt artykulacji
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is dbpprop:redirect of