Week 7 Paths

Question 1

Path

Answer 1

Let G = (V, E, ε) be a finite graph. A path in G (of combinatorial length n ≥ 0) is a finite sequence of vertices
{v_i}^n _i=0 and a finite sequence of edges {e_j}^n _j=1 such that
ε(e_j ) = {v_j−1, v_j }for each j = 1, . . . , n. We say that the path begins at vertex v_0 and ends at vertex v_n (or is a path
from v_0 to v_n).

Question 2

Cycle / circuit

Answer 2

A cycle (or circuit) is a path that begins and ends at the same
vertex.

Question 3

Connected

Answer 3

We say that a graph G is connected if for every pair of
distinct vertices u ≠ v there is a path in G from u to v.

Question 4

Connected component

Answer 4

Let G = (V, E, ε) be a graph and let v ∈V . The
connected component of v in G, denoted G^(v), is the
subgraph of G whose vertex set is the set of vertices that
can be reached by a path from v and whose edge set is the
set of edges incident on these vertices.

Question 5

What function is a generating function for the number of paths of length n between any two vertices

Answer 5

(I−tA)^−1