Binary Decision Diagrams
Applied Discrete Structures 2021-01-23
I've started to explore the feasibility of introducing Binary Decision Diagrams (BDD's) into the topics in the Applied Discrete Structure (ADS) sphere of influence. Volume 4A of Knuth's Art of Computer Programming has extensive coverage of the topic and there are some neat examples that build on the topics we introduce in ADS.
Here is a very simple example of a BDD that identifies the majority bit value among three bits $b_1 b_2 b_3$. We can think of any particular value as a case in a truth table with the output being the truth value for that case. For example, the case $010$ would have a truth value of 0. The whole truth table is a sequence of eight bits $00010111$, one for each case from $000$ to $111$. The first half of the truth table corresponds with the case $b_1=0$ while the second corresponds with $b_1=1$. Starting at the top of the figure below, the red edge is path followed in the $b_1=0$ case while the blue edge is followed in the $b_1=1$ case. In either case, the half of the truth table that is followed is again split depending on the value of $b_2$. Notice that if $b_1=0$ and then $b_2=0$ we are left with the first quarter of our original truth table, $00$, which produces an output of $0$ no matter what value $b_3$ has so we immediately move to the bottom right vertex, corresponding to a majority value of $0$. Another interesting situation is that if $b1=0$ and $b_2=1$, the remaining truth table is $01$, which is the same as if $b_1=1$ and $b_2=0$. This is reflected in the fact that the two cases put us into the same node, where the value of $b_3$ decides the majority value.
Instead of a truth table with eight cases, we have a graph with only six vertices that "computes" the majority value. This is a modest improvement, but for many more complex Boolean functions, the improvement can be significant.
Another example is to consider a graph with six vertices and ten edges. Suppose we wish to color the graph with three colors; i. e. identify a valid coloring with no two adjacent vertices having the same color. A boolean expression that determines whether a coloring is valid can be constructed using propositions of the form $p_{i,j}$ which represents whether vertex $i$ is colored with color $j$. For the case of six vertices and three colors, there are 18 propositions. If the chromatic number of the graph is three or less, then there would be an assignment of values to these propositions that corresponds with a 3-coloring. For one particular graph, a BDD for the coloring is below. Instead of a truth table with $2^{18}$ cases, we have a busy looking graph, but it has only 93 vertices.
For this graph we initially move from left to right. The vertex in the middle corresponds with the assignment of value to the propositions that are not valid colorings for that particular graph. All but six of the assignments end up in that vertex. For examples this size and larger, the graph's embedding in the plane isn't all that useful, but there are data structures such as python dictionaries that can be used to represent the BDD.
This idea of using BDD's in a course is still just an idea. It might be a good topic for a senior project too.