B-Matching

Ein (perfektes) u-kapazitiertes b-Matching ist in der Graphentheorie eine Menge von Kanten, so dass jeder Knoten v mit höchstens (genau) ${\displaystyle b_{v}}$ Kanten dieser Menge inzidiert und jede Kante in höchstens ${\displaystyle u_{e}}$ dieser Mengen enthalten ist.

Definition

Sei G=(V,E) ein Graph. Sind zusätzlich nicht negative ganze Zahlen ${\displaystyle b_{v}\in \mathbb {Z} _{+}}$ für alle Knoten ${\displaystyle v\in V}$ (sogenannte Gradbeschränkungen) und ${\displaystyle u_{e}\in \mathbb {Z} _{+}}$ für alle Kanten ${\displaystyle e\in E}$ (sogenannte Kantenkapazitäten) gegeben so nennt man eine Zuweisung ${\displaystyle x\colon E\rightarrow \mathbb {Z} }$ ein (perfektes) b-Matching falls für alle ${\displaystyle v\in V:b_{v}\geq (=)\sum _{e\in \delta (v)}x_{e}}$ und für alle ${\displaystyle e\in E:0\leq x_{e}\leq u_{e}}$ gilt.

Spezialfälle

• Gilt ${\displaystyle b\equiv 1}$ und ${\displaystyle u\equiv 1}$ so spricht man lediglich von einem (perfekten) Matching bzw. einer Paarung.
• Der Spezialfall eines perfekten 2-Matchings, d. h. ${\displaystyle b\equiv 2}$ und ${\displaystyle u\equiv 1}$ liefert eine Menge von disjunkten Kreisen. Damit kann man also ein 2-Matching auch als Relaxierung des Hamiltonkreisproblems auffassen.

Siehe auch

• Problem des Handlungsreisenden