Table of Contents
III. Theory and Mathematical Background – 40%
C. Discrete structures
2. Elementary combinatorics and graph theory
a. Definition: Combinatorics is the study of counting and of sets.
b. Definition: Graphs help us to study various types of problems. In this case, a graph is set of lines and vertices.
c. Prefix notation (also called Polish notation) is a way of writing mathematical formulas that accurately show how a computer parses and executes the expression. Prefix notation does not use parentheses or rules of precedence. The order of execution is entirely dependent on the order of the expression. When evaluating a prefix expression, imagine that the values and operators of the expression are nodes in a binary tree. To evaluate the expression, traverse the tree in preorder. Alternatively, once the expression is in prefix notation, you can evaluate it by finding the rightmost operator. Evaluate the expression that uses that operator and the two values immediately to the right of the operator. For example
* + + 2 3 4 * * 5 + + 6 7 8 9
6 + 7 = 13
* + + 2 3 4 * * 5 + 13 8 9
13 + 8 = 21
* + + 2 3 4 * * 5 21 9
5 * 21 = 105
* + + 2 3 4 * 105 9
…
d. Postfix notation (also called reverse Polish notation) traverses the tree in postorder. Alternatively, evaluate the expression starting with the leftmost operator and the two values immediately to the left of that operator.
e. There are two basic rules when counting. We call the first the product rule. If a task P can be divided into two parts P1 and P2, if P1 happens x times and P2 happens y times, then the task P happens xy times. The sum rule says that if a task Q can be broken into two tasks that have no impact on each other, then Q = Q1 + Q2.
f. The most basic type of graph consists of nodes (or vertices) and edges. An edge connects two nodes together. If the edges point from one node to another, then they are directed, and we say it is a directed graph.
g. A clique is a graph where all of the nodes are connected directly to each other.
h. A path in a graph is the set of nodes and edges you travel to get from one node to another node.
i. The degree of a node is the number of edges that connect to it.
