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

• увеличивающий путь
• расширяющий путь
• увеличивающего пути

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

A network is at maximum flow if and only if there is no augmenting path in the residual network Gf.
Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

An augmenting path is an s- t{\displaystyle s-t} path in the residual graph G f{\displaystyle G_{f.
Дополняющий путь- s- t{\ displaystyle s- t} путь в остаточном графе G f{\ displaystyle G_{ f.

However, for non-bipartite graphs, the task of finding the augmenting paths within each phase is more difficult.
Однако для недвудольных графов поиск удлиняющих путей в каждой фазе более сложен.

One can prove that a matching is maximum if and only if it does not have any augmenting path.
Можно доказать, что паросочетание является наибольшим в том и только в том случае, если не существует пополняющего пути.

Notice how the length of the augmenting path found by the algorithm(in red) never decreases.
Отметим, что в процессе выполнения алгоритма длины дополняющих путей( на рисунках обозначены красным) не убывают.

The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph.
Паросочетание строится путем итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа.

Finally, it locates an augmenting path P′ in the contracted graph(line B22) and lifts it to the original graph line B23.
Наконец, алгоритм обнаруживает увеличивающий путь P′ в сжатом графе( строка B22) и поднимает его в исходном графе строка B23.

The algorithm finds a maximal set of vertex disjoint augmenting paths of length k{\displaystyle k.
Алгоритм находит максимальное множество непересекающихся по вершинам путей длины k{\ displaystyle k.

If no augmenting path can be found, an algorithm may safely terminate, since in this case M{\displaystyle M} must be optimal.
Если увеличивающего пути не существует, можно успешно прервать алгоритм, так как M{\ displaystyle M} должно быть оптимальным.

That is, a vertex v{\displaystyle v} is put into F{\displaystyle F} if and only if it ends a shortest augmenting path.
Получается, вершина v{\ displaystyle v} принадлежит F{\ displaystyle F} тогда и только тогда, когда в ней кончается кратчайший удлиняющий путь.

Once an augmenting path is found that involves one of the vertices in F{\displaystyle F}, the DFS is continued from the next starting vertex.
Как только увеличивающий путь войдет в одну из вершин F{\ displaystyle F}, следует начать DFS от следующей вершины.

Let us now prove the contrapositive of Berge's lemma: G has a matching larger than M if and only if G has an augmenting path.
Теперь мы можем доказать лемму Бержа от противного- граф G имеет паросочетание, большее чем у M тогда и только тогда, когда G имеет расширяющий путь.

However, instead of finding just a single augmenting path per iteration, the algorithm finds a maximal set of shortest augmenting paths..
Вместо того чтобы находить один увеличивающий путь, алгоритм находит максимальное множество кратчайших увеличивающих путей..

Thus, whenever there exists a matching M∗{\displaystyle M^{*}} larger than the current matching M{\displaystyle M}, there must also exist an augmenting path.
Итак, если существует паросочетание M∗{\ displaystyle M^{*}}, большее текущего паросочетания M{\ displaystyle M}, также должен существовать увеличивающий путь.

By Berge's lemma, matching M is maximum if and only if there is no M-augmenting path in G. Hence, either a matching is maximum, or it can be augmented..
По лемме Бержа, паросочетание M является наибольшим тогда и только тогда, когда нет M- увеличивающего пути в G. Следовательно, либо паросочетание является наибольшим, либо его можно увеличить.

Since M′ is larger than M, D contains a component that has more edges from M′ than M. Such a component is a path in G that starts and ends with an edge from M′, so it is an augmenting path..
Поскольку M′ больше M, D содержит компоненту, которая имеет больше ребер изM′, чем из M. Такая компонента является путем в G, который начинается и кончается ребром из M′, так что он является расширяющим.

Note that the number of unmatched edges in an augmenting path is greater by one than the number of matched edges, and hence the total number of edges in an augmenting path is odd.
Заметим, что число не принадлежащих паросочетанию вершин в увеличивающем пути больше на единицу числа ребер, принадлежащих паросочетанию, а потому число ребер в увеличивающем пути нечетно.

But then one of M and M′ must have one fewer edge than the other in this component, meaning that the component as a whole is an augmenting path with respect to that matching.
Но тогда одно из паросочетаний M или M′ должно иметь меньше ребер в этой компоненте, что означает, что эта компонента в целом является расширяющим путем для этого паросочетания.

In each iteration the algorithm either(1) finds an augmenting path,(2) finds a blossom and recurses onto the corresponding contracted graph, or(3) concludes there are no augmenting paths..
На каждой итерации алгоритм либо( 1) находит увеличивающий путь, либо( 2) находит цветок и осуществляет рекурсию в сжатый граф, либо( 3) делается вывод, что увеличивающего пути не существует.

Therefore, once the initial| V|{\displaystyle{\sqrt{|V|}}} phases of the algorithm are complete, the shortest remaining augmenting path has at least| V|{\displaystyle{\sqrt{|V|}}} edges in it.
Следовательно, после того как первые| V|{\ displaystyle{\ sqrt{| V|}}} фаз алгоритма завершились, кратчайший оставшийся увеличивающий путь имеет длину, по крайней мере,| V|{\ displaystyle{\ sqrt{| V|.

An augmenting path in a matching problem is closely related to the augmenting paths arising in maximum flow problems, paths along which one may increase the amount of flow between the terminals of the flow.
Увеличивающие пути в задачах о паросочетаниях тесно связаны с увеличивающими путями, возникающими в задачах о максимальном потоке, путями, вдоль которых можно увеличить поток между истоком и стоком.

However, the symmetric difference of the eventual optimal matching and of the partial matching M found by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles.
Однако симметрическая разность оптимального паросочетания и текущего паросочетания M{\ displaystyle M}, найденного в предыдущих фазах, образует множество вершинно непересекающихся увеличивающих путей и чередующихся циклов.

The basic concept that the algorithm relies on is that of an augmenting path, a path that starts at a free vertex, ends at a free vertex, and alternates between unmatched and matched edges within the path.
Алгоритм основан на понятии увеличивающего пути- пути, который начинается и заканчивается в свободной вершине, а внутри пути ребра, принадлежащие и не принадлежащие паросочетанию M{\ displaystyle M}, чередуются.

For instance, in the average case for sparse bipartite random graphs, Bast et al.(2006)(improving a previous result of Motwani 1994) showed that with high probability all non-optimal matchings have augmenting paths of logarithmic length.
Например, в случае разреженного двудольного случайного графа в 2006 году было показано( улучшая предыдущий результат), что с большой вероятностью все неоптимальные паросочетания имеют увеличивающие пути логарифмической длины.

It can be shown that each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer.
Можно показать, что каждая фаза увеличивает длину кратчайшего удлиняющего пути, по крайней мере, на 1: фаза находит максимальный набор дополняющих путей данной длины, так что любой оставшийся путь должен быть длиннее.

Their results in general tend to show that the Hopcroft-Karp method is not as good in practice as it is in theory: it is outperformed both by simpler breadth-first and depth-first strategies for finding augmenting paths, and by push-relabel techniques.
Их результаты показали, что в общем случае алгоритм Хопкрофта- Карпа на практике не так хорош, как в теории: его превосходят по производительности как простые BFS и DFS- стратегии по поиску увеличивающего пути, так и алгоритмы, основанные на методе проталкивания предпотока.

If M{\displaystyle M} is a matching, and P{\displaystyle P} is an augmenting path relative to M{\displaystyle M}, then the symmetric difference of the two sets of edges, M⊕ P{\displaystyle M\oplus P}, would form a matching with size| M|+ 1{\displaystyle|M|+1.
Если M{\ displaystyle M}- паросочетание и P{\ displaystyle P}- увеличивающий путь в M{\ displaystyle M}, то симметрическая разность двух множеств ребер M⊕ P{\ displaystyle M\ oplus P} является паросочетанием размера| M|+ 1{\ displaystyle| M|+ 1.

Clearly, an augmenting path P of G can be used to produce a matching M′ that is larger than M- just take M′ to be the symmetric difference of P and M M′ contains exactly those edges of G that appear in exactly one of P and M.
Ясно, что расширяющий путь P графа G может быть использован для получения паросочетания M′, которое больше паросочетания M- просто возьмем в качестве M′ симметрическую разность пути P и M M′ состоит в точности из тех ребер графа G, которые появляются ровно раз в пути P, либо в паросочетании M.

Berge's lemma states that a matching M in a graph G is maximum(contains the largest possible number of edges) if and only if there is no augmenting path(a path that starts and ends on free(unmatched) vertices, and alternates between edges in and not in the matching) with M. It was proven by French mathematician Claude Berge in 1957 though already observed by Petersen in 1891 and Kőnig in 1931.
Лемма Бержа утверждает, что паросочетание M в графе G является наибольшим( содержит наибольшее возможное число ребер) тогда и только тогда, когда не существует расширяющего пути( пути, который начинается и завершается на свободных, то есть не принадлежащих паросочетаниям, вершинах и поочередно проходит по ребрам, принадлежащих и не принадлежащих паросочетанию) в M. Лемму доказал французский математик Клауди Берж в 1957 году хотя ее уже обсуждали Петерсен в 1891 и Кениг в 1931.

This means that we can use augmenting paths p 1{\displaystyle p_{1}}, p 2{\displaystyle p_{2}}, p 1{\displaystyle p_{1}} and p 3{\displaystyle p_{3}} infinitely many times and residual capacities of these edges will always be in the same form.
Это значит, что мы можем использовать увеличивающие пути p 1{\ displaystyle p_{ 1}}, p 2{\ displaystyle p_{ 2}}, p 1{\ displaystyle p_{ 1}} и p 3{\ displaystyle p_{ 3}} бесконечно много раз, и остаточные пропускные способности этих ребер всегда будут в той же форме.