| Figure (b) above is an example of a perfect matching. | Фигура (Ь) на рисунке выше является примером такого паросочетания. |
| The Turán graph T(2n, n) can be formed by removing a perfect matching from a complete graph K2n. | Граф Турана T(2n, n) можно получить удалением совершенного паросочетания из полного графа K2n. |
| Therefore, the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set. | Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества. |
| If k = 2n - 2, then G can be constructed by removing a perfect matching from K2n. | Если к = 2n - 2, то G можно получить путём удаления совершенного паросочетания из K2n. |
| Because of this decomposition, and because odd graphs are not bipartite, they have chromatic number three: the vertices of the maximum independent set can be assigned a single color, and two more colors suffice to color the complementary matching. | Ввиду этого разложения и ввиду того, что нечётные графы не являются двудольными, они имеют хроматическое число равное трём - вершинам максимального независимого множества можно назначить один цвет, а два других цвета получим из паросочетания, порождённого дополнением. |
| For a regular graph of degree k that does not have a perfect matching, this lower bound can be used to show that at least k + 1 colors are needed. | Для регулярных графов степени к {\displaystyle k}, не имеющих совершенного паросочетания, эта нижняя граница может быть использована, чтобы показать, что необходимо как минимум k + 1 {\displaystyle k+1} цветов. |
| Thus, v(G) <= p(G), that is, the size of a maximum matching is no larger than the size of a minimum edge cover. | В общем случае v (G) <= p (G) {\displaystyle u (G)\leq \rho (G)}, то есть размер наибольшего паросочетания не превосходит размера наименьшего рёберного покрытия. |
| 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. | Но тогда одно из паросочетаний М или М' должно иметь меньше рёбер в этой компоненте, что означает, что эта компонента в целом является расширяющим путём для этого паросочетания. |
| Determining the achromatic number is NP-hard; determining if it is greater than a given number is NP-complete, as shown by Yannakakis and Gavril in 1978 by transformation from the minimum maximal matching problem. | Определение, не будет ли ахроматическое число больше заданного числа является NP-полной, как показали Янакакис и Гаврил (Yannakakis, Gavril) в 1978 году путём преобразования из задачи поиска минимального наибольшего паросочетания. |
| Equivalently, its vertices can be thought of as describing all perfect matchings in a complete bipartite graph, and a linear optimization problem on this polytope can be interpreted as a bipartite minimum weight perfect matching problem. | Равным образом, вершины этого многогранника можно понимать как описание всех совершенных паросочетаний полного двудольного графа, а задачу линейной оптимизации на этом многограннике можно рассматривать как задачу поиска взвешенного минимального совершенного паросочетания. |
| In any graph without isolated vertices, the sum of the matching number and the edge covering number equals the number of vertices. | В любом графе без изолированных вершин число паросочетания и число рёберного покрытия в сумме дают число вершин. |
| Since each phase of the algorithm increases the size of the matching by at least one, there can be at most | V | {\displaystyle {\sqrt {|V|}}} additional phases before the algorithm terminates. | Так как каждая фаза алгоритма увеличивает размер паросочетания, по крайней мере, на 1, ещё может произойти не более | V | {\displaystyle {\sqrt {|V|}}} фаз. |
| If we know the values, then maximizing social welfare reduces to computing a maximum weight bipartite matching. | Если мы знаем ценности, то максимизация общественного благосостояния ограничивается поиском паросочетания максимального веса в соответствующем двудольном графе. |
| Kőnig's theorem states that the equality between the sizes of the matching and the cover (in this example, both numbers are six) applies more generally to any bipartite graph. | Теорема Кёнига как раз и утверждает равенство размеров паросочетания и покрытия (в данном примере оба числа равны шести). |
| A major reason that the blossom algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time. | Основной причиной, почему алгоритм сжатия цветков важен, является то, что он дал первое доказательство возможности нахождения наибольшего паросочетания за полиномиальное время. |
| Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem provides a characterization for arbitrary graphs. | Теорема Холла (или теорема о свадьбах) обеспечивает характеризацию двудольных графов, имеющих совершенные паросочетания, а Теорема Тутта даёт характеризацию произвольных графов. |
| However, no polynomial-time algorithm is known for finding a minimum maximal matching, that is, a maximal matching that contains the smallest possible number of edges. | Однако неизвестно никакого полиномиального по времени алгоритма для нахождения наименьшего максимального паросочетания, то есть максимального паросочетания, содержащего наименьшее возможное число рёбер. |
| This inequality is tight: for example, if G is a path with 3 edges and 4 vertices, the size of a minimum maximal matching is 1 and the size of a maximum matching is 2. | Например, если G - путь с тремя рёбрами и 4 вершинами, минимальный размер максимального паросочетания равен 1, а размер наибольшего паросочетания равен 2. |
| 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. | Однако симметрическая разность оптимального паросочетания и текущего паросочетания М {\displaystyle 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. | Совершенные паросочетания могут быть использованы для ещё одной характеристики графов без клешней - это в точности те графы, в которых любой связный порождённый подграф чётного порядка имеет совершенное паросочетание. |
| For the forward direction, let M' be a matching in G larger than M. Consider D, the symmetric difference of M and M'. | Для доказательства в прямом направлении положим, что М' является паросочетанием графа G, большим паросочетания M. Рассмотрим в качестве D симметрическую разность M и M'. |
| Similarly, cycles that alternate between matched and unmatched edges are of importance in weighted matching problems. | Аналогично, циклы, в которых чередуются рёбра из паросочетания и не из паросочетания важны в задачах взвешенных паросочетаний. |
| 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. | В случае, когда почти совершенное паросочетание фактор-критического графа также задано, ушное разложение может быть выбрано таким образом, что каждое ухо попеременно проходит рёбра паросочетания и рёбра, не входящие в паросочетание. |
| 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-трудными задачами. |