| dbo:abstract |
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric. (en) En théorie des graphes, l'arboricité (arboricity en anglais) d'un graphe non orienté est le nombre minimum de forêts nécessaires pour couvrir toutes les arêtes. Il en existe plusieurs variantes avec des couvertures par des arbres particuliers, comme les étoiles. C'est une mesure de la densité d'un graphe : une grande arboricité correspond à un graphe dense alors qu'une faible arboricité correspond à un graphe assez proche d'un arbre donc de faible densité. (fr) Деревність неорієнтованого графа — це найменша кількість лісів, на які можна розкласти його ребра. Еквівалентно це є найменшим числом кістякових дерев, необхідних для покриття ребер графа. (uk) Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа. (ru) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/K44_arboricity.svg?width=300 |
| dbo:wikiPageExternalLink |
http://www.math-inst.hu/~p_erdos/1966-07.pdf%7Cdoi=10.1007/BF02020444%7Cdoi-access=free%7Cmr=0193025%7Caccess-date=2011-05-30%7Carchive-url=https:/web.archive.org/web/20130524175958/http:/www.math-inst.hu/~p_erdos/1966-07.pdf%7Carchive-date=2013-05-24%7Curl-status=dead http://portal.acm.org/citation.cfm%3Fid=320176.320191%7Ctitle=Embedding |
| dbo:wikiPageID |
2476311 (xsd:integer) |
| dbo:wikiPageLength |
9470 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1107498343 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Degeneracy_(graph_theory) dbr:Dense_graph dbr:Algorithmica dbc:Spanning_tree dbr:Undirected_graph dbr:Degree_(graph_theory) dbr:Induced_subgraph dbr:Pseudoforest dbr:(a,b)-decomposability dbc:Graph_invariants dbr:Complete_bipartite_graph dbr:Nash-Williams_theorem dbr:Thickness_(graph_theory) dbr:Slope_number dbr:Star_(graph_theory) dbr:Matroid_partitioning dbr:Acta_Mathematica_Hungarica dbr:Tree_(graph_theory) dbr:Fáry's_theorem dbr:Linear_arboricity dbr:Linear_forest dbr:Discrete_Mathematics_(journal) dbr:Goldberg–Seymour_conjecture dbr:Graph_partition dbr:Graphs_and_Combinatorics dbr:Israel_Journal_of_Mathematics dbr:Journal_of_Combinatorial_Theory dbr:Planar_graph dbr:Journal_of_the_London_Mathematical_Society dbr:Strength_of_a_graph dbr:Pseudoarboricity dbr:Crispin_St._J._A._Nash-Williams dbr:Spanning_tree_(mathematics) dbr:File:K44_arboricity.svg |
| dbp:wikiPageUsesTemplate |
dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Harv dbt:Main dbt:Refbegin dbt:Refend dbt:Short_description |
| dct:subject |
dbc:Spanning_tree dbc:Graph_invariants |
| gold:hypernym |
dbr:Number |
| rdf:type |
yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| rdfs:comment |
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric. (en) En théorie des graphes, l'arboricité (arboricity en anglais) d'un graphe non orienté est le nombre minimum de forêts nécessaires pour couvrir toutes les arêtes. Il en existe plusieurs variantes avec des couvertures par des arbres particuliers, comme les étoiles. C'est une mesure de la densité d'un graphe : une grande arboricité correspond à un graphe dense alors qu'une faible arboricité correspond à un graphe assez proche d'un arbre donc de faible densité. (fr) Деревність неорієнтованого графа — це найменша кількість лісів, на які можна розкласти його ребра. Еквівалентно це є найменшим числом кістякових дерев, необхідних для покриття ребер графа. (uk) Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа. (ru) |
| rdfs:label |
Arboricity (en) Arboricité (fr) Древесность графа (ru) Деревність графа (uk) |
| owl:sameAs |
freebase:Arboricity yago-res:Arboricity wikidata:Arboricity dbpedia-fr:Arboricity dbpedia-hu:Arboricity dbpedia-ru:Arboricity dbpedia-sr:Arboricity dbpedia-uk:Arboricity https://global.dbpedia.org/id/4RxWs |
| prov:wasDerivedFrom |
wikipedia-en:Arboricity?oldid=1107498343&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/K44_arboricity.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Arboricity |
| is dbo:wikiPageRedirects of |
dbr:Anarboricity dbr:Schnyder_wood dbr:Star_arboricity |
| is dbo:wikiPageWikiLink of |
dbr:Queue_number dbr:Degeneracy_(graph_theory) dbr:Dense_graph dbr:Pseudoforest dbr:(a,_b)-decomposition dbr:Crispin_Nash-Williams dbr:Nash-Williams_theorem dbr:Clique_problem dbr:Graph_coloring_game dbr:Thickness_(graph_theory) dbr:Anarboricity dbr:Star_(graph_theory) dbr:Matroid_partitioning dbr:Laman_graph dbr:Linear_arboricity dbr:Edge_coloring dbr:Goldberg–Seymour_conjecture dbr:Graph_property dbr:Graph_theory dbr:Covering_problems dbr:Arthur_Hobbs_(mathematician) dbr:Schnyder_wood dbr:Implicit_graph dbr:Star_arboricity |
| is foaf:primaryTopic of |
wikipedia-en:Arboricity |
