In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - K-Zusammenhang (de)
- Graphe sommet-connexe (fr)
- K-vertex-connected graph (en)
- K-頂点連結グラフ (ja)
- Graf k-spójny (pl)
- Вершинно k-связный граф (ru)
- Grafo k-vértice-conexo (pt)
- K-вершинно-зв'язний граф (uk)
|
| rdfs:comment
| - Der k-Zusammenhang eines Graphen ist ein wichtiger Begriff in der Graphentheorie und eine Verallgemeinerung des Zusammenhangs. Anschaulich ist der k-Zusammenhang ein Maß dafür, wie schwierig es ist, einen Graphen durch Löschen von Knoten in zwei Komponenten zu zerlegen. Ist der k-Zusammenhang groß, so müssen viele Knoten gelöscht werden. (de)
- In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected. (en)
- En théorie des graphes, un graphe connexe « est dit k-sommet-connexe s'il possède au moins k + 1 sommets et s'il reste encore connexe après en avoir ôté k – 1 ». (fr)
- Graf k-spójny to graf spójny, w którym usunięcie mniej niż k dowolnych wierzchołków nie spowoduje jego rozspojenia. (pl)
- Na teoria dos grafos, um grafo G é dito k-vértice-conexo (ou k-conexo) se tem mais de k vértices e permanece conexo sempre que são removidos k-1 vértices. O vértice-conexo ou conexão, de um grafo é o maior k para que o grafo continua k-vértice-conexo. (pt)
- 数学のグラフ理論において、頂点集合 を備えるグラフ がk-頂点連結（k-ちょうてんれんけつ、英: k-vertex-connected）あるいはk-連結であるとは、k より少ない数の頂点を取り除いても依然として連結グラフであることを言う。つまり、点連結度がk以上のグラフのことである。代替的に、グラフがk-連結であるとは、それらを除いたときにグラフが非連結となるような頂点の最小部分集合の大きさが k であることを言う。 グラフが完全でないことと同値な定義は、任意の二つの頂点が k 独立な道 (点素パス) によって結ばれるときにグラフがk-連結であることである; メンガーの定理を参照されたい。しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: n-頂点の完全グラフは、頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、独立な道に基づいた定義に従うと、その連結度は n − 1 になる。そして、何人かの研究者は、連結度が n となるような代替的な定義を用いている。 1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。 グラフの頂点連結度あるいは単純に連結度とは、そのグラフ k-頂点連結であるような k の最大数のことを言う。 (ja)
- В теории графов говорят, что нетривиальный граф G вершинно k-связен (или k-связен), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным. Вершинная связность, или просто связность, графа — это наибольшее k, для которого граф k-вершинно-связен. Эквивалентное определение — если для любой пары вершин графа можно найти k непересекающихся путей, соединяющих эти вершины — см. теорему Менгера . Это определение имеет тот же ответ: n − 1 для связности полного графа Kn. (ru)
- В теорії графів кажуть, що граф G з множиною вершин V(G) k-вершинно-зв'язний (або k-зв'язний), якщо граф залишається зв'язним після видалення менше ніж k вершин з графу. Інакше кажучи, граф k-зв'язний, якщо k — це розмір найменшої множини вершин, після видалення якої граф перестає бути зв'язним. Тотожне визначення для графів з двома і більше вершинами таке, граф є k-зв'язним, якщо будь-які дві його вершини можуть бути сполучені через k незалежних шляхів; дивись теорему Менгера. 1-вершинно-зв'язний граф називається зв'язним, а 2-вершинно-зв'язний граф називають двозв'язним. (uk)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Der k-Zusammenhang eines Graphen ist ein wichtiger Begriff in der Graphentheorie und eine Verallgemeinerung des Zusammenhangs. Anschaulich ist der k-Zusammenhang ein Maß dafür, wie schwierig es ist, einen Graphen durch Löschen von Knoten in zwei Komponenten zu zerlegen. Ist der k-Zusammenhang groß, so müssen viele Knoten gelöscht werden. (de)
- In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected. (en)
- En théorie des graphes, un graphe connexe « est dit k-sommet-connexe s'il possède au moins k + 1 sommets et s'il reste encore connexe après en avoir ôté k – 1 ». (fr)
- 数学のグラフ理論において、頂点集合 を備えるグラフ がk-頂点連結（k-ちょうてんれんけつ、英: k-vertex-connected）あるいはk-連結であるとは、k より少ない数の頂点を取り除いても依然として連結グラフであることを言う。つまり、点連結度がk以上のグラフのことである。代替的に、グラフがk-連結であるとは、それらを除いたときにグラフが非連結となるような頂点の最小部分集合の大きさが k であることを言う。 グラフが完全でないことと同値な定義は、任意の二つの頂点が k 独立な道 (点素パス) によって結ばれるときにグラフがk-連結であることである; メンガーの定理を参照されたい。しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: n-頂点の完全グラフは、頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、独立な道に基づいた定義に従うと、その連結度は n − 1 になる。そして、何人かの研究者は、連結度が n となるような代替的な定義を用いている。 1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。 グラフの頂点連結度あるいは単純に連結度とは、そのグラフ k-頂点連結であるような k の最大数のことを言う。 任意のk-次元凸ポリトープのは、k-頂点連結グラフを形成する（バリンスキーの定理、）。その部分的な逆として、では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。 (ja)
- В теории графов говорят, что нетривиальный граф G вершинно k-связен (или k-связен), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным. Вершинная связность, или просто связность, графа — это наибольшее k, для которого граф k-вершинно-связен. Альтернативно граф, отличный от полного, имеет связность k, если k является размером наименьшего подмножества вершин, при удалении которого граф становится несвязным. Полные графы исключены из рассмотрения, поскольку их нельзя сделать несвязными путём удаления вершин. Полный граф с n вершинами имеет связность n − 1, как вытекает из первого определения. Эквивалентное определение — если для любой пары вершин графа можно найти k непересекающихся путей, соединяющих эти вершины — см. теорему Менгера . Это определение имеет тот же ответ: n − 1 для связности полного графа Kn. 1-связный граф называется также связным, 2-связный граф называется двусвязным, 3-связный граф называется, соответственно, трисвязным. 1-скелет любого k-мерного выпуклого многогранника образует k-вершинно-связный граф (Теорема Балинского, ). Частично обратная теорема Штейница утверждает, что любой 3-вершинно-связный планарный граф образует скелет выпуклого многогранника. (ru)
- Graf k-spójny to graf spójny, w którym usunięcie mniej niż k dowolnych wierzchołków nie spowoduje jego rozspojenia. (pl)
- Na teoria dos grafos, um grafo G é dito k-vértice-conexo (ou k-conexo) se tem mais de k vértices e permanece conexo sempre que são removidos k-1 vértices. O vértice-conexo ou conexão, de um grafo é o maior k para que o grafo continua k-vértice-conexo. (pt)
- В теорії графів кажуть, що граф G з множиною вершин V(G) k-вершинно-зв'язний (або k-зв'язний), якщо граф залишається зв'язним після видалення менше ніж k вершин з графу. Інакше кажучи, граф k-зв'язний, якщо k — це розмір найменшої множини вершин, після видалення якої граф перестає бути зв'язним. Тотожне визначення для графів з двома і більше вершинами таке, граф є k-зв'язним, якщо будь-які дві його вершини можуть бути сполучені через k незалежних шляхів; дивись теорему Менгера. Хоча визначення в літературі тотожні для більшості графів вони несумісні, коли мова йде про повні графи Kn, він альтернативно вважається n-зв'язним, (n-1)-зв'язним або навіть нескінченно зв'язним. 1-вершинно-зв'язний граф називається зв'язним, а 2-вершинно-зв'язний граф називають двозв'язним. Вершинна зв'язність або просто зв'язність, це найбільше k для якого граф є k-вершинно-зв'язним. 1-кістяк будь-якого k-вимірного опуклого політопа утворює k-вершинно-зв'язний граф. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
