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) <math>b_v</math> Kanten dieser Menge inzidiert und jede Kante in höchstens <math>u_e</math> dieser Mengen enthalten ist.
Definition
Sei G=(V,E) ein Graph. Sind zusätzlich nicht negative ganze Zahlen <math>b_v\in\mathbb{Z}_+</math> für alle Knoten <math>v\in V</math> (sogenannte Gradbeschränkungen) und <math>u_e\in\mathbb{Z}_+</math> für alle Kanten <math>e\in E</math> (sogenannte Kantenkapazitäten) gegeben, so nennt man eine Zuweisung <math>x\colon E\rightarrow \mathbb{Z}</math> ein (perfektes) b-Matching, falls für alle <math>v\in V: b_v \geq (=) \sum_{e\in\delta(v)} x_e</math> und für alle <math>e \in E: 0\leq x_e \leq u_e</math> gilt.
Spezialfälle
- Gilt <math>b\equiv 1</math> und <math>u \equiv 1</math> so spricht man lediglich von einem (perfekten) Matching bzw. einer Paarung.
- Der Spezialfall eines perfekten 2-Matchings, d. h. <math>b\equiv 2</math> und <math>u \equiv 1</math> liefert eine Menge von disjunkten Kreisen. Damit kann man also ein 2-Matching auch als Relaxierung des Hamiltonkreisproblems auffassen.