Sta znaci na Engleskom ПАРОСОЧЕТАНИЕ - prevod na Енглеском

• matching
• a matching

Примери коришћења Паросочетание на Руском и њихови преводи на Енглески

Любое максимальное паросочетание всегда является реберным доминирующим множеством.
Any maximal matching is always an edge dominating set.

Для каждой пары факторизаций существует ровно одно общее совершенное паросочетание.
Every pair of factorizations has exactly one perfect matching in common.

Оставшиеся ребра образуют паросочетание и все эти ребра можно выкрасить третьим цветом.
The remaining edges form a matching and may be colored with a third color.

Паросочетание и трехмерное паросочетание являются специальными случаями упаковки множеств.
Matching and 3-dimensional matching are special cases of set packing.

Тем не менее, граф имеет максимальное паросочетание с семью ребрами, так что β 7{\ displaystyle\ beta= 7.
However, the graph has maximum matchings with seven edges, so β 7.

Говорят, что граф k- фактор критический, если любое подмножество из n- k вершин имеет совершенное паросочетание.
A graph is said to be k-factor-critical if every subset of n- k vertices has a perfect matching.

Вопрос, можно ли любое паросочетание расширить до гамильтонова цикла, остается открытым.
The question whether every matching extends to a Hamiltonian cycle remains an open problem.

Однако если G очень хорошо покрыт, то любое совершенное паросочетание в G удовлетворяет этим свойствам.
If G is very well covered, then every perfect matching in G satisfies these properties.

Все ребра, по которым идет поток из X{\ displaystyle X} в Y{\ displaystyle Y}, образуют максимальное паросочетание.
All edges with flow from X{\displaystyle\ X} to Y{\displaystyle\ Y} then constitute a maximum matching.

Меньше известен факт, что любое совершенное паросочетание в гиперкубе можно раширить до гамильтонова цикла.
A lesser known fact is that every perfect matching in the hypercube extends to a Hamiltonian cycle.

В реберной раскраске ребра одного цвета должны быть несмежны, так что они образуют паросочетание.
In an edge coloring, the set of edges with any one color must all be non-adjacent to each other, so they form a matching.

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

Двудольным двойным покрытием полного графа Kn является корона полный двудольный граф Kn, n минус совершенное паросочетание.
The bipartite double cover of a complete graph Kn is a crown graph a complete bipartite graph Kn, n minus a perfect matching.

Число паросочетаний в полном графе без ограничения, чтобы паросочетание было совершенным, задается телефонными номерами.
The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are given by the telephone numbers.

Существует простой аппроксимационный алгоритм полиномиального времени с коэффициентом аппроксимации 2- находим любое максимальное паросочетание.
There is a simple polynomial-time approximation algorithm with approximation factor 2: find any maximal matching.

Первое слагаемое это другое паросочетание максимального веса в двудольном графе, а второе слагаемое может быть легко получено из a∗{\ displaystyle a.
The first term is another max weight bipartite matching, and the second term can be computed easily from a∗{\displaystyle a.

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

Например, рисунок показывает вершины графа, помещенные на окружность и образующие цикл, а диагонали внутри окружности образуют паросочетание.
For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching.

В графе Хивуда имеется 24 паросочетания, и во всех паросочетаниях ребра, не входящие в паросочетание, образуют гамильтонов цикл.
There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle.

Наибольшее паросочетание( или максимальное по размеру паросочетание)- это такое паросочетание, которое содержит максимальное количество ребер.
A maximum matching(also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges.

Этот результат следует прямо из более фундаментальной теоремы, что любой связный граф без клешней с четным числом вершин имеет совершенное паросочетание.
This result follows directly from the more fundamental theorem that every connected claw-free graph with an even number of vertices has a perfect matching.

Если дан граф G=( V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и| M| максимально.
Given a general graph G(V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and|M| is maximized.

Самнер( Sumner, 1974) и, независимо, Лас Вергнас( Las Vergnas, 1975) доказали, что любой связный граф без клешней с четным числом вершин имеет совершенное паросочетание.
Sumner(1974) and, independently, Las Vergnas(1975) proved that every claw-free connected graph with an even number of vertices has a perfect matching.

Двудольный граф на рисунке вверху имеет 14 вершин, паросочетание с 6 ребрами выделено синим цветом, а вершинное покрытие из шести вершин выделено красным.
The bipartite graph shown in the above illustration has 14 vertices; a matching with six edges is shown in blue, and a vertex cover with six vertices is shown in red.

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

После этого, если степень нечетна, Алон находит совершенное паросочетание за линейное время, назначает ему цвет и удаляет из графа, что приводит к графу четной степени.
Then, if the degree is odd, Alon finds a single perfect matching in near-linear time, assigns it a color, and removes it from the graph, causing the degree to become even.

По исходной лемме тогда это паросочетание( M или M′) не может быть наибольшим, что противоречит предположению о том, что оба паросочетания M и M′ являются наибольшими.
By the original lemma, then, that matching(whether M or M′) cannot be a maximum matching, which contradicts the assumption that both M and M′ are maximum.

Фактор- критический граф, это граф с нечетным числом вершин, такой, что при удалении любой вершины v из графа оставшиеся вершины имеют совершенное паросочетание.
A factor-critical graph is a graph with an odd number of vertices, such that for each vertex v, if v is removed from the graph then the remaining vertices have a perfect matching.

Паросочетание максимального размера может быть найдено за полиномиальное время, но поиск наибольшего 3- мерного паросочетания или наибольшего независимого множества являются NP- трудными задачами.
A maximum-size matching can be found in polynomial time, but finding a largest 3-dimensional matching or a largest independent set is NP-hard.

Задачу о паросочетаниях можно обобщить назначением весов ребрам графа G. В этом случае задается вопрос о множестве M, которое дает паросочетание с максимальным( минимальным) полным весом.
The matching problem can be generalized by assigning weights to edges in G and asking for a set M that produces a matching of maximum(minimum) total weight.