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

Definition

Bearbeiten

Sei G=(V,E) ein Graph. Sind zusätzlich nicht negative ganze Zahlen   für alle Knoten   (sogenannte Gradbeschränkungen) und   für alle Kanten   (sogenannte Kantenkapazitäten) gegeben, so nennt man eine Zuweisung   ein (perfektes) b-Matching, falls für alle   und für alle   gilt.

Spezialfälle

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

Siehe auch

Bearbeiten