| The question whether every matching extends to a Hamiltonian cycle remains an open problem. | Вопрос, можно ли любое паросочетание расширить до гамильтонова цикла, остаётся открытым. |
| A lesser known fact is that every perfect matching in the hypercube extends to a Hamiltonian cycle. | Меньше известен факт, что любое совершенное паросочетание в гиперкубе можно раширить до гамильтонова цикла. |
| Every perfect matching is maximum and hence maximal. | Любое совершенное паросочетание является наибольшим и максимальным. |
| There is a simple polynomial-time approximation algorithm with approximation factor 2: find any maximal matching. | Существует простой аппроксимационный алгоритм полиномиального времени с коэффициентом аппроксимации 2 - находим любое максимальное паросочетание. |
| Moreover, if G is very well covered, then every perfect matching in G satisfies these properties. | Однако если G очень хорошо покрыт, то любое совершенное паросочетание в G удовлетворяет этим свойствам. |
| A maximal matching can be found with a simple greedy algorithm. | Максимальное паросочетание можно найти простым жадным алгоритмом. |
| Every pair of factorizations has exactly one perfect matching in common. | Для каждой пары факторизаций существует ровно одно общее совершенное паросочетание. |
| Any maximal matching is always an edge dominating set. | Любое максимальное паросочетание всегда является рёберным доминирующим множеством. |
| The remaining edges form a matching and may be colored with a third color. | Оставшиеся рёбра образуют паросочетание и все эти рёбра можно выкрасить третьим цветом. |
| A perfect matching is also a minimum-size edge cover. | Совершенное паросочетание является также рёберным покрытием минимального размера. |
| Sumner (1974) and, independently, Las Vergnas (1975) proved that every claw-free connected graph with an even number of vertices has a perfect matching. | Самнер (Sumner, 1974) и, независимо, Лас Вергнас (Las Vergnas, 1975) доказали, что любой связный граф без клешней с чётным числом вершин имеет совершенное паросочетание. |
| Minimum maximal matching (decision version) is the problem GT10 in Appendix A1.1. | Минимальное по размеру максимальное паросочетание - это задача GT10 в приложении A1.1. |
| One can then remove the perfect matching to obtain a (k - 1)-regular bipartite graph, and apply the same reasoning repeatedly. | Можно тогда удалить совершенное паросочетание и (к - 1)-регулярный двудольный граф и продолжить тот же процесс рекурсивно. |
| One can prove that a matching is maximum if and only if it does not have any augmenting path. | Можно доказать, что паросочетание является наибольшим в том и только в том случае, если не существует пополняющего пути. |
| 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. | Этот результат следует прямо из более фундаментальной теоремы, что любой связный граф без клешней с чётным числом вершин имеет совершенное паросочетание. |
| The Hosoya index is always at least one, because the empty set of edges is counted as a matching for this purpose. | Индекс Хосойи всегда больше либо равен одному, поскольку пустое множество рёбер считается как паросочетание. |
| Both problems can be approximated within factor 2 in polynomial time: simply find an arbitrary maximal matching M. The number of matchings in a graph is known as the Hosoya index of the graph. | Обе задачи могут быть аппроксимированы с коэффициентом 2 с полиномиальным временм - просто находим произвольное максимальное паросочетание M. Число паросочетаний в графе известно как индекс Хосойи. |
| Perfect matchings may be used to provide another characterization of the claw-free graphs: they are exactly the graphs in which every connected induced subgraph of even order has a perfect matching. | Совершенные паросочетания могут быть использованы для ещё одной характеристики графов без клешней - это в точности те графы, в которых любой связный порождённый подграф чётного порядка имеет совершенное паросочетание. |
| The bipartite double cover of a complete graph Kn is a crown graph (a complete bipartite graph Kn, n minus a perfect matching). | Двудольным двойным покрытием полного графа Kn является корона (полный двудольный граф Kn, n минус совершенное паросочетание). |
| Line perfect graphs generalize the bipartite graphs, and share with them the properties that the maximum matching and minimum vertex cover have the same size, and that the chromatic index equals the maximum degree. | Рёберно совершенные графы обобщают двудольные графы и разделяют с ними свойства, что наибольшее паросочетание и наименьшее вершинное покрытие имеют одинаковые размеры, а хроматический индекс равен максимальной степени. |
| All edges with flow from X {\displaystyle \ X} to Y {\displaystyle \ Y} then constitute a maximum matching. | Все рёбра, по которым идёт поток из Х {\displaystyle X} в Y {\displaystyle Y}, образуют максимальное паросочетание. |
| But the only nontrivial chains in the partial order are pairs of elements corresponding to the edges in the graph, so the nontrivial chains in P form a matching in the graph. | Но нетривиальными цепями в частичном порядке могут быть только пары элементов, соответствующих рёбрам графа, так что нетривиальные цепи из Р образуют паросочетание в графе. |
| 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. | После этого, если степень нечётна, Алон находит совершенное паросочетание за линейное время, назначает ему цвет и удаляет из графа, что приводит к графу чётной степени. |
| 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. | Двудольный граф на рисунке вверху имеет 14 вершин, паросочетание с 6 рёбрами выделено синим цветом, а вершинное покрытие из шести вершин выделено красным. |
| 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. | Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и |M| максимально. |