Degeneracy (graph theory)
http://dbpedia.org/resource/Degeneracy_(graph_theory) an entity of type: Abstraction100002137
Degenerovaný graf nebo k-degenerovaný graf je v teorii grafů graf, jehož každý podgraf obsahuje alespoň jeden vrchol stupně nejvýše k.
rdf:langString
In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.
rdf:langString
En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage.
rdf:langString
k-ви́роджений граф — це неорієнтований граф, у якому кожен підграф має вершини зі степенем, що не перевищує k. Ви́родженість графа — це найменше значення k, для якого граф є k-виродженим. Виродженість графа відбиває, наскільки граф розріджений і (з точністю до сталого множника) відбиває інші заходи розрідженості, такі як деревність графа.
rdf:langString
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и (с точностью до постоянного множителя) отражает другие меры разреженности, такие как древесность графа.
rdf:langString
rdf:langString
Degenerovaný graf
rdf:langString
Degeneracy (graph theory)
rdf:langString
Dégénérescence (théorie des graphes)
rdf:langString
Вырожденность (теория графов)
rdf:langString
Виродженість (теорія графів)
xsd:integer
27545816
xsd:integer
1081344237
rdf:langString
Szekeres
rdf:langString
Wilf
xsd:integer
1968
rdf:langString
Degenerovaný graf nebo k-degenerovaný graf je v teorii grafů graf, jehož každý podgraf obsahuje alespoň jeden vrchol stupně nejvýše k.
rdf:langString
In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph. Degeneracy is also known as the k-core number, width, and linkage, and is essentially the same as the coloring number or Szekeres–Wilf number (named after Szekeres and Wilf). k-degenerate graphs have also been called k-inductive graphs. The degeneracy of a graph may be computed in linear time by an algorithm that repeatedly removes minimum-degree vertices. The connected components that are left after all vertices of degree less than k have been (repeatedly) removed are called the k-cores of the graph and the degeneracy of a graph is the largest value k such that it has a k-core.
rdf:langString
En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage. Il est possible de calculer l'ordre de dégénérescence en temps linéaire.L'algorithme consiste à retirer itérativement les nœuds de plus faible degré, en maintenant à jour une file de paquets indexés par leur degré courant.Les composantes connexes obtenues lorsque tous les sommets de degré inférieur à k ont été retirés sont appelés k-cœur du graphe, et la dégénérescence k est alors donnée par la plus grande valeur k associée à un k-cœur non-vide. La dégénérescence est une mesure de la non-densité du graphe (c'est-à-dire d'à quel point le graphe est creux). On l'utilise notamment dans les problèmes de coloration de graphes.
rdf:langString
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и (с точностью до постоянного множителя) отражает другие меры разреженности, такие как древесность графа. Вырожденность известна также под именем k-ядерное число, ширина и зацепление, и, по существу, это то же самое, что и число раскраски или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графами. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степенью. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна наибольшему значению k, для которого существует k-ядро.
rdf:langString
k-ви́роджений граф — це неорієнтований граф, у якому кожен підграф має вершини зі степенем, що не перевищує k. Ви́родженість графа — це найменше значення k, для якого граф є k-виродженим. Виродженість графа відбиває, наскільки граф розріджений і (з точністю до сталого множника) відбиває інші заходи розрідженості, такі як деревність графа. Виродженість відома також під назвою k-я́дерне число́, ширина́ і заче́плення, і, по суті, це те саме, що й число́ розфарбовува́ння або число́ Секереша — Ві́лфа. k-вироджені графи називаються також k-індукти́вними гра́фами. Виродженість графа можна обчислити за лінійний час за допомогою алгоритму, що послідовно видаляє вершини з найменшим степенем. Компоненту зв'язності, що залишилася після видалення всіх вершин зі степенем, меншим від k називають k-ядро́м графа, і виродженість графа дорівнює найбільшому значенню k, для якого існує k-ядро.
rdf:langString
George Szekeres
rdf:langString
Herbert Wilf
xsd:nonNegativeInteger
28863
