Math Background

Question 1

Surjective Function

Answer 1

All Functions: Every A is mapped to at most 1 B (every A has one; not one-to-many)
Surjective: Every B is mapped to at least 1 A (every B has one)

Question 2

Injective Function

Answer 2

All Functions: Every A is mapped to at most 1 B (every A has one; not one to many)
Injective: Every A is mapped to at most one B (not many-to-one)

Question 3

Cycle

Answer 3

A cycle is a list (v_0, v_1, …, v_k) element of V^(k+1) s.t. (v_i, v_i+1) element of E for all i element of [k] and v_k = v_0.

Question 4

one-to-one function

Answer 4

injective (not many-to-one); invertible

Question 5

onto function

Answer 5

surjective (every B has one)

Question 6

Graph Theory Theorem: DAG Acyclic when …

Answer 6

A n-vertex directed graph is acyclic iff you can number vertices so numbers only increase

Question 7

Proof: DAG Acyclic when … A n-vertex directed graph is acyclic iff you can number vertices so numbers only increase

Answer 7

Lemma 1: Every DAG has a sink (proof by contradiction, pigeon hole on the number of vertices visited)

Question 8

Graph Theory Theorem: Connected graphs have a minimum of … edges

Answer 8

Every connected undirected graph of n vertices has at least n − 1 edges.

Question 9

Proof: Every connected undirected graph of n vertices has at least n − 1 edges.

Answer 9

Inductive Lemma 0.10 For every k ∈ N, undirected graph G = (V, E) of at most k edges, and u ∈ V, the number of vertices connected to u in G is at most k + 1.

Inductive Hypothesis: Q(n) A graph with n edges, for every v in the graph, v is connected to at most n+1 vertices (include itself).

Statement is implied from Q(n-2)

Question 10

Graph Property 1: Lemma 0.2 In any undirected graph G = (V, E), the sum of the degrees of all vertices is equal to twice the number of edges.

Answer 10

Proof: Lemma 0.2 can be shown by seeing that every edge {u, v} contributes twice to the sum of the degrees (once for u and the second time for v.)

Question 11

Graph Property 2: Lemma 0.3 The connectivity relation is transitive, in the sense that if u is connected to v, and v is connected to w, then u is connected to w.

Answer 11

Proof: Lemma 0.3 can be shown by simply attaching a path of the form
(u, u1, u2, . . . , uk−1
, v) to a path of the form (v, u
′
1
, . . . , u
′
k
′−1
, w) to
obtain the path (u, u1, . . . , uk−1
, v, u
′
1
, . . . , u
′
k
′−1
, w) that connects u to
w.

Question 12

Graph Property 3: For every undirected graph G = (V, E) and connected pair u, v, the shortest path from u to v is simple. In particular, for every connected pair there exists a simple path that connects them.

Answer 12

Proof: Lemma 0.4 can be shown by “shortcutting” any non simple path of
the form (u, u1, . . . , ui−1
, w, ui+1
, . . . , uj−1
, w, uj+1
, . . . , uk−1
, v) where
the same vertex w appears in both the i-th and j-position, to obtain
the shorter path (u, u1, . . . , ui−1
, w, uj+1
, . . . , uk−1
, v).

Question 13

Sink in a DAG

Answer 13

a vertex with 0 degree out-edges

Question 14

Big O Notation Definition

Answer 14

f=O(g) if f(n) < c*g(n) for all n > N_0 for some c. Big O measures asymptotic dynamics of a function in terms of another function

Question 15

Big O Notation Limits

Answer 15

Use the limit x -> infty of f(x) / g(x) to reveal how fast f and g grow relative to one another.

If the limit is a finite value (not 0 or infty), then f and g grow at a similar enough pace to asymptotically be multiples of one another.

If the limit is 0 or infty, then f and g grow at different rates and we conclude g = O(f) or f = O(g), respectively.