Direkt zum Inhalt

Lexikon der Mathematik: binary moment diagram

BMD, Datenstruktur für Funktionen \(f:{\{0,1\}}^{n}\to {\mathbb{Z}}\). Der Aufbau eines BMD entspricht dem eines binären Entscheidungsgraphen mit dem Unterschied, daß die Blätter mit ganzen Zahlen und nicht nur mit den Werten 0 und 1 markiert sind.

Ist jeder Kante e noch zusätzlich ein Gewicht ceaus \({\mathbb{Z}}\) zugeordnet, so spricht man von multiplicative binary moment diagram oder *BMD. Ein BMD kann als *BMD aufgefaßt werden, bei dem alle Kantengewichte gleich 1 sind.

Ein *BMD mit Wurzel w, der über der n-elementigen Variablenmenge {x1,…,xn} definiert ist, beschreibt eine Funktion \({f}_{w}:{\{0,1\}}^{n}\to {\mathbb{Z}}\), definiert wie folgt:

  1. Ist w ein Blatt, \(index(W)\in {\mathbb{Z}}\) die Markierung von w, so ist fw die konstante Abbildung, die jedes Argument auf den Wert index(w) abbildet.
  2. Ist w ein innerer Knoten und index(w) = xi, so ist

    \begin{eqnarray}{f}_{w} & = & {c}_{(w,low(w))}\cdot {f}_{low(w)}\\ & & +{x}_{i}\cdot {c}_{(w,high(w))}\cdot {f}_{high(w)}.\end{eqnarray}

*BMDs sind unter bestimmten Einschränkungen kanonische Darstellungen der Funktionen \(f:{\{0,1\}}^{n}\to {\mathbb{Z}}\). Sie müssen geordnet (geordneter binärer Entscheidungsgraph) sein, und die multiplikativen Faktoren korrespondierender low- und high-Kanten müssen zueinander relativ prim sein. Zudem müssen die *BMDs reduziert sein. Hier gelten ähnliche Reduktionsregeln wie bei den reduzierten geordneten binären Entscheidungsgraphen. Zeigt die high-Kante eines Knotens v auf das 0-Blatt, so kann der Knoten v gelöscht werden. Alle in v einlaufenden Kanten laufen nun in den Nachfolgerknoten von v ein. Sind die low-Nachfolgerknoten ebenso wie die high-Nachfolgerknoten von zwei Knoten v und w identisch, so kann einer der beiden Knoten v oder w gelöscht werden, wobei die in ihn hineingehenden Kanten auf den anderen Knoten umgelenkt werden.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos