b-Matching verallgemeinert das klassische Matching: Jeder Knoten v darf in höchstens b(v) ausgewählten Kanten vorkommen. Die Kapazität b(v) ist pro Knoten vorgegeben — beim gewöhnlichen Matching steht überall b(v) = 1. Ein b-Matching ist damit eine Menge von Kanten, in der die Kapazität jedes Knotens eingehalten wird.
Definition und Zusammenhang zum Matching
Formal: In einem Graphen G = (V, E) mit Kapazitätsfunktion b: V → ℕ ist ein b-Matching eine Kantenmenge M ⊆ E, sodass jeder Knoten v in höchstens b(v) Kanten von M vorkommt. Das klassische Matching ist der Spezialfall b(v) = 1 für alle Knoten. Spricht man von einem „perfekten b-Matching“, sind alle Kapazitäten voll ausgeschöpft. Im bipartiten Graphen modelliert die Kapazität oft ein Angebot: Eine Seite hat mehrere Plätze, die andere Seite genügt jeweils einfach.
Algorithmen
b-Matching lässt sich auf klassisches Matching zurückführen, indem man jeden Knoten in b(v) Kopien aufteilt (Knotensplitting). Damit greifen dieselben polynomialen Verfahren wie der Blossom-Algorithmus von Jack Edmonds. In bipartiten Graphen reicht eine Reduktion auf ein Flussproblem, das mit Standard-Maxflow-Verfahren in polynomieller Zeit lösbar ist. Für die Praxis bedeutet das: b-Matching ist effizient lösbar, auch mit Gewichten — das gewichtete b-Matching findet eine Kantenmenge mit maximaler Gewichtssumme unter den Kapazitätsbedingungen.
Anwendungen
b-Matching löst Zuteilungsprobleme, bei denen Ressourcen eine begrenzte Anzahl an Einheiten haben: Aufgabenverteilung, Scheduling von Maschinen, Frequenzvergabe in Funknetzen oder die Zuordnung von Arbeitnehmern zu Schichten. Auch der Grad-Zusammenhang spielt eine Rolle: Ein b-Matching, das jeden Knoten mit genau b(v) Kanten versorgt, entspricht einem Teilgraphen mit vorgegebenen Graden. Die Kapazitäts-Idee ähnelt den Verhältnissen im Hospitals/Residents-Problem, dort mit Präferenzen statt Gewichten.