Graph theory

Question 1

What is a graph?

Answer 1

A diagram with a set of points called vertices that are joined by lines called edges

Question 2

What are adjacent vertices?

Answer 2

Two vertices that are at opposite ends of an edge (a common edge)

Question 3

What does multiple edges mean?

Answer 3

Two or more edges which connect to the same pair of vertices.

Question 4

What is a loop?

Answer 4

An edge in a graph that joins a vertex to itself

Question 5

What is an isolated vertex?

Answer 5

A vertex that isn’t connected to any other vertex in a graph by an edge

Question 6

What is the degree of a vertex?

Answer 6

The number of graph edges that touch that vertex

Question 7

How many degrees does a loop add to a vertex?

Answer 7

Two

Question 8

What is the sum of degrees?

Answer 8

The total number of degrees of each vertex added together

Question 9

What is the in-degree of a vertex?

Answer 9

The number of edges coming into the vertex

Question 10

What is the out-degree of a vertex?

Answer 10

The number of edges going out from that vertex

Question 11

Give an example of a vertex and edge set.

Answer 11

Set of vertices: V = {A, B, C}
Set of edges: E = {AB, AD, AC, BC}

Question 12

Give an example of an adjacency list.

Answer 12

A: B, D, E
B: A
C: D, E
D: A, C, E
E: A, C, D

The list indicates what each vertex is adjacent to

Question 13

What is a null graph?

Answer 13

A graph made up of isolated vertices and no edges

Question 14

What is a trivial graph?

Answer 14

A null graph with only one vertex

Question 15

What are the features of a simple graph?

Answer 15

• No loops
• No multiple edges
• Number of vertices with an odd degree is even

Question 16

What is the main feature of a connected graph?

Answer 16

There’s a path between each pair of vertices

Question 17

What is the main feature of a disconnected graph?

Answer 17

There’s a pair of vertices with no path between them

Question 18

What are the features of a non-directed/undirected graph?

Answer 18

Made up of vertices and non-directed edges

Question 19

What is the main feature of a directed graph/digraph?

Answer 19

Each edge has an arrow to show the direction of movement

Question 20

What is a simple digraph?

Answer 20

Directed graph with no loops or multiple edges

Question 21

What is the main feature of a regular graph?

Answer 21

All vertices have the same degree

Question 22

What are the features of a complete graph?

Answer 22

• Undirected
• Simple
• Every vertex is connected to every other vertex by an edge

Question 23

What are the features of a weighted graph?

Answer 23

• Each edge is labelled with a number (weight) used to represent a quality associated with the edge (eg: distance, time)
• Can be directed or undirected

Question 24

What is a subgraph?

Answer 24

A part of another graph with no new vertices or edges

Question 25

What are the features of a bipartite graph?

Answer 25

• Vertices can be split into two groups
• Each edge of the graph joins a vertex in the 1st group to a vertex in the 2nd group

Question 26

What is a complete bipartite graph?

Answer 26

Bipartite graph where every vertex in the 1st group is connected to every vertex in the 2nd group

Question 27

What sort of adjacency matrix would “A” indicate?

Answer 27

One-stage matrix with no stopovers

Question 28

What sort of adjacency matrix would “A²” indicate?

Answer 28

Two-stage matrix with one stopover

Question 29

What sort of adjacency matrix would “A³” indicate?

Answer 29

Three stage matrix with two stopovers

Question 30

What sort of adjacency matrix would “A + A²” indicate?

Answer 30

Matrix with one stopover at most

Question 31

What sort of adjacency matrix would “A + A² + A³” indicate?

Answer 31

Matrix with two stopovers at most

Question 32

What are the features of a planar graph?

Answer 32

• Undirected
• Can be drawn on a plane without any edges crossing

Question 33

What is Euler’s formula?

Answer 33

For planar graphs: v + f - e = 2

v = number of vertices
f = number of faces
e = number of edges