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 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\rightarrow \mathbb{Z} ein (perfektes) b-Matching falls für alle v\in V: b_v \geq (=)\sum_{e\in\delta(v)} x_e und für alle e \in E: 0\leq x_e \leq 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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Matching Dreams — Directed by B. Reeves Eason Starring Sylvia Ashton Release date(s) January 3, 1916 (1916 01 03) …   Wikipedia

  • Matching Mole — war eine englische Rockband aus der Canterbury Szene. Inhaltsverzeichnis 1 Entstehung 2 Musik und Werdegang 3 Weiterer Werdegang der einzelnen Musiker 4 Diskograph …   Deutsch Wikipedia

  • B.C. Rich — is a manufacturer of guitars and bass guitars started by the late Bernardo Chavez Rico in the early 1970s. By the 1990s, B.C. Rich s guitars were widely used in heavy metal. The popularity of B.C. Rich instruments among metal musicians continues… …   Wikipedia

  • Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

  • Matching (Graphentheorie) — Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird. Folgende Situation wird dabei betrachtet: Gegeben eine Menge von Dingen und zu diesen… …   Deutsch Wikipedia

  • Matching law — In operant conditioning, the matching law is a quantitative relationship that holds between the relative rates of response and the relative rates of reinforcement in concurrent schedules of reinforcement. It applies reliably when non human… …   Wikipedia

  • Matching theory (macroeconomics) — In macroeconomics, matching theory, also known as search and matching theory, is a mathematical framework attempting to describe the formation of mutually beneficial relationships over time. It offers a way of modeling markets in which frictions… …   Wikipedia

  • Matching pennies — This article is about the two person game. For the confidence trick, see coin matching game. Heads Tails Heads +1, −1 −1, +1 …   Wikipedia

  • Matching hypothesis — The matching hypothesis (also known as the matching phenomenon) is a social psychology theory, first proposed by Elaine Hatfield and her colleagues in 1966,[1], which suggests why people become attracted to their partner. It claims that people… …   Wikipedia

  • Matching (statistics) — The matching is a statistical technique which is used to evaluate the effect of a treatment by comparing the treated and the non treated in non experimental design (when the treatment is not randomly assigned). People use this technique with… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”