In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph is 1-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum t for which it is t-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Graph toughness (en)
- Dureté d'un graphe (fr)
- Жёсткость графа (ru)
- Жорсткість графа (uk)
|
| rdfs:comment
| - En théorie des graphes, la dureté (« toughness » en anglais) est une mesure de la connexité d'un graphe. (fr)
- In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph is 1-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum t for which it is t-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness. (en)
- Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению, имеют бесконечную жёсткость. (ru)
- Жорсткість графа — міра зв'язності графа: граф G t-жорсткий за деякого дійсного t, якщо для будь-якого цілого k > 1 не можна розбити граф G на k різних компонент зв'язності, видаливши менше ніж tk вершин. Наприклад, граф 1-жорсткий, якщо число компонент, які утворюються при видаленні вершин, завжди не перевищує числа видалених вершин. Жорсткість графа — це найбільше t, для якого він t-жорсткий. Число є скінченним числом для всіх скінченних графів, за винятком повних графів, які, за згодою, мають нескінченну жорсткість. (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
| |
| authorlink
| |
| first
| |
| last
| |
| year
| |
| has abstract
| - In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph is 1-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum t for which it is t-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness. Graph toughness was first introduced by Václav Chvátal. Since then there has been extensive work by other mathematicians on toughness; the recent survey by lists 99 theorems and 162 papers on the subject. (en)
- En théorie des graphes, la dureté (« toughness » en anglais) est une mesure de la connexité d'un graphe. (fr)
- Жорсткість графа — міра зв'язності графа: граф G t-жорсткий за деякого дійсного t, якщо для будь-якого цілого k > 1 не можна розбити граф G на k різних компонент зв'язності, видаливши менше ніж tk вершин. Наприклад, граф 1-жорсткий, якщо число компонент, які утворюються при видаленні вершин, завжди не перевищує числа видалених вершин. Жорсткість графа — це найбільше t, для якого він t-жорсткий. Число є скінченним числом для всіх скінченних графів, за винятком повних графів, які, за згодою, мають нескінченну жорсткість. Жорсткість увів Вацлав Хватал 1973 року; згодом поняттю було присвячено багато великих досліджень інших фахівців з теорії графів, так, огляд 2006 року, цілком присвячений жорсткості, налічує 99 теорем і 162 сторінки. (uk)
- Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению, имеют бесконечную жёсткость. Жёсткость была введена Вацлавом Хваталом в 1973 году; впоследствии понятию было посвящено много обширных исследований других специалистов по теории графов, так, обзор 2006 года, целиком посвящённый жёсткости, насчитывает 99 теорем и 162 страницы. (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is known for
of | |
| is known for
of | |
| is foaf:primaryTopic
of | |
![[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)
