Definitions/Propositions

Question 1

What is a graph?

Answer 1

A graph G(V,E) is finite, with a non-empty set V (the vertex set) along with a second set E (edge set) whose elements e ∈ E are pairs (a,b) with a,b ∈ V

Question 2

What is an undirected graph?

Answer 2

A graph G(V,E) whose edges are not ordered pairs

Question 3

What is a diagraph?

Answer 3

A diagraph or directed graph G(V,E) is a graph whose edge set consists of ordered pairs

Question 4

What are adjacent vertices?

Answer 4

Two vertices a,b ∈ V in an undirected graph G(V,E) are said to be adjacent or neighbours IFF (a,b) ∈ E

Question 5

Predecessor/Successor of a vertex?

Answer 5

If the directed edge e(u,v) appears in a diagraph then u is a predecessor to v and v is a successor to u. u is the tail vertex of e and v is the tip vertex of e.

Question 6

Properties of the adjacency matrix?

Answer 6

• A is not unique, depends on the numbering scheme for the vertices. If renumbered, rows & columns will change accordingly
• If G(V,E) is undirected then A is symmetric
• If the graph has no loops then A_jj = 0

Question 7

What is an adjacency list?

Answer 7

In an undirected graph G(V,E) the adjacency list associated with a vertex v is the set A_v = { u | u ∈ V and (u,v) ∈ E}

Question 8

What is the predecessor list?

Answer 8

In a directed graph G(V,E), the predecessor list of vertex v is the set P_v = { u | u ∈ V and (u,v) ∈ E}

Question 9

What is the successor list?

Answer 9

In a directed graph G(V,E), the successor list of vertex v is the set P_v = { u | u ∈ V and (v,u) ∈ E}

Question 10

What is it to say two graphs are isomorphic?

Answer 10

G1 and G2 are isomorphic if there exists a bijection a: V1 –> V2 such that (a(x),a(y)) ∈ E2 if (x,y) ∈ E1

Question 11

Two graphs isomorphic implies what about cardinality?

Answer 11

If G1 and G2 are isomorphic then |V1| = |V2| and |E1| = |E2|

Question 12

If G1 and G2 are isomorphic then what does this imply about their degree?

Answer 12

deg(v) = deg(a(v)) for all v ∈ V1 and deg(u) = deg(a^-1(u)) for all u ∈ V2

Question 13

What is the degree sequence of undirected graph?

Answer 13

A list of the degrees of the vertices (arranged in ascending order)

Question 14

What is the degree of a vertex?

Answer 14

The number of edges that include the vertex

Question 15

If G1 and G2 are isomorphic then this implies what about their degree sequence?

Answer 15

They have the same degree sequence

Question 16

What is a a subgraph of a graph G(V,E)?

Answer 16

A graph G’(V’,E’) where V’⊆V and E’⊆E

Question 17

Given a graph G(V,E) and a subset V’⊆V, what is the subgraph induced by V’?

Answer 17

Subgraph G’(V’,E’) where E’ = { (u,v) | u,v ∈ V’ and (u,v) ∈ E}

Question 18

What is a k-colouring?

Answer 18

Map phi: V –> {1,2,…,K} with the property that adjacent vertices are assigned distinct “colours”. i.e. (u,v) ∈ E implies phi(u) does not equal phi(v)

Question 19

What is the chromatic number?

Answer 19

chi(G) is the smallest k for which G has a K-colouring

Question 20

A graph G is bipartite IFF?

Answer 20

chi(G) = 2

Question 21

If H is a subgraph of G then? (chromatic number)

Answer 21

chi(H) ≤ chi(G)

Question 22

If H is a subgraph of G and G is k-colourable then?

Answer 22

so is H

Question 23

“Floor of x”?

Answer 23

max{k ∈ integers | k ≤ x}

Question 24

“Ceiling of x”?

Answer 24

min{k ∈ integers | k ≥ x}

Question 25

If n is composite it has a factor of b then?

Answer 25

b ≤ sqrt(n)

Question 26

What is a walk?

Answer 26

A sequence of edges (e1e2e3….el) is a walk if there exists a sequence of vertices (v0v1….vl) such that e_j = (e(j-1),e(j))

Question 27

What is a closed walk?

Answer 27

A walk in which vo=vl

Question 28

What is a trail?

Answer 28

A walk in which all edges are distinct

Question 29

What is a path?

Answer 29

A trail in which all vertices are distinct

Question 30

What is a cycle?

Answer 30

A cycle is a subgraph isomorphic to one of the cycle graphs

Question 31

What is the length of the walk?

Answer 31

The number of edges in the sequence

Question 32

What is it to say that two vertices are connected?

Answer 32

a & b are said to be connected if there is a walk such that v0 = a and vl = b

Question 33

What is a connected graph?

Answer 33

A graph in which each pair of vertices is connected is a connected graph

Question 34

What are the equivalence classes of G called?

Answer 34

Connected components of G

Question 35

What is it to say a vertex in a diagraph G is accessible or reachable?

Answer 35

A vertex b is accessible/reachable from a vertex a if there exists a walk from a to b (not the other way round necessarily)

Question 36

Strongly connected vertices?

Answer 36

If u is reachable from v and v is reachable from u in a diagraph

Question 37

Weakly connected diagraph?

Answer 37

A diagraph G(V,E) is weakly connected when it becomes a connected graph when you ignore the directions of the edges

Question 38

In a graph G(V,E), if there is a walk from u to v then?

Answer 38

There is also a path