Algebra & Graphs

Part 4 of 8 · Previous: Functions · Index · Next: Sequences

19. Fractions

\frac{a}{b}

means $a$ divided by $b$ .

Example:

A_{k} = \frac{N + D _{k} - k}{k}

Read the entire numerator before dividing:

Add $N$ and $D_{k}$ , subtract $k$ , then divide the complete result by $k$ .

In code:

A_k = (N + D_k - k) / k

From:

a - b = c

derive:

a = c + b

From:

\frac{x}{k} \geq y

and $k > 0$ :

x \geq k y

When multiplying by a negative number, reverse the inequality:

- 2 x < 6

becomes:

x > - 3

If:

D_{k + 1} = D_{k} + Δ_{k + 1}

then in:

A_{k + 1} = \frac{N + D _{k + 1} - ( k + 1 )}{k + 1}

replace $D_{k + 1}$ :

A_{k + 1} = \frac{N + D _{k} + Δ _{k + 1} - ( k + 1 )}{k + 1}

Authors often write:

Substituting $D_{k + 1} = D_{k} + Δ_{k + 1}$ , we obtain…

Notation	Meaning
$G = (V, E)$	Graph with vertices $V$ and edges $E$
$V (G)$	Vertex set of graph $G$
$E (G)$	Edge set of graph $G$
$u \sim v$	$u$ and $v$ are adjacent
$(u, v) \in E$	Directed edge from $u$ to $v$
${u, v} \in E$	Undirected edge between $u, v$
$de g (v)$	Degree of vertex $v$
$N (v)$	Neighbourhood of $v$
$P : u ⇝ v$	Path from $u$ to $v$
$ℓ (P)$	Length of path $P$
$d (u, v)$	Shortest-path distance
$G [S]$	Subgraph induced by vertices $S$
$G - v$	Graph after removing vertex $v$
$G - e$	Graph after removing edge $e$

V (P_{i}) \cap V (P_{j}) = {s, t}

means:

Paths $P_{i}$ and $P_{j}$ share only start and end.

Equivalently:

Int (P_{i}) \cap Int (P_{j}) = \emptyset