THE SUBGRAPH на Русском - Русский перевод

• подграфа
• подграф

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

The Subgraph Isomorphism problem is NP-complete.
При этом задача поиска изоморфного подграфа в графе является NP- полной.

On the other hand, if S is finite, then(by working in the subgraph G\ S) it can be assumed to be empty.
С другой стороны, если S конечно, то( работая с подграфом G\ S) его можно считать пустым.

More precisely, it is graph homomorphism φ from G to itself such that φ(v) v for each vertex v in the subgraph φG.
Точнее, это гомоморфизм φ из G в себя, в котором φ( v) v для каждой вершины v в подграфе φG.

Equivalently, it is one of the connected components of the subgraph of G formed by repeatedly deleting all vertices of degree less than k.
Эквивалентно, это одна из связных компонент подграфа G, образованного последовательным удалением всех вершин со степенью, меньшей k.

The degeneracy of a graph is the maximum, over all induced subgraphs of the graph, of the minimum degree of a vertex in the subgraph.
Вырожденность графа- это максимальное число, по всем порожденным подграфам графа, минимума степеней вершин подграфа.

Each edge within the subgraph is oriented from a vertex with a lower number to a vertex with a higher number, and is therefore properly colored.
При такой раскраске каждое ребро подграфа ориентировано из вершины с меньшим индексом в вершину с большим индексом, а потому раскраска будет правильной.

Via this theorem, similar bounds in extremal graph theory can be proven for any excluded subgraph, depending on the chromatic number of the subgraph.
Вследствие этой теоремы в теории экстремальных графов для любого запрещенного подграфа можно доказать похожие границы, зависящие от хроматического числа подграфа.

The weak dual of a plane graph is the subgraph of the dual graph whose vertices correspond to the bounded faces of the primal graph.
Слабодвойственный планарному графу- это подграф двойственного графа, в котором вершины соответствуют ограниченным граням исходного графа.

Their algorithm finds large planar subgraphs within the given graph such that, if a linkless embedding exists, it has to respect the planar embedding of the subgraph.
Их алгоритм находит большие планарные подграфы внутри заданного графа, такие, что, если существует незацепленное вложение, они представляют планарное вложение подграфа.

This is different from the subgraph isomorphism problem in that the absence of an edge in G1 implies that the corresponding edge in G2 must also be absent.
Задача отличается от задачи изоморфизма подграфу в том, что из отсутствия ребра в G1 следует, что соответствующее ребро в G2 должно также отсутствовать.

Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.
Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов.

The set of flaps β(X) for a haven of order k(with the touching definition) forms a bramble of order at least k, because any set Y of fewer than k vertices fails to hit the subgraph βY.
Множество бортов β( X) для укрытия порядка k( с определением касания) образует ежевику порядка как минимум k, поскольку любое множество Y с числом вершин, меньшим k не может покрыть подграф βY.

A connected component of an undirected graph is the subgraph consisting of the vertices and edges that can be reached by following edges from a single given starting vertex.
Связная компонента неориентированного графа- это подграф, состоящий из вершин и ребер, которые можно достичь, следуя по ребрам, исходя из одной стартовой вершины.

The thickness of G is also within constant factors of another standard graph invariant, the degeneracy, defined as the maximum, over subgraphs of G, of the minimum degree within the subgraph.
Толщина графа G связана с другим стандартным инвариантом, вырожденностью, определяемой как максимум по всем подграфам графа G минимальной степени подграфа.

A graph, G(V, E), has a perfect matching if and only if for every subset U of V, the subgraph induced by V- U has at most|U| connected components with an odd number of vertices.
Граф G( V, E) имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества U в V подграф, индуцированный V- U, имеет не более| U| связных компонент с нечетным числом вершин.

A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph.
Совершенный граф- это неориентированный граф, в любом порожденном подграфе которого размер его наибольшей клики равен минимальному числу цветов раскраски подграфа.

The induced subgraph isomorphism problem is a form of the subgraph isomorphism problem in which the goal is to test whether one graph can be found as an induced subgraph of another.
Задача изоморфизма порожденных подграфов является видом задачи поиска изоморфного подграфа, в которой целью является проверка, может ли один граф быть найден как порожденный подграф другого графа.

The result of one or more edge contractions in an undirected graph G is a quotient of G, in which the blocks are the connected components of the subgraph of G formed by the contracted edges.
Результат одного или более стягивания ребра в неориентированном графе G является факторграфом графа G, в котором блоки являются связными компонентами подграфа графа G образованные стягиванием ребер.

C{\displaystyle C} is peripheral if it is an induced cycle with the property that the subgraph G∖ C{\displaystyle G\setminus C} formed by deleting the edges and vertices of C{\displaystyle C} is connected.
C{\ displaystyle C} является периферийным циклом, если он является порожденным циклом со свойством, что подграф G∖ C{\ displaystyle G\ setminus C}, образованный удалением ребер и вершин цикла C{\ displaystyle C} связен.

The subgraph isomorphism problem, of finding whether a pattern graph of bounded size exists as a subgraph of a larger graph, can be solved in linear time when the larger graph has bounded book thickness.
Задача изоморфизма подграфа, заключающаяся в определении, находится ли ограниченный в размере граф некоторого вида в качестве подграфа большего графа, может быть решена за линейное время, если больший граф имеет ограниченную толщину книжного вложения.

To a graph G there corresponds a signed complete graph Σ on the same vertex set, whose edges are signed negative if in G and positive if not in G. Conversely, G is the subgraph of Σ that consists of all vertices and all negative edges.
Графу G соответствует знаковый полный граф Σ на том же множестве вершин, ребра которого отрицательны, если принадлежат G, и положительны, если не принадлежат G. И обратно, G является подграфом Σ и состоит из всех вершин и отрицательных ребер.

For each partition class X{\displaystyle X} in P{\displaystyle P}, the subgraph G{\displaystyle G} induced by X{\displaystyle X} is called a factor and gives a representation of all edges with both endpoints in X{\displaystyle X.
Для каждого класса разбиения X{\ displaystyle X} в P{\ displaystyle P} подграф G{\ displaystyle G}, порожденный X{\ displaystyle X}, называется множителем и он дает представление всех ребер с обоими концами в X{\ displaystyle X.

Two graphs G and H are homomorphically equivalent if G→ H and H→ G. A retraction is a homomorphism r from a graph G to a subgraph H of G such that r(v) v for each vertex v of H. In this case the subgraph H is called a retract of G. A core is a graph with no homomorphism to any proper subgraph..
Ретракция- это гомоморфизм r из графа G в подграф H графа G, такой что r( v)= v для каждой вершины v из H. В этом случае подграф H называется ретрактом графа G. Ядро- это граф, не имеющий гомоморфизма в любой собственный подграф..

For example, the subgraph isomorphism problem is NP-complete on connected proper interval graphs and on connected bipartite permutation graphs, but the induced subgraph isomorphism problem can be solved in polynomial time on these two classes.
Например, задача об изоморфизме подграфу является NP- полной на связных собственных интервальных графах и на связных двудольных графах перестановок, но задача изоморфизма порожденному подграфу может быть решена за полиномиальное время на этих двух классах.

Despite these differences, modules preserve a desirable property of connected components, which is that many properties of the subgraph G{\displaystyle G} induced by a connected component X{\displaystyle X} are independent of the rest of the graph.
Не смотря на различия, модули сохраняют желательное свойство компонент связности, заключающееся в том, что многие свойства подграфа G{\ displaystyle G}, порожденного компонентой связности X{\ displaystyle X}, не зависят от остальной части графа.

Instances of the subgraph isomorphism problem in which the goal is to find a target graph of bounded size, as a subgraph of a larger graph whose size is not bounded, may be solved in linear time when the larger graph belongs to a family of graphs of bounded expansion.
Экземпляр задачи изоморфизма подграфа, в которой целью является поиск графа ограниченного размера, являющегося подграфом большего графа, размер которого не ограничен, может быть решен за линейное время, если больший граф принадлежит семейству графов с ограниченным расширением.

A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph(pattern matching, thus solving the subgraph isomorphism problem) and by replacing the found occurrence by an instance of the replacement graph.
Правило переписывания графа применяется к исходному графу путем поиска вхождения шаблонного графа( сопоставление с образцом, тем самым решая проблему изоморфизма подграфа) и замены найденного вхождения экземпляром заменяющего графа.

The subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete.
Задача поиска изоморфного подграфа- это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H. Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP- полной.

Cameron, Edmonds& Lovász(1986) proved that, if the edges of a complete graph are partitioned into three subgraphs in such a way that every three vertices induce a connected graph in one of the three subgraphs, and if two of the subgraphs are perfect, then the third subgraph is also perfect.
Камерон, Эдмондс и Ловаш доказали, что если ребра полного графа разбиты на три подграфа таким образом, что любые три вершины порождают связный граф в одном из трех подграфов, и если два из подграфов совершенны, то третий подграф тоже совершенный.

In a sense, the vector component of the digital maps can be considered as the global graph, inside which the vertices of the subgraph formed by the wireless network nodes are placed, while vertices of the subgraph can or cannot match with vertices of the global graph, and can be placed on its edges.
В известном смысле, векторная компонента цифровой карты может рассматриваться как глобальный граф, внутри которого размещаются вершины субграфа, образованного узлами беспроводной сети, причем вершины субграфа могут, как совпадать с вершинами глобального графа, так и располагаться на его ребрах.