What is the translation of " INPUT GRAPH " in Russian?

• входного графа
• входной граф
• исходный граф

Examples of using Input graph in English and their translations into Russian

Ting of HIS stream; transmit signal to input graph device;
На входное устройство графа подается сигнал;

For each node[math]v[/math] of the input graph, the indicator of reachability from the source node[math]u/math.
Для каждой вершины[ math] v[/ math] исходного графа значение достижимости( достижима или нет) от вершины- источника[ math] u/ math.

The analysis can be improved to within a polynomial factor of the number t( G){\displaystyle t(G)} of spanning trees of the input graph.
Анализ времени работы можно улучшить до полиномиального множителя числа t( G){\ displaystyle t( G)} остовных деревьев входного графа.

The running time is linear in the size of the input graph, and polynomial in its number of sources and sinks.
Время работы линейно от размера входного графа и полиномиально от числа источников и стоков.

If the input graphs are restricted to dense instances, with degree Ω( n){\displaystyle\Omega(n)}, there is an FPRAS if x≥ 1, y≥ 1.
Если входной граф ограничен до плотных графов со степенью Ω( n){\ displaystyle\ Omega( n)}, существует FPRAS алгоритм, если x≥ 1, y≥ 1.

The sphere separators constructed in this way partition the input graph into subgraphs of at most n(d+ 1)/(d+ 2) vertices.
Сферические сепараторы, построенные таким образом, разбивают входной граф на подграфы, имеющие не более n( d+ 1)/( d+ 2) вершин.

It is impossible to exactly estimate the number of nodes in each layer because this number depends on the connectedness structure of the input graph.
Точно оценить число вершин в каждом слое невозможно в силу того, что их количество зависит от структуры связанности входного графа.

However, if edges arrive in a random order, and the input graph has a degree that is at least logarithmic, then smaller competitive ratios can be achieved.
Однако, если ребра поступают в случайном порядке и исходный граф имеет степень как минимум логарифмическую, можно получить меньший конкурентный коэффициент.

The idea behind this celebrated result of Jerrum and Sinclair is to set up a Markov chain whose states are the matchings of the input graph.
Идея этого подхода, принадлежащего Джерраму и Синклеру, заключается в образовании цепи Маркова, состояния которой соответствуют паросочетаниям входного графа.

If the input graph is not a Helly circular-arc graph, then the algorithm returns a certificate of this fact in the form of a forbidden induced subgraph.
Если входной граф не является циркулярным графом дуг Хелли, то алгоритм возвращает подтверждение этого факта в виде запрещенного порожденного подграфа.

Note right away that, for implementations of such algorithms, the locality depends in many ways on the structure of the input graph and may change significantly.
Сразу нужно отметить, что локальность реализаций таких алгоритмов во многом зависит от структуры входного графа и может существенно меняться.

For each node[math]v[/math] of the input graph, the distance[ math] d( v)[/ math] defined as the number of arcs in the shortest path from[math]u[/math] to[math]v/math.
Для каждой вершины[ math] v[/ math] исходного графа расстояние[ math] d( v)[/ math], определенное как число ребер, лежащих на кратчайшем пути от вершины[ math] u[/ math] к[ math] v/ math.

In order to demonstrate efficiency, we present the graphs of the execution times for different modes of computation as functions of the size of the input graph.
Для демонстрации эффективности представлены графики времени выполнения различных режимов вычислений в зависимости от размера входного графа.

Compute a planar embedding of G. Compute a spanning tree T1 of the input graph G. Give an arbitrary orientation to each edge in G that is also in T1.
Вычисляем планарное вложение графа G. Вычисляем остовное дерево T1 входного дерева G. Даем произвольную ориентацию каждому ребру графа G, которое принадлежит также дереву T1.

This indicates that the problem fits very badly into cache memory, and the program is compelled to work all the time with RAM, which is explained by the very large size of the input graph.
Это указывает на то, что задача очень плохо укладывается в кэш- память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.

Furthermore, the Boyer-Myrvold test was extended to extract multiple Kuratowski subdivisions of a non-planar input graph in a running time linearly dependent on the output size.
При этом алгоритм проверки Бойера и Мирволда был расширен для выделения нескольких подразделений Куратовского непланарного входного графа со временем работы, линейно зависящим от размера выхода.

The leaves of the Cartesian tree represent the vertices of the input graph, and the minimax distance between two vertices equals the weight of the Cartesian tree node that is their lowest common ancestor.
Листья декартова дерева представляют собой вершины входного графа, а минимаксное расстояние между двумя вершинами равно весу узла декартова дерева, который является их наименьшим общим предком.

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.
Тем не менее, известны некоторые алгоритмы вычисления путевой декомпозиции с большей эффективностью, если путевая ширина мала, если класс входных графов ограничен, или требуется вычислить путевую ширину приближенно.

For instance, it can be solved in time linear in the size of the input graph(but exponential in the length of the path), by an algorithm that performs the following steps: Perform a depth-first search of the graph..
Например, задача может быть решена за время, линейно зависящее от размера входного графа( но за экспоненциальное время по длине пути), с помощью алгоритма, делающего следующие шаги: Осуществляем поиск в глубину по графу..

It is possible to find maximum-capacity paths and minimax paths with a single source and single destination very efficiently even in models of computation that allow only comparisons of the input graph's edge weights and not arithmetic on them.
Можно найти пути максимальной емкости и минимаксные пути с одиночным источником и одной вершиной назначения очень эффективно даже в моделях вычислений, которые позволяют лишь сравнение весов ребер входного графа, а не арифметику с ними.

Besides, it may depend on the type of the input graph because the structure and the number of strongly connected components affect strongly both the time for finding these components and the time for performing breadth-first searches.
Кроме того, данное соотношение может так же зависеть от типа входного графа, так как структура и количество сильно- связанных компонент сильно влияют как на время поиска сильно- связанных компонент, так и на время выполнения поисков в ширину.

As with treewidth, branchwidth can be used as the basis of dynamic programming algorithms for many NP-hard optimization problems, using an amount of time that is exponential in the width of the input graph or matroid.
Как и в случае древесной ширины, ширина ветвления может быть использована в качестве базиса алгоритмов динамического программирования для многих NP- трудных задач оптимизации, и в этих алгоритмах время решения будет экспоненциальным от ширины входного графа или матроида.

Roughly speaking, in order to solve the undirected s-t connectivity problem in logarithmic space, the input graph is transformed, using a combination of powering and the zigzag product, into a constant-degree regular graph with a logarithmic diameter.
Грубо говоря, для решения ненаправленной задачи s- t связности в логарифмическом пространстве памяти исходный граф преобразуется с использованием комбинации произведения и зигзаг- произведения в регулярный граф постоянной степени с логарифмическим диаметром.

The Fraysseix-Rosenstiehl planarity criterion can be used directly as part of algorithms for planarity testing, while Kuratowski's and Wagner's theorems have indirect applications: if an algorithm can find a copy of K5 or K3,3 within a given graph, it can be sure that the input graph is not planar and return without additional computation.
Критерий планарности Де Фрейсекса- Розенштиля можно использовать прямо как часть алгоритма проверки планарности, в то время как теоремы Куратовского и Вагнера применяются косвенно- если алгоритм может найти копию K5 или K3, 3 в данном графе, можно быть уверенным, что входной граф не планарен.

The algorithm of Alon(2003) begins by making the input graph regular, without increasing its degree or significantly increasing its size, by merging pairs of vertices that belong to the same side of the bipartition and then adding a small number of additional vertices and edges.
Алгоритм Алона начинает с того, что делает граф регулярным без существенного увеличения степени или существенного увеличения размера путем слияния пар вершин, принадлежащих одной доле двудольного графа, а затем добавлением небольшого числа вершин и ребер.

By the above theorem, this is equivalent to the Feder-Vardi conjecture on CSP dichotomy, which states that for every constraint language Γ, CSP(Γ) is NP-complete or in P. The homomorphism problem with a single fixed graph G on left side of input instances can be solved by brute-force in time| V( H)| O(| V( G)|), so polynomial in the size of the input graph H. In other words, the problem is trivially in P for graphs G of bounded size.
По теореме выше это эквивалентно гипотезе Федера- Варди о дихотомии задач удовлетворения ограничений, которая утверждает, что для любого языка ограничений Γ задача CSP( Γ) либо NP- полна, либо принадлежит классу P. Задача о гомоморфизме с одним фиксированным графом G в левой стороне может быть решена полным перебором за время| V( H)| O(| V( G)|), то есть полиномиально от размера входного графа H. Другими словами, задача тривиальна в P для графов G ограниченного размера.

Since counting the number of perfect matchings in a general graph is P-complete, some restriction on the input graph is required unless FP, the function version of P, is equal to P. Counting matchings, which is known as the Hosoya index, is also P-complete even for planar graphs..
Поскольку подсчет числа совершенных паросочетаний в графе общего вида является P- полной задачей, требуются некоторые ограничения на входной граф если только сложность FP, функциональной версии P, не равна P. Подсчет паросочетаний, который известен также как индекс Хосойи, также является P- полной задачей даже для планарных графов..

By applying exact algorithms for vertex coloring to the line graph of the input graph, it is possible to optimally edge-color any graph with m edges, regardless of the number of colors needed, in time 2mmO(1) and exponential space, or in time O(2.2461m) and only polynomial space Björklund.
При применении точных алгоритмов раскраски вершин реберного графа, можно реберно раскрасить оптимально любой граф с m{\ displaystyle m} ребрами, независимо от числа необходимых цветов за время 2 m m O( 1){\ displaystyle 2^{ m} m^{ O( 1)}}, используя экспоненциальное пространство, или за время O( 2. 2461 m){\ displaystyle O( 2. 2461^{ m})} и полиномиальное пространство.

For example, when the output devices of graph A are connected to the input devices of graph B, then B is dependent on A.
Например, когда выходные устройства графа А подключены к входным устройствам графа Б, то Б зависит от А.

ECG graph shows the input signal.
ЭКГ график показывает входного сигнала.