Skip to main content

Midterm 3 note sheet

Relations and functions, graphs, finite automata and trees

Published

Last modified: 2026-11-19 12:07:39 (PST)

This sheet comes printed with Midterm 3. You may not bring your own notes, so study with this sheet. It leaves out some results; the full definitions are in the notes. Download the PDF to print it.

Relations and functions

Table 1: Relations and functions.
Relation on \(A\) \(R \subseteq A \times A\), and \((a \mathrel{R} b) \Leftrightarrow ((a, b) \in R)\)
Reflexive \(\forall a \in A, a \mathrel{R} a\)
Symmetric \(\forall a, b \in A, ((a \mathrel{R} b) \Rightarrow (b \mathrel{R} a))\)
Transitive \(\forall a, b, c \in A, (((a \mathrel{R} b) \land (b \mathrel{R} c)) \Rightarrow (a \mathrel{R} c))\)
Antisymmetric \(\forall a, b \in A, (((a \mathrel{R} b) \land (b \mathrel{R} a)) \Rightarrow (a = b))\)
Equivalence relation reflexive, symmetric and transitive
Equivalence class \([a] = {\mathopen{}\left\{b \in A : b \mathrel{R} a\right\}\mathclose{}}\)
Injective \(f : A \to B\) \(\forall a_1, a_2 \in A, ((f(a_1) = f(a_2)) \Rightarrow (a_1 = a_2))\)
Surjective \(\forall b \in B, \exists a \in A, f(a) = b\)
Bijective injective and surjective
Inverse of a bijection \(f^{-1} : B \to A\) with \((f^{-1}(b) = a) \Leftrightarrow (f(a) = b)\)
Floor \(\mathopen{}\left\lfloor x\right\rfloor\mathclose{} = \max {\mathopen{}\left\{n \in \mathbb{Z}: n \le x\right\}\mathclose{}}\)

Graphs

Table 2: Graphs.
Degree \(\deg(v)\): edges with endpoint \(v\), a loop counting twice
Walk from \(u\) to \(v\) \(v_0, e_1, v_1, \ldots, e_n, v_n\), \(v_0 = u\), \(v_n = v\), \(e_i\) joins \(v_{i - 1}\) and \(v_i\); length \(n\)
Trail, path a walk with no repeated edge; with no repeated vertex
Circuit a trail of length \(\ge 1\) from a vertex to itself
Connected a walk between every two vertices
Euler circuit a circuit that contains every edge
Euler trail a trail from \(u\) to \(v \ne u\) that contains every edge
Hamiltonian cycle a circuit that visits every vertex once, then returns to its start
Bipartite \(V = V_1 \cup V_2\) with \(V_1 \cap V_2 = \emptyset\), and every edge has one endpoint in \(V_1\) and one in \(V_2\)
procedure bfs(G, s)                       procedure dfs(G, v)   // start: dfs(G, s)
    mark s, and set dist[s] := 0              mark v
    Q := a queue containing only s            for each vertex u in the list of v, in order
    while Q is not empty                          if u is not marked
        v := remove the front of Q                    dfs(G, u)
        for each vertex u in the list of v, in order
            if u is not marked
                mark u, and set dist[u] := dist[v] + 1
                add u to the back of Q

Finite automata

Table 3: Finite automata.
DFA \(M = (S, \Sigma, \delta, s_0, F)\): states, alphabet, \(\delta : S \times \Sigma \to S\), initial state, accepting states
Transition table \(\to\) marks the initial state, \(*\) each accepting state
Empty string \(\lambda\)
Run on \(w = x_1 \cdots x_n\) \(r_0, \ldots, r_n\) with \(r_0 = s_0\) and \(r_i = \delta(r_{i - 1}, x_i)\)
Accepts \(w\) \(r_n \in F\)
Language \(L(M) = {\mathopen{}\left\{w : M \text{ accepts } w\right\}\mathclose{}}\)

Trees

Table 4: Trees.
Tree a connected graph with no cycles
Edges of a tree a tree with \(n\) vertices has \(n - 1\) edges
Binary tree \(\mathtt{nil}\), or \(\operatorname{node}(x, L, R)\): root label \(x\), subtrees \(L\) and \(R\)
In Racket \(\mathtt{nil}\) is '(), \(\operatorname{node}(x, L, R)\) is (list x L R)
Preorder root, preorder of \(L\), preorder of \(R\)
Inorder inorder of \(L\), root, inorder of \(R\)
Postorder postorder of \(L\), postorder of \(R\), root
Level, height the root is at level 0, a child one below its parent; height is the largest level
Leaf a vertex with no children
Leaf of a tree with no root a vertex of degree 1
Back to top