Decision 2: Graphs and Networks

Question 1

What is a graph?

Answer 1

Points (vertices/nodes) connected by lines (edges/arcs)

Question 2

What is a vertex/node?

Answer 2

The point where the ends of two edges meet

Question 3

What is an arc/edge?

Answer 3

A line joining dots together

Question 4

What is a sub-graph?

Answer 4

A section of an original graph, containing some of the edges and nodes

Question 5

What is degree/valency/order?

Answer 5

The number of arcs coming off a node

Question 6

What is a path?

Answer 6

A non-repeating, finite sequence of connected vertices

Question 7

What is a walk?

Answer 7

A path where vertices can be repeated

Question 8

What is a trail?

Answer 8

A walk in which no edge is visited more than once

Question 9

What is a cycle/circuit?

Answer 9

A path that returns to its starting position (start/end vertex is an exception to the path rules)

Question 10

What is the handshaking lemma?

Answer 10

Sum of degrees = 2 x number of edges

The number of odd nodes must be even

Question 11

What is always true for total valency?

Answer 11

Total valency is always even

Question 12

What is a connected graph?

Answer 12

All vertices in the graph are connected; there are no constituent parts to the graph

Question 13

What is a loop?

Answer 13

An edge that starts and ends at the same vertex, adding two to the valency

Question 14

What is a simple graph?

Answer 14

A graph with no loops and no more than one edge connecting the same pair of vertices

Question 15

What is a digraph?

Answer 15

A graph with edges that have a direction associated with them

Question 16

What is a tree?

Answer 16

A connected graph that has no possible cycles

Question 17

What is a spanning tree?

Answer 17

A tree subgraph containing all vertices from the original graph

Question 18

What is a bipartite graph?

Answer 18

Two sets of vertices, X and Y, in which only vertices from different sets can be connected (i.e. X can only be connected to Y)

Question 19

What is a complete graph? (2)

Answer 19

All nodes are directly connected to each other

Kn = n vertices

Question 20

What is a complete bipartite graph? (2)

Answer 20

Every node from one set is connected to all nodes in the other set
K(n,m) = n vertices connected to m vertices

Question 21

What is an isomorphic graph?

Answer 21

The same graph drawn differently

Question 22

What is an adjacency matrix?

Answer 22

A matrix recording the number of direct links between each node

Question 23

What is a distance matrix?

Answer 23

A matrix recording the distances between directly connected nodes

Question 24

What is a Hamiltonian cycle?

Answer 24

A cycle that includes every vertex

Question 25

What is the planarity algorithm used for?

Answer 25

To determine if a graph is planar (can be drawn so that no edges cross except at a vertex)

Question 26

What is the planarity algorithm? (4)

Answer 26

Find a Hamiltonian cycle from the graph in question
Redraw the graph with the cycle as a polygon and the remaining sides within the polygon
Label one of the interior edges, I and list any edges that cross it, labelling them O unless two of them cross each other (meaning the graph is non-planar)
Work through the sides until all of them are labelled and then redraw the graph so that all of the I edges are inside the polygon and the O edges are around the outside