Примеры в контексте "Matching - Паросочетание"

Перевод

Примеры

Примеры: Matching — Паросочетание

• Therefore, if some choice of U has few vertices but its removal creates a large number of odd components, then there will be many unmatched vertices, implying that the matching itself will be small.

  Таким образом, если некоторое подмножество вершин U имеет малый размер, но при его удалении создаётся большое число нечётных компонент, то останется много непокрытых паросочетанием вершин, из чего следует, что и паросочетание будет малым.

• For instance, a matching in G is a set of edges no two of which are adjacent, and corresponds to a set of vertices in L(G) no two of which are adjacent, that is, an independent set.

  Например, паросочетание в G - это множество дуг, ни одна из которых не смежна другой, и соответствующее множество вершин в L(G), ни одна из которых не смежна другой, то есть независимое множество вершин.

• By the first corollary, if edge e is part of such an alternating chain, then a new maximum matching, M', must exist and e would exist either in M or M', and therefore be free.

  По первому следствию, если ребро ё является частью такой чередующейся цепи, то должно существовать новое наибольшее паросочетание М' и ё будет принадлежать либо М, либо М', а потому является свободным.

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "A compendium of NP optimization problems": Minimum Edge Dominating Set, Minimum Maximal Matching.

  Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "A compendium of NP optimization problems": Наименьшее доминантное множество рёбер, Наименьшее максимальное паросочетание.

• A perfect matching is a spanning 1-regular subgraph, a.k.a. a 1-factor.

  Совершенное паросочетание порождает остовный 1-регулярный подграф, то есть 1-фактор.

• A graph is said to be k-factor-critical if every subset of n - k vertices has a perfect matching.

  Говорят, что граф к-фактор критический, если любое подмножество из n - k вершин имеет совершенное паросочетание.

• 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 имеет расширяющий путь.

• In the case that a near-perfect matching of the factor-critical graph is also given, the ear decomposition can be chosen in such a way that each ear alternates between matched and unmatched edges.

  В случае, когда почти совершенное паросочетание фактор-критического графа также задано, ушное разложение может быть выбрано таким образом, что каждое ухо попеременно проходит рёбра паросочетания и рёбра, не входящие в паросочетание.

• Their algorithm is based on using a push-relabel maximum flow algorithm and then, when the matching created by this algorithm becomes close to optimum, switching to the Hopcroft-Karp method.

  Этот алгоритм базируется на алгоритме проталкивания предпотока, а, когда паросочетание становится близко к оптимальному, переключается на метод Хопкрофта - Карпа.

• As they showed, when the base graph is biconnected, a graph constructed in this way is planar if and only if its base graph is outerplanar and the matching forms a dihedral permutation of its outer cycle.

  Как они показали, если базовый граф двусвязен, граф, полученный из него описанным способом, планарен тогда и только тогда, когда базовый граф внешнепланарен и паросочетание образует диэдральные перестановки внешнего цикла.

• See the glossary. is cubic, has domination number 3, and has a perfect matching and a 2-factor. has 6 distinct perfect the smallest cubic graph of girth 5.

  Задача о независимом множестве. является кубическим графом, имеет число доминирования З, имеет совершенное паросочетание и 2-фактор. имеет 6 различных совершенных паросочетаний. является наименьшим кубическим графом с обхватом 5.

• Matching and 3-dimensional matching are special cases of set packing.

  Паросочетание и трёхмерное паросочетание являются специальными случаями упаковки множеств.

• 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.

  По лемме Бержа, паросочетание М является наибольшим тогда и только тогда, когда нет М-увеличивающего пути в G. Следовательно, либо паросочетание является наибольшим, либо его можно увеличить.

• Other pairs of graph types that always admit a simultaneous embedding, but that might need larger grid sizes, include a wheel graph and a cycle graph, a tree and a matching, or a pair of graphs both of which have maximum degree two.

  Другие пары графов, позволяющие одновременное вложение, но, возможно, требующие больших размеров решётки, это колесо и цикл, дерево и паросочетание, а также пары графов, у которых максимальная степень равна двум.

• The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph.

  Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа.

• 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.

  Паросочетание максимального размера может быть найдено за полиномиальное время, но поиск наибольшего З-мерного паросочетания или наибольшего независимого множества являются NP-трудными задачами.

• To do so, find the subgraph H of G consisting of the edges that satisfy the two properties of a matched edge in a very well covered graph, and then use a matching algorithm to test whether H has a perfect matching.

  Чтобы сделать это, найдём подграф Н графа G, состоящий из рёбер, удовлетворяющих двум свойствам паросочетаний в очень хорошо покрытом графе, а затем используем алгоритм нахождения совершенного покрытия для проверки, имеет ли H совершенное паросочетание.

• There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle.

  В графе Хивуда имеется 24 паросочетания, и во всех паросочетаниях рёбра, не входящие в паросочетание, образуют гамильтонов цикл.

• 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.

  Задачу о паросочетаниях можно обобщить назначением весов рёбрам графа G. В этом случае задаётся вопрос о множестве M, которое даёт паросочетание с максимальным (минимальным) полным весом.

• An independent set in L(G) corresponds to a matching in G, and a dominating set in L(G) corresponds to an edge dominating set in G. Therefore a minimum maximal matching has the same size as a minimum edge dominating set.

  Независимое множество в L(G) соответствует паросочетанию в G, а доминирующее множество в L(G) соответствует рёберному доминирующему множеству в G. Таким образом, минимальное наибольшее паросочетание имеет тот же размер, что и минимальное рёберное доминирующее множество.

• Thus, whenever there exists a matching M {\displaystyle M^{ }} larger than the current matching M {\displaystyle M}, there must also exist an augmenting path.

  Итак, если существует паросочетание М {\displaystyle M^{ }}, большее текущего паросочетания M {\displaystyle M}, также должен существовать увеличивающий путь.

• A maximum matching is also a maximal matching, and hence it is possible to find a largest maximal matching in polynomial time.

  Наибольшее паросочетание является также максимальным, и, поэтому, имеется возможность найти самое большое максимальное паросочетание за полиномиальное время.

• 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.

  По исходной лемме тогда это паросочетание (М или М') не может быть наибольшим, что противоречит предположению о том, что оба паросочетания М и М' являются наибольшими.

Другие варианты перевода слова matching

• Сопоставление
• Соответствующий
• Увязка
• Соответствие
• Одинаковые
• Согласование
• Подбор
• Паросочетания
• Соответствует
• Совпадение
• Одинаковых
• Сверки