| dbo:abstract |
In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence. An arborescence can equivalently be defined as a rooted digraph in which the path from the root to any other vertex is unique. (en) Ein Out-Tree ist in der Graphentheorie ein spezieller Graph, genauer ein gewurzelter Baum, bei dem die Kanten von der Wurzel ausgehen. (de) 在圖論內，樹狀圖（arborescence）是一個有向图；並且，對其中一個我們稱呼作根的頂點，以及任何其他頂點，此圖必然存在且只存在一條從到的路徑。換句話說，樹狀圖是一個有向的，有根的樹，並且所有的邊都指離根的方向。所有的樹狀圖都是一個有向无环图。 (zh) |
| dbo:wikiPageID |
13251077 (xsd:integer) |
| dbo:wikiPageLength |
7209 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1096719629 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Rooted_tree dbc:Directed_acyclic_graphs dbr:Undirected_graph dbc:Trees_(graph_theory) dbr:Tree_(graph_theory) dbr:W._T._Tutte dbr:Directed_graph dbr:Edmonds'_algorithm dbr:Graph_theory dbr:Directed_acyclic_graph dbr:Vertex_(graph_theory) dbr:Multitree dbr:Directed_path dbr:Rooted_digraph |
| dbp:title |
Arborescence (en) Rooted Tree (en) |
| dbp:urlname |
Arborescence (en) RootedTree (en) |
| dbp:wikiPageUsesTemplate |
dbt:Combin-stub dbt:Mathworld dbt:Mvar dbt:OEIS dbt:Reflist dbt:Short_description |
| dct:subject |
dbc:Directed_acyclic_graphs dbc:Trees_(graph_theory) |
| gold:hypernym |
dbr:Graph |
| rdf:type |
dbo:Software yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:VisualCommunication106873252 yago:WikicatDirectedGraphs |
| rdfs:comment |
Ein Out-Tree ist in der Graphentheorie ein spezieller Graph, genauer ein gewurzelter Baum, bei dem die Kanten von der Wurzel ausgehen. (de) 在圖論內，樹狀圖（arborescence）是一個有向图；並且，對其中一個我們稱呼作根的頂點，以及任何其他頂點，此圖必然存在且只存在一條從到的路徑。換句話說，樹狀圖是一個有向的，有根的樹，並且所有的邊都指離根的方向。所有的樹狀圖都是一個有向无环图。 (zh) In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence. (en) |
| rdfs:label |
Out-Tree (de) Arborescence (graph theory) (en) Arborescenza (it) 樹狀圖 (zh) |
| owl:sameAs |
freebase:Arborescence (graph theory) yago-res:Arborescence (graph theory) wikidata:Arborescence (graph theory) dbpedia-de:Arborescence (graph theory) dbpedia-it:Arborescence (graph theory) dbpedia-zh:Arborescence (graph theory) https://global.dbpedia.org/id/WssC |
| prov:wasDerivedFrom |
wikipedia-en:Arborescence_(graph_theory)?oldid=1096719629&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Arborescence_(graph_theory) |
| is dbo:wikiPageDisambiguates of |
dbr:Arborescence |
| is dbo:wikiPageRedirects of |
dbr:Arboreal_decomposition |
| is dbo:wikiPageWikiLink of |
dbr:Binary_tree dbr:Rhizome_(philosophy) dbr:Rooted_graph dbr:Strahler_number dbr:Matroid_intersection dbr:Address_space dbr:Tree_(data_structure) dbr:Tree_(graph_theory) dbr:3D_Slash dbr:Eulerian_path dbr:Edmonds'_algorithm dbr:Directed_acyclic_graph dbr:BEST_theorem dbr:Arborescence dbr:Polytree dbr:Minimum_spanning_tree dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Multitree dbr:Sumner's_conjecture dbr:Separation_oracle dbr:Random_graph dbr:Random_tree dbr:Arboreal_decomposition |
| is foaf:primaryTopic of |
wikipedia-en:Arborescence_(graph_theory) |