imported>Orthographus: Komma

2022-05-22T07:48:52Z

Komma

Neue Seite

Ein '''(perfektes) u-kapazitiertes b-Matching''' ist in der [[Graphentheorie]] eine [[Menge (Mathematik)|Menge]] von [[Kante (Graphentheorie)|Kanten]], so dass jeder [[Knoten (Graphentheorie)|Knoten]] v mit höchstens (genau) <math>b_v</math> Kanten dieser Menge [[Inzidenz (Graphentheorie)|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 [[Matching (Graphentheorie)|(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 [[Hamiltonkreisproblem|Hamiltonkreisproblems]] auffassen.

== Siehe auch ==
* [[Problem des Handlungsreisenden]]

[[Kategorie:Grundbegriff (Graphentheorie)]]

B-Matching - Versionsgeschichte

imported>Orthographus: Komma