- 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) bv Kanten dieser Menge inzidiert und jede Kante in höchstens ue dieser Mengen enthalten ist.
Definition
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
- 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
- Gilt
Wikimedia Foundation.