Direkt zum Inhalt

Lexikon der Mathematik: geordneter binärer Entscheidungsgraph

OBDD, ordered binary decision diagram, ein binärer Entscheidungsgraph G = (V, E, index), der über Booleschen Variablen x1,…, xn definiert ist und für den \begin{eqnarray}index(u)\lt index(\upsilon )\end{eqnarray} für jede Kante (u, v) ∈ E gilt, bei der v kein Blatt ist. Hierbei ist < eine lineare Ordnung auf {x1,…, xn}. Die lineare Ordnung < wird Variablenordnung des OBDD genannt. In einem OBDD tritt auf jedem Pfad von der Wurzel zu einem Blatt jede Variable höchstens einmal auf, und zwar in der durch die Variablenordnung < vorgegebenen Reihenfolge.

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