Перевод acyclic с английского на русский

Because every DAG has a topological ordering, every acyclic orientation can be constructed in this way.

Поскольку любой ОАГ имеет топологическую сортировку, любая ациклическая ориентация может быть получена указанным образом.

The orientations for which the longest path has minimum length always include at least one acyclic orientation.

В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.

An acyclic group is a group all of whose reduced integral homology vanishes.

Ациклическая группа является группой, в которой все приведённые интегральные гомологии нулевые.

An acyclic orientation with a single source and a single sink is called a bipolar orientation.

Ациклическая ориентация с единственным источником и единственным стоком называется биполярной ориентацией.

An acyclic orientation of a complete graph is called a transitive tournament, and is equivalent to a total ordering of the graph's vertices.

Ациклическая ориентация полного графа называется транзитивным турниром и она эквивалентна полному упорядочению вершин графа.

It is an acyclic orientation if the resulting directed graph has no directed cycles.

Ориентация является ациклической, если полученный ориентированный граф не имеет ориентированных циклов.

The result might look something like this: This sequence (4, 13, 28, 27, 18) is called the acyclic or linear convolution of the two original sequences (1,2,3) and (4,5,6).

Результат будет выглядеть так: Эта последовательность (4, 13, 28, 27, 18) называется ациклической или линейной свёрткой от последовательностей (1,2,3) и (4,5,6).

Since chordal graphs can be optimally colored in O(n+m) time, the same is also true for acyclic coloring on that class of graphs.

Поскольку для хордальных графов можно найти оптимальную раскраску за время O(n+m), то же самое верно и для ациклической раскраски на этом классе графов.

The binary icosahedral group is not acyclic, however, as Hn(2I, Z) is cyclic of order 120 for n = 4k+3, and trivial for n > 0 otherwise, (Adem & Milgram 1994, pp. 279).

Бинарная группа икосаэдра, однако, не является ациклической, поскольку Hn(2I, Z) является циклической порядка 120 для n = 4k+3 и тривиальной для других n > 0.

Acyclic edge coloring is the edge-coloring variant of acyclic coloring, an edge coloring for which every two color classes form an acyclic subgraph (that is, a forest).

Ацикличная рёберная раскраска - это вариант ациклической раскраски, в которой любые два цвета формируют ацикличный подграф (то есть, лес).

However, it is possible for different vertex sequences to give rise to the same acyclic orientation, when the resulting DAG has multiple topological orderings.

Однако различные последовательности вершин могут привести к одинаковым ациклическим ориентациям, если получаемый ОАГ имеет несколько топологических сортировок.

Undirected graphs of bounded genus, bounded degree, or bounded acyclic chromatic number also have bounded oriented chromatic number.

Неориентированные графы с ограниченным родом, ограниченной степенью или ограниченным ациклическим хроматическим числом также имеют ограниченное ориентированное хроматическое число.

If the graph does not contain any cycles (i.e. it's an acyclic graph), its girth is defined to be infinity.

Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности.

In contrast, the problem of deleting edges from a directed graph to make it acyclic, the feedback arc set problem, is NP-complete.

В противоположность этому задача удаления рёбер из ориентированного графа с целью сделать его ациклическим, то есть задача о разрезающем циклы наборе дуг, является NP-полной.

Any partial order may be represented (usually in more than one way) by a directed acyclic graph in which there is a path from x to y whenever x and y are elements of the partial order with x <= y.

Любой частичный порядок может быть представлен (обычно не однозначно) направленным ациклическим графом, в котором имеется путь от х к у для всех элементов х и у частичного порядка, для которых выполняетсях <= у.

However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пути в задачах планирования.

For instance, for a four-vertex cycle graph (shown), there are 24 different vertex sequences, but only 14 possible acyclic orientations.

Например, у цикла с четырьмя вершинами (показан на рисунке) существует 24 различных последовательности, но только 14 возможных ациклических ориентаций.

With the interpretation of strings as connected, directed acyclic graphs of maximum degree one, classical definitions of edit distance such as Levenshtein distance, Hamming distance and Jaro-Winkler distance may be interpreted as graph edit distances between suitably constrained graphs.

При интерпретации сток как связных направленных ациклических графов с максимальной степенью два, классические определения расстояния редактирования, такие как расстояние Левенштейна, расстояние Хэмминга и расстояние Джаро - Винклера, могут интерпретироваться как расстояния редактирования графов между подходящими графами.

In the area of database theory, his contributions include the initiation of the study of acyclic databases and of non-two-phase locking.

В области теории баз данных основной вклад Михалиса Яннакакиса состоит в инициировании исследований ациклических баз данных и недвухфазного блокирования.

Acyclic orientations of complete graphs are called transitive tournaments.

Ациклические ориентации полных графов называются транзитивными турнирами.

Acyclic orientations and totally cyclic orientations are related to each other by planar duality.

Ациклические ориентации и вполне циклические ориентации связаны друг с другом планарной двойственностью.

Acyclic orientations are also related to colorings through the chromatic polynomial, which counts both acyclic orientations and colorings.

Ациклические ориентации связаны с раскраской посредством хроматического многочлена, который подсчитывает как ациклические ориентации, так и раскраски.

The planar dual of an acyclic orientation is a totally cyclic orientation, and vice versa.

Для планарных графов ациклические ориентации являются двойственными графами вполне циклических ориентаций, и наоборот.

If acyclic, specific in the editor the signal is understood as specific area of an infinite signal, and outside of specific area the signal is equal to zero.

Если непериодический, то заданный в редакторе сигнал понимается как заданная область бесконечного сигнала, и вне заданной области сигнал равен нулю.

Testing whether an outerplanar directed acyclic graph has an upward planar drawing is also polynomial.

Проверка, имеет ли внешнепланарный ориентированный ациклический граф восходящее планарное представление, также полиномиальна.

The directed acyclic graph resulting from such an orientation is called a polytree.

Ориентированный ациклический граф, полученный такой ориентацией называется полидеревом.

In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG).

В некоторых приложениях такие циклы нежелательны, мы можем исключить их и получить направленный ациклический граф (Directed Acyclic Graph, DAG).

However, it is NP-complete to determine whether a planar directed acyclic graph with multiple sources and sinks has an upward planar drawing.

Однако задача определения, имеет ли восходящее планарное представление планарный направленный ациклический граф с несколькими источниками и несколькими стоками, является NP-полной.

Conversely, every directed acyclic graph that has a bimodal planar embedding with a consistent assignment has an upward planar drawing, that can be constructed from it in linear time.

В обратную сторону, любой направленный ациклический граф, имеющий бимодальное планарное вложение с правильным назначением имеет восходящее планарное представление, которое может быть построено за линейное время.

In graph theory, a moral graph is used to find the equivalent undirected form of a directed acyclic graph.

В теории графов моральный граф используется для поиска эквивалентного неориентированного графа для направленного ациклического графа.

This construction can be used to derive a directed acyclic graph from any directed graph.

Это построение может быть использовано для получения направленного ациклического графа из любого ориентированного графа.

In particular, the order dual of a partial order can be interpreted in this way as the transposition of a transitively-closed directed acyclic graph.

В частности, двойственный порядок частичного порядка можно интерпретировать как транспонирование транзитивно замкнутого направленного ациклического графа.

Along the same lines, it is possible to construct an upward planar drawing (when it exists) of a directed acyclic graph with a single source and sink, in linear time.

Вдоль тех же линий можно построить восходящее планарное представление (если существует) направленного ациклического графа с единственным источником и стоком за линейное время.

Equivalently, a moral graph of a directed acyclic graph G is an undirected graph in which each node of the original G is now connected to its Markov blanket.

Эквивалентно, моральный граф ориентированного ациклического графа G является неориентарованным графом, в котором каждый узел исходного графа G соединяется с его марковским ограждением.

Every graph has an acyclic orientation.

Любой граф имеет ациклическую ориентацию.

The Gallai-Hasse-Roy-Vitaver theorem states that a graph has an acyclic orientation in which the longest path has at most k vertices if and only if it can be colored with at most k colors.

Теорема Галлаи - Хассе - Роя - Витавера утверждает, что граф имеет ациклическую ориентацию, в которой самый длинный путь имеет максимум к вершин, тогда и только тогда, когда его можно раскрасить раскрасить максимум в к цветов.

Grünbaum (1973) introduced acyclic coloring and acyclic chromatic number, and conjectured the result in the above theorem.

Грюнбаум (1973) ввёл ациклическую раскраску и ациклическое хроматическое число и высказал гипотезу, которая и была доказана Бородиным.

Once you have the acyclic convolution of two sequences, computing the product of the original numbers is easy: you just perform the carrying (for example, in the rightmost column, you'd keep the 8 and add the 1 to the column containing 27).

Зная ациклическую свёртку двух последовательностей, рассчитать произведение несложно: достаточно выполнить перенос (например, в самом правом столбце, мы оставляем 8 и добавляем 1 к столбцу, содержащему 27).

A bipolar orientation of a planar graph results in an st-planar graph, a directed acyclic planar graph with one source and one sink.

Биполярная ориентация планарного графа приводит к st-планарному графу, ориентированному ациклическому планарному графу с одним источником и одним стоком.

Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has cycle rank zero, while a complete digraph of order n with a self-loop at each vertex has cycle rank n.

Интуитивно, это понятие отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n.

One of the most common examples is the reduction of a general directed graph to an acyclic directed graph by contracting all of the vertices in each strongly connected component.

Наиболее известным примером является сведение общего ориентированного графа к ориентированному ациклическому графу стягиванием всех вершин в каждой компоненте сильной связности.

An acyclic orientation is an orientation that results in a directed acyclic graph.

Ациклическая ориентация - это ориентация, которая приводит к ориентированному ациклическому графу.

Orientations of trees are always acyclic, and give rise to polytrees.

Ориентации деревьев всегда ацикличны и являются полидеревьями.

A sheaf E on a paracompact Hausdorff space X is called soft if every section of the restriction of E to a closed subset of X extends to a section of E on all of X. Every soft sheaf is acyclic.

Пучок Е на паракомпактном хаусдорфовом пространстве Х называется мягким, если любое сечение ограничения Е на замкнутое подмножество Х может быть продолжено до сечения Е на всём Х. Мягкие пучки ацикличны.

Acyclic edge coloring is the edge-coloring variant of acyclic coloring, an edge coloring for which every two color classes form an acyclic subgraph (that is, a forest).

Ацикличная рёберная раскраска - это вариант ациклической раскраски, в которой любые два цвета формируют ацикличный подграф (то есть, лес).