|
Violence and graph theory
|
|
|
|
 | |  |
| A spanning tree is a subgraph of a simple connected graph that contains no cycles | |
 | |  |
|
 |
| | |
| A tree is a simple connected graph that contains no cycles. The difference between a tree and a spanning tree is that a spanning tree is obtained by removing edges from a graph with cycles | |
| | |
|
|
|
|
|
|
|
| | |
| Any circuit can be expressed as a combination of boolean variables, which have values of either 0 or 1. These values can be enumerated in a table showing all possible combinations of the variables | |
| | |
|
 |
| | |
| The circuit can be represnted by taking each combination of variables that gives 1 as a result, doing a boolean multiplication (AND operation) on those terms to create a minterm | |
| | |
|
|
|
|
Boolean reduction made easy
|
|
|
|
| | |
| Repeate this process for every time the graph gives a result of 1, and then do a boolean addition (OR operation) on all the minterms | |
| | |
|
 |
| | |
| The resulting formula will be a simplified representation of the circuit. The minterms can be further reduced by removing variables that have no effect on the outcome of the minterm | |
| | |
|
|
|
