| dbo:abstract
|
- En théorie des graphes, un arbre de Trémaux, pour un graphe non orienté G, est un arbre couvrant de G, enraciné en l'un de ses sommets, avec la propriété que deux sommets qui sont voisins dans G sont reliés l'un à l'autre en tant qu'ascendant et descendant dans l'arbre. (fr)
- In graph theory, a Trémaux tree of an undirected graph is a type of spanning tree, generalizing depth-first search trees.They are defined by the property that every edge of connects an ancestor–descendant pair in the tree. 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. All depth-first search trees and all Hamiltonian paths are Trémaux trees. In finite graphs, every Trémaux tree is a depth-first search tree, but 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 connected graph has a Trémaux tree, and not every infinite Trémaux tree is a depth-first search tree. The graphs that have Trémaux trees can be characterized by forbidden minors. An infinite 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. (en)
- Дерево Тремо неориентированного графа G — это остовное дерево графа G с выделенным корнем со свойством, что любые две смежные вершины в графе G связаны друг с другом отношением предок/потомок. Все деревья поиска в глубину и все гамильтоновы пути являются деревьями Тремо.Деревья Тремо названы именем Шарля Пьера Тремо, французского автора 19-го века, который использовал вариант поиска в глубину как стратегию . Деревья Тремо также называют нормальными остовными деревьями, особенно в контексте бесконечных графов. В конечных графах, хотя поиск в глубину сам по себе изначально последователен, деревья Тремо могут быть построены рандомизированным параллельным алгоритмом с классом сложности RNC. Деревья Тремо можно использовать для определения глубины дерева графа и как часть для проверки, является ли граф планарным.Описание деревьев Тремо одноместной второго порядка позволяет распознать эффективно свойства графа, зависимые от ориентации, для графов с ограниченной древесной шириной при использовании теоремы Курселя. Не любой бесконечный граф имеет дерево Тремо и графы, такого дерева не имеющие, можно описать запрещёнными минорами.Дерево Тремо существует в любом графе со счётным числом вершин, даже если вариант бесконечного поиска в глубину не может успешно проверить все вершины графа.В бесконечном графе дерево Тремо должно иметь в точности один бесконечный путь для каждого графа и существование дерева Тремо характеризует графы, топологические пополнения которых, образованные добавлением бесконечно удалённой точки для каждого луча, являются метрическими пространствами. (ru)
- Де́рево Тремо́ неорієнтованого графа G — це кістякове дерево графа G з виділеним коренем зі властивістю, що будь-які дві суміжні вершини в графі G пов'язані відношенням предок/нащадок. Всі дерева пошуку в глибину і всі гамільтонові шляхи є деревами Тремо. Дерева Тремо названо на честь Чарльза П'єра Тремо, французького автора XIX століття, який використовував варіант пошуку в глибину як стратегію виходу з лабіринта. Дерева Тремо також називають норма́льними кістяко́вими дере́вами, особливо в контексті нескінченних графів. У скінченних графах, хоча пошук у глибину сам по собі спочатку послідовний, дерева Тремо можна побудувати рандомізованим паралельним алгоритмом із класом складності RNC. Дерева Тремо можна використовувати для визначення деревної глибини графа і як частину для перевірки, чи є граф планарним. Опис дерев Тремо одномісною другого порядку дозволяє ефективно розпізнати властивості графа, залежні від орієнтації, для графів з обмеженою деревною шириною за використання теореми Курселя. Не кожен нескінченний граф має дерево Тремо і графи, які такого дерева не мають, можна описати забороненими мінорами. Дерево Тремо існує в будь-якому графі зі зліченним числом вершин, навіть якщо варіант нескінченного пошуку в глибину не може успішно перевірити всіх вершин графа. У нескінченному графі дерево Тремо повинне мати рівно один нескінченний шлях для кожного кінця графа і існування дерева Тремо характеризує графи, топологічні поповнення яких, утворені доданням нескінченно віддаленої точки для кожного променя, є метричними просторами. (uk)
|
| rdfs:comment
|
- En théorie des graphes, un arbre de Trémaux, pour un graphe non orienté G, est un arbre couvrant de G, enraciné en l'un de ses sommets, avec la propriété que deux sommets qui sont voisins dans G sont reliés l'un à l'autre en tant qu'ascendant et descendant dans l'arbre. (fr)
- In graph theory, a Trémaux tree of an undirected graph is a type of spanning tree, generalizing depth-first search trees.They are defined by the property that every edge of connects an ancestor–descendant pair in the tree. 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. (en)
- Де́рево Тремо́ неорієнтованого графа G — це кістякове дерево графа G з виділеним коренем зі властивістю, що будь-які дві суміжні вершини в графі G пов'язані відношенням предок/нащадок. Всі дерева пошуку в глибину і всі гамільтонові шляхи є деревами Тремо. Дерева Тремо названо на честь Чарльза П'єра Тремо, французького автора XIX століття, який використовував варіант пошуку в глибину як стратегію виходу з лабіринта. Дерева Тремо також називають норма́льними кістяко́вими дере́вами, особливо в контексті нескінченних графів. (uk)
- Дерево Тремо неориентированного графа G — это остовное дерево графа G с выделенным корнем со свойством, что любые две смежные вершины в графе G связаны друг с другом отношением предок/потомок. Все деревья поиска в глубину и все гамильтоновы пути являются деревьями Тремо.Деревья Тремо названы именем Шарля Пьера Тремо, французского автора 19-го века, который использовал вариант поиска в глубину как стратегию . Деревья Тремо также называют нормальными остовными деревьями, особенно в контексте бесконечных графов. (ru)
|
