ПУТЕВАЯ ШИРИНА на Английском - Английский перевод

• pathwidth

Примеры использования Путевая ширина на Русском языке и их переводы на Английский язык

Путевая ширина и путевая декомпозиция являются тесной аналогией с древесной шириной и древесной декомпозицией.
Pathwidth and path-decompositions are closely analogous to treewidth and tree decompositions.

Однако, в отличие от числа Стралера, путевая ширина определена только для всего графа, а не для каждого узла в графе.
However, unlike the Strahler number, the pathwidth is defined only for the whole graph, and not separately for each node in the graph.

Путевая ширина любого графа G на единицу меньше наименьших кликового числа интервального графа, содержащего G в качестве подграфа.
The pathwidth of any graph G is equal to one less than the smallest clique number of an interval graph that contains G as a subgraph.

Поскольку путевые декомпозиции являются специальными случаями древесных декомпозиций, путевая ширина любого графа больше либо равна его древесной ширине..
Since path-decompositions are a special case of tree-decompositions, the pathwidth of any graph is greater than or equal to its treewidth.

Как следствие, путевая ширина графа как минимум не меньше его древесной ширины, но может быть больше только на логарифмический множитель.
As a consequence, the pathwidth of a graph is always at least as large as its treewidth, but it can only be larger by a logarithmic factor.

Древесная декомпозиция, в которой деревом служит путь, называется путевой декомпозицией и древесная ширина этого специального вида древесной декомпозиции известна как путевая ширина.
A tree decomposition in which the underlying tree is a path graph is called a path decomposition, and the width parameter derived from these special types of tree decompositions is known as pathwidth.

Эта теория, в которой путевая ширина тесно связана с произвольными семействами графов, замкнутых относительно миноров, имеет важное алгоритмическое применение.
This theory, in which pathwidth is intimately connected to arbitrary minor-closed graph families, has important algorithmic applications.

Тем не менее, известны некоторые алгоритмы вычисления путевой декомпозиции с большей эффективностью, если путевая ширина мала, если класс входных графов ограничен, или требуется вычислить путевую ширину приближенно.
Nevertheless, several algorithms are known to compute path-decompositions more efficiently when the pathwidth is small, when the class of input graphs is limited, or approximately.

Путевая ширина известна также как интервальная толщина( на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно- поисковое число.
Pathwidth is also known as interval thickness(one less than the maximum clique size in an interval supergraph of G), vertex separation number, or node searching number.

Поскольку любое семейство графов, замкнутое относительно взятия миноров, как и в случае планарных графов, имеет разбивающее множество вершин размера O(√ n), отсюда следует, что путевая ширина графов в любом фиксированном замкнутом относительно миноров семействе снова равна O√ n.
Since, like planar graphs, the graphs in any fixed minor-closed graph family have separators of size O(√n), it follows that the pathwidth of the graphs in any fixed minor-closed family is again O√n.

Путевая ширина имеет несколько приложений для визуализации графов: Минимальные графы, имеющие заданное число пересечений, имеют путевую ширину, ограниченную функцией от числа пересечений.
Pathwidth has several applications to graph drawing: The minimal graphs that have a given crossing number have pathwidth that is bounded by a function of their crossing number.

Для некоторых классов графов доказано, что путевая ширина и древесная ширина всегда равны друг другу- это верно для кографов, графов перестановки, дополнений графов сравнимости и графов сравнимости интервальных порядков.
In some classes of graphs, it has been proven that the pathwidth and treewidth are always equal to each other: this is true for cographs, permutation graphs, the complements of comparability graphs, and the comparability graphs of interval orders.

Путевая ширина графа имеет очень похожее на древесную ширину определение через древесное разложение, но ограничивается только теми разложениями, в которых результирующее дерево является путем.
The pathwidth of a graph has a very similar definition to treewidth via tree decompositions, but is restricted to tree decompositions in which the underlying tree of the decomposition is a path graph.

При трансляции высокоуровневых языков программирования путевая ширина возникает в задаче переупорядочения линейного кода( то есть кода без управляющей логики- переходов и циклов) таким образом, что все значения, вычисленные в коде, могут быть в машинные регистры, а не вытеснены в основную память.
In the compilation of high-level programming languages, pathwidth arises in the problem of reordering sequences of straight-line code(that is, code with no control flow branches or loops) in such a way that all the values computed in the code can be placed in machine registers instead of having to be spilled into main memory.

Путевая ширина произвольного неориентированного графа G может быть определена как наименьшее число w, такое, что существует интервальный граф H, содержащий G в качестве подграфа, такой, что наибольшая клика графа H имеет w+ 1 вершин.
The pathwidth of an arbitrary undirected graph G may be defined as the smallest number w such that there exists an interval graph H containing G as a subgraph, with the largest clique in H having w+ 1 vertices.

Если древесная ширина или путевая ширина графа не превосходит k, тогда он является подграфом хордального графа, имеющего совершенный порядок исключения, при котором каждая вершина имеет не более k предшествующих соседей.
If a graph has treewidth or pathwidth at most k, then it is a subgraph of a chordal graph which has a perfect elimination ordering in which each vertex has at most k earlier neighbors.

Путевая ширина интервального графа на единицу меньше размера максимальной клики( или, что эквивалентно, на единицу меньше его хроматического числа), a путевая ширина любого графа G равна наименьшей путевой ширине интервального графа, содержащего G в качестве подграфа.
The pathwidth of an interval graph is one less than the size of its maximum clique(or equivalently, one less than its chromatic number), and the pathwidth of any graph G is the same as the smallest pathwidth of an interval graph that contains G as a subgraph.

Для некоторых классов планарных графов путевая ширина графа и путевая ширина его двойственного графа должны лежать в интервале, границы которого линейно зависят от значений- такие границы известны для двусвязных внешнепланарных графов и для графов многогранников.
For some classes of planar graphs, the pathwidth of the graph and the pathwidth of its dual graph must be within a constant factor of each other: bounds of this form are known for biconnected outerplanar graphs and for polyhedral graphs.

Однако путевую ширину можно вычислить за линейное время для деревьев и лесов.
However, the pathwidth may be computed in linear time for trees and forests.

Графы с таким представлением имеют путевую ширину, ограниченную функцией от h и k.
The graphs with such drawings have pathwidth that is bounded by a function of h and k.

Карнаи и Туца описали приложение путевой ширины для обработки естественного языка.
Kornai& Tuza(1992) describe an application of path-width in natural language processing.

Существуют кубические графы с путевой шириной. 082n, но неизвестно, как сократить этот разрыв между нижней границей и верхней границей n/ 6.
There exist cubic graphs with pathwidth 0.082n, but it is not known how to reduce this gap between this lower bound and the n/6 upper bound.

Тогда минорно- замкнутое семейство F имеет ограниченную путевую ширину тогда и только тогда, когда множество X запрещенных миноров для F включает хотя бы один лес.
Then, a minor-closed family F has bounded pathwidth if and only if the set X of forbidden minors for F includes at least one forest.

Тот же самый метод динамического программирования может быть применен к графам с неограниченной путевой шириной, что приводит к алгоритмам, решающим непараметризованные задачи на графах за экспоненциальное время.
The same dynamic programming method also can be applied to graphs with unbounded pathwidth, leading to algorithms that solve unparametrized graph problems in exponential time.

Таким образом, графы с путевой шириной, не превосходящей p, могут быть охарактеризованы множеством Xp запрещенных миноров.
Therefore, the graphs of pathwidth at most p can be characterized by a set Xp of excluded minors.

Это свойство образует параллели, подобные связи между путевой шириной и интервальными графами, а также между древесной шириной и хордальными графами.
This property parallels similar relations between pathwidth and interval graphs, and between treewidth and chordal graphs.

Остается открытым вопрос, являются ли путевые ширины планарного графа и его двойственного всегда в линейных границах для остальных случаев.
It remains open whether the pathwidth of a planar graph and its dual are always within a constant factor of each other in the remaining cases.

В одном направлении этот результат можно доказать прямо- а именно, что если X не содержит хотя бы один лес, то свободные от X- миноров графы не имеет ограниченной путевой ширины.
In one direction, this result is straightforward to prove: if X does not include at least one forest, then the X-minor-free graphs do not have bounded pathwidth.

Но совершенные бинарные деревья с 2k+ 1 уровнями имеют путевую ширину k, так что в этом случае свободные от X- миноров графы имеют неограниченную путевую ширину.
But a perfect binary tree with 2k+ 1 levels has pathwidth k, so in this case the X-minor-free-graphs have unbounded pathwidth.

В этой терминологии, 1- гусеница- это то же самое, что и граф- гусеница, а k- гусеницы являются реберно- максимальными графами с путевой шириной k.
In this terminology, a 1-caterpillar is the same thing as a caterpillar tree, and k-caterpillars are the edge-maximal graphs with pathwidth k.