Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q7849146> ?p ?o }
Showing triples 1 to 43 of
43
with 100 triples per page.
- Q7849146 subject Q6465276.
- Q7849146 subject Q7035728.
- Q7849146 subject Q8498914.
- Q7849146 subject Q8548676.
- Q7849146 abstract "In graph theory, a Trémaux tree of an undirected graph G is a spanning tree of G, rooted at one of its vertices, with the property that every two adjacent vertices in G are related to each other as an ancestor and descendant in the tree. All depth-first search trees and all Hamiltonian paths are Trémaux trees.Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.In finite graphs, although depth-first search itself is inherently sequential, Trémaux trees can be constructed by a randomized parallel algorithm in the complexity class RNC. They can be used to define the tree-depth of a graph, and as part of the left-right planarity test for testing whether a graph is a planar graph.A characterization of Trémaux trees in the monadic second-order logic of graphs allows graph properties involving orientations to be recognized efficiently for graphs of bounded treewidth using Courcelle's theorem.Not every infinite graph has a Trémaux tree, and the graphs that do have them can be characterized by their forbidden minors.A Trémaux tree exists in every graph with countably many vertices, even when an infinite form of depth-first search would not succeed in exploring every vertex of the graph.In an infinite graph, a Trémaux tree must have exactly one infinite path for each end of the graph, and the existence of a Trémaux tree characterizes the graphs whose topological completions, formed by adding a point at infinity for each end, are metric spaces.".
- Q7849146 thumbnail Undirected_graph.svg?width=300.
- Q7849146 wikiPageWikiLink Q1087987.
- Q7849146 wikiPageWikiLink Q1128796.
- Q7849146 wikiPageWikiLink Q1141840.
- Q7849146 wikiPageWikiLink Q1191139.
- Q7849146 wikiPageWikiLink Q1192020.
- Q7849146 wikiPageWikiLink Q131476.
- Q7849146 wikiPageWikiLink Q141488.
- Q7849146 wikiPageWikiLink Q1570441.
- Q7849146 wikiPageWikiLink Q1606072.
- Q7849146 wikiPageWikiLink Q174733.
- Q7849146 wikiPageWikiLink Q179899.
- Q7849146 wikiPageWikiLink Q180953.
- Q7849146 wikiPageWikiLink Q185478.
- Q7849146 wikiPageWikiLink Q230655.
- Q7849146 wikiPageWikiLink Q273037.
- Q7849146 wikiPageWikiLink Q320357.
- Q7849146 wikiPageWikiLink Q45715.
- Q7849146 wikiPageWikiLink Q5067368.
- Q7849146 wikiPageWikiLink Q5178114.
- Q7849146 wikiPageWikiLink Q5375783.
- Q7849146 wikiPageWikiLink Q5467387.
- Q7849146 wikiPageWikiLink Q547823.
- Q7849146 wikiPageWikiLink Q5494049.
- Q7849146 wikiPageWikiLink Q6465276.
- Q7849146 wikiPageWikiLink Q7035728.
- Q7849146 wikiPageWikiLink Q7102401.
- Q7849146 wikiPageWikiLink Q7837500.
- Q7849146 wikiPageWikiLink Q816319.
- Q7849146 wikiPageWikiLink Q831672.
- Q7849146 wikiPageWikiLink Q8498914.
- Q7849146 wikiPageWikiLink Q8548676.
- Q7849146 wikiPageWikiLink Q905789.
- Q7849146 wikiPageWikiLink Q905837.
- Q7849146 wikiPageWikiLink Q994399.
- Q7849146 comment "In graph theory, a Trémaux tree of an undirected graph G is a spanning tree of G, rooted at one of its vertices, with the property that every two adjacent vertices in G are related to each other as an ancestor and descendant in the tree. All depth-first search trees and all Hamiltonian paths are Trémaux trees.Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes.".
- Q7849146 label "Trémaux tree".
- Q7849146 depiction Undirected_graph.svg.