| 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 of a complete graph is called a transitive tournament, and is equivalent to a total ordering of the graph's vertices. | Ациклическая ориентация полного графа называется транзитивным турниром и она эквивалентна полному упорядочению вершин графа. |
| The acyclic chromatic number A(G) of a graph G is the least number of colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. | Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G. Ациклическая раскраска часто связывается с графами на поверхностях, не являющихся плоскостями. |
| 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). |
| 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). | Ацикличная рёберная раскраска - это вариант ациклической раскраски, в которой любые два цвета формируют ацикличный подграф (то есть, лес). |
| The acyclic chromatic number A(G) of a graph G is the least number of colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. | Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G. Ациклическая раскраска часто связывается с графами на поверхностях, не являющихся плоскостями. |
| 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. | Любой частичный порядок может быть представлен (обычно не однозначно) направленным ациклическим графом, в котором имеется путь от х к у для всех элементов х и у частичного порядка, для которых выполняетсях <= у. |
| The acyclic chromatic number A(G) of a graph G is the least number of colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. | Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G. Ациклическая раскраска часто связывается с графами на поверхностях, не являющихся плоскостями. |
| 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. | Для планарных графов ациклические ориентации являются двойственными графами вполне циклических ориентаций, и наоборот. |
| 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. | Ориентированный ациклический граф, полученный такой ориентацией называется полидеревом. |
| 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. | В обратную сторону, любой направленный ациклический граф, имеющий бимодальное планарное вложение с правильным назначением имеет восходящее планарное представление, которое может быть построено за линейное время. |
| The UCM team has now specified and established the foundation of the UCM specification as a mathematical Directed Acyclic Graph. | Сейчас группа по УМКП обозначила и установила соответствующий математический ациклический орграф в качестве основы для спецификации УМКП. |
| Here, a linear forest is an acyclic graph with maximum degree two, i.e., a disjoint union of path graphs. | Здесь линейный лес - это ациклический граф с максимальной степенью два, то есть, дизъюнктное объединение путей. |
| 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 соединяется с его марковским ограждением. |
| The moralized counterpart of a directed acyclic graph is formed by adding edges between all pairs of nodes that have a common child, and then making all edges in the graph undirected. | Морализованная копия направленного ациклического графа образуется добавлением рёбер между всеми парами узлов, которые имеют общих детей, а затем преобразования всех рёбер в графе в неориентированные. |
| Thus, finding a minimum feedback vertex set in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graphs). | Таким образом, поиск минимального разрезающего цикла множество вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случае ориентированных графов). |
| 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. | Пучок Е на паракомпактном хаусдорфовом пространстве Х называется мягким, если любое сечение ограничения Е на замкнутое подмножество Х может быть продолжено до сечения Е на всём Х. Мягкие пучки ацикличны. |