| dbo:abstract
|
- In der Graphentheorie bezeichnet ein Gelenkpunkt, Artikulationspunkt, Artikulation oder Schnittknoten einen Knoten eines Graphen, dessen Entfernen die Anzahl der zusammenhängenden Teilgraphen erhöhen würde. Wenn der Graph vor dem Entfernen des Knotens zusammenhängend war, ist er danach unzusammenhängend. Ein Gelenkpunkt ist ein Spezialfall eines Trenners. Der Begriff des Gelenkpunkts ist auch für gerichtete Graphen wohldefiniert, wird aber hauptsächlich für ungerichtete Graphen verwendet. Grundsätzlich kann ein zusammenhängender ungerichteter Graph mit n Knoten nicht mehr als n-2 Gelenkpunkte besitzen. Eine Brücke ist eine Kante analog zu einem Gelenkpunkt; das heißt, das Entfernen der Brücke erhöht die Anzahl der zusammenhängenden Teilgraphen. (de)
- In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components. (en)
- En teoría de grafos, un vértice de corte, nodo de corte, punto de corte o punto de articulación es un vértice de un grafo tal que al eliminarlo de este 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. En un árbol, cada vértice con grado mayor que 1 es un vértice de corte. El concepto de vértice de corte se puede generalizar a un conjunto de vértices. Así, un conjunto de corte es un conjunto de vértices necesario para mantener la conexión de un grafo. Un corte de nodos-k es un conjunto de corte de k vértices. Por lo tanto, un vértice de corte es un corte de nodos-1. Análogamente, una arista de corte o puente, es una arista que al eliminarla incrementa el número de componentes conexos del grafo. El grado de conectividad de un grafo se puede calcular en términos del número de vértices o aristas de corte que posee. Esta conectividad es una medida de su cohesión o robustez. (es)
- En mathématiques, et en particulier en théorie des graphes, un point d'articulation est un sommet d'un graphe non orienté qui, si on le retire du graphe, augmente le nombre de composantes connexes. Si le graphe était connexe avant de retirer ce sommet, il devient donc non connexe. (fr)
- Em matemática e ciência da computação, um vértice de corte ou ponto de articulação é um vértice de um grafo tal que a remoção deste vértice provoca um aumento no número de componentes conectados. Se o grafo era conectado antes da remoção do vértice, ele será desconectado depois. Qualquer grafo conectado com um vértice de corte tem uma conectividade de 1. Embora bem definidos, mesmo para grafos dirigidos (digrafos), os vértices de corte são utilizados principalmente em grafos não dirigidos. Em geral, um grafo conectado, não-dirigido, com n vértices não pode ter mais do que n-2 vértices de corte. Naturalmente, um grafo pode não ter nenhum vértice de corte. Uma ponte é uma aresta análoga a um vértice de corte, ou seja, a remoção de uma ponte aumenta o número de componentes conectados do grafo. (pt)
- Dwuspójna składowa - maksymalny podzbiór krawędzi grafu, taki że każda krawędź jest częścią cyklu prostego w stosunku z każdą inną krawędzią. W dwuspójnej składowej pomiędzy każdą parą wierzchołków istnieją dwie rozłączne krawędziowo drogi. (pl)
- Точкой сочленения (англ. articulation point) в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «шарнир». (ru)
- В теорії графів, двозв'язна компонента (також відомий як блок або 2-зв'язний компонент ) є максимальним двозв'язним підграфом. Будь-який підключений граф розпадається в дерево двузв'язного компонента під назвою блок-зрубаного дерева графа. Блоки з'єднані один з одним в загальній вершині, яка називається вирізана вершина або зчленувальна точка. Зокрема, вирізана вершина є будь-яка вершина, видаливши котру, збільшується число підключених компонентів. (uk)
- В теорії графів, двозв'язний компонент (також відомий як блок або 2-приєднаний компонент) є максимальним двозв'язниим підграфом. Будь-який зв'язний граф розпадається в дерево двозв'язних компонентів, званих блок-дерева графу. Блоки скріплені один з одним в загальних вершинах, званих зрізані вершини або точки шарнірного з'єднання. Зокрема, скороченна вершина є будь-яка вершина видалення якої збільшує число підключених компонентів. (uk)
- Шарніром (англ. articulation point) в теорії графів називається вершина графу, при видаленні якої кількість компонент зв'язності графу зростає. (uk)
|
| rdfs:comment
|
- In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components. (en)
- En mathématiques, et en particulier en théorie des graphes, un point d'articulation est un sommet d'un graphe non orienté qui, si on le retire du graphe, augmente le nombre de composantes connexes. Si le graphe était connexe avant de retirer ce sommet, il devient donc non connexe. (fr)
- Dwuspójna składowa - maksymalny podzbiór krawędzi grafu, taki że każda krawędź jest częścią cyklu prostego w stosunku z każdą inną krawędzią. W dwuspójnej składowej pomiędzy każdą parą wierzchołków istnieją dwie rozłączne krawędziowo drogi. (pl)
- Точкой сочленения (англ. articulation point) в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «шарнир». (ru)
- В теорії графів, двозв'язна компонента (також відомий як блок або 2-зв'язний компонент ) є максимальним двозв'язним підграфом. Будь-який підключений граф розпадається в дерево двузв'язного компонента під назвою блок-зрубаного дерева графа. Блоки з'єднані один з одним в загальній вершині, яка називається вирізана вершина або зчленувальна точка. Зокрема, вирізана вершина є будь-яка вершина, видаливши котру, збільшується число підключених компонентів. (uk)
- В теорії графів, двозв'язний компонент (також відомий як блок або 2-приєднаний компонент) є максимальним двозв'язниим підграфом. Будь-який зв'язний граф розпадається в дерево двозв'язних компонентів, званих блок-дерева графу. Блоки скріплені один з одним в загальних вершинах, званих зрізані вершини або точки шарнірного з'єднання. Зокрема, скороченна вершина є будь-яка вершина видалення якої збільшує число підключених компонентів. (uk)
- Шарніром (англ. articulation point) в теорії графів називається вершина графу, при видаленні якої кількість компонент зв'язності графу зростає. (uk)
- In der Graphentheorie bezeichnet ein Gelenkpunkt, Artikulationspunkt, Artikulation oder Schnittknoten einen Knoten eines Graphen, dessen Entfernen die Anzahl der zusammenhängenden Teilgraphen erhöhen würde. Wenn der Graph vor dem Entfernen des Knotens zusammenhängend war, ist er danach unzusammenhängend. Ein Gelenkpunkt ist ein Spezialfall eines Trenners. Eine Brücke ist eine Kante analog zu einem Gelenkpunkt; das heißt, das Entfernen der Brücke erhöht die Anzahl der zusammenhängenden Teilgraphen. (de)
- En teoría de grafos, un vértice de corte, nodo de corte, punto de corte o punto de articulación es un vértice de un grafo tal que al eliminarlo de este 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. (es)
- Em matemática e ciência da computação, um vértice de corte ou ponto de articulação é um vértice de um grafo tal que a remoção deste vértice provoca um aumento no número de componentes conectados. Se o grafo era conectado antes da remoção do vértice, ele será desconectado depois. Qualquer grafo conectado com um vértice de corte tem uma conectividade de 1. Uma ponte é uma aresta análoga a um vértice de corte, ou seja, a remoção de uma ponte aumenta o número de componentes conectados do grafo. (pt)
|
