B matching

A (perfect) u-capacitive b-matching is a set of edges in graph theory , so that every node v is incised with at most (exact) edges of this set and each edge is contained in at most these sets. ${\displaystyle b_{v}}$ ${\displaystyle u_{e}}$

definition

Let G = (V, E) be a graph. If non-negative integers are also given for all nodes (so-called degree restrictions) and for all edges (so-called edge capacities), an assignment is called a (perfect) b-matching if applies to all and to all . ${\displaystyle b_{v}\in \mathbb {Z} _{+}}$ ${\displaystyle v\in V}$ ${\displaystyle u_{e}\in \mathbb {Z} _{+}}$ ${\displaystyle e\in E}$ ${\displaystyle x\colon E\rightarrow \mathbb {Z} }$ ${\displaystyle v\in V:b_{v}\geq (=)\sum _{e\in \delta (v)}x_{e}}$ ${\displaystyle e\in E:0\leq x_{e}\leq u_{e}}$

Special cases

• Applies and so one speaks only of a (perfect) matching or pairing. ${\displaystyle b\equiv 1}$ ${\displaystyle u\equiv 1}$
• The special case of a perfect 2-matching, i.e. H. and returns a set of disjoint circles. A 2-matching can thus also be understood as a relaxation of the Hamilton circle problem. ${\displaystyle b\equiv 2}$ ${\displaystyle u\equiv 1}$

See also

• Salesman Problem