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) $b_v$ Kanten dieser Menge inzidiert und jede Kante in höchstens $u_e$ dieser Mengen enthalten ist.

Definition

Sei G=(V,E) ein Graph. Sind zusätzlich nicht negative ganze Zahlen $b_v\in {\mathbb{Z}}_{+}$ für alle Knoten $v\in V$ (sogenannte Gradbeschränkungen) und $u_e\in {\mathbb{Z}}_{+}$ für alle Kanten $e\in E$ (sogenannte Kantenkapazitäten) gegeben, so nennt man eine Zuweisung $x:E\to \mathbb{Z}$ ein (perfektes) b-Matching, falls für alle $v\in V:b_v\ge (=)\sum _{e\in \delta (v)}{x}_e$ und für alle $e\in E:0\le x_e\le u_e$ gilt.

Spezialfälle

• Gilt $b\equiv 1$ und $u\equiv 1$ so spricht man lediglich von einem (perfekten) Matching bzw. einer Paarung.
• Der Spezialfall eines perfekten 2-Matchings, d. h. $b\equiv 2$ und $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