Decision 2 - Graphs and Networks

Question 1

What is a graph in decision maths?

Answer 1

A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs).
If a graph has a number associated with each edge (usually called its weight), then the graph is known as a weighted graph or network.

Question 2

What is a vertex?

Answer 2

A vertex is a point on a graph. Vertices are sometimes called nodes.

Question 3

What is an edge?

Answer 3

An edge is a line segment joining vertices. Edges are sometimes called arcs.

Question 4

What is the vertex set?

Answer 4

The list of vertices comprising a graph.

Question 5

What is a subgraph?

Answer 5

A graph, each of whose vertices belongs to the original graph and each of whose edges belong to the original graph.
It is simply a part of the original graph.

Question 6

What is the degree of a vertex?

Answer 6

The degree or valency or order of a vertex is the number of edges incident. If the degree of a vertex is even, it is said to have even degree.

Question 7

What does it mean if an edge and vertex are incident?

Answer 7

A vertex and an edge are incident if the vertex is at either end of the edge.

Question 8

What is a walk?

Answer 8

A route through the graph along edges from one vertex to the next.

Question 9

What is a path?

Answer 9

A path is a walk in which no vertex is visited more than once.

Question 10

What is a trail?

Answer 10

A trail is a walk in which no edge is visited more than once.

Question 11

What is a cycle?

Answer 11

A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.

Question 12

What is a Hamiltonian cycle?

Answer 12

A Hamiltonian cycle is a cycle that includes every vertex.

Question 13

What does it mean for two vertices to be connected?

Answer 13

Two vertices are connected if there is a path between them.

Question 14

What does it mean for a graph to be connected?

Answer 14

A graph is connected if all its vertices are connected.

Question 15

What is a loop?

Answer 15

A loop is an edge that starts and ends at the same vertex.

Question 16

What does it mean for a graph to be simple?

Answer 16

A simple graph is one in which there are no loops and there is at most one edge connecting any pair of vertices.

Question 17

What is a directed edge?

Answer 17

If an edge of a graph has a direction associated with it, it is known as a directed edge and the graph is known as a directed graph, often abbreviated to a digraph.

Question 18

What is the sum of the degrees of the vertices of any undirected graph?

Answer 18

The sum of the degrees is equal to 2×the number of edges. As a consequence, the number of odd vertices must be even, including possibly zero. This result is known as Euler’s handshaking lemma.

Question 19

What is a tree?

Answer 19

A tree is a connected graph with no cycles.

Question 20

What is a spanning tree?

Answer 20

A spanning tree is a subgraph which includes all the original graph’s vertices and is also a tree.

Question 21

What is a complete graph?

Answer 21

A complete graph is a graph in which every vertex is directly connected by a single edge to each of the other vertices.
The complete graph of 𝑛 vertices is written Kₙ.

Question 22

What is an isomorphic graph?

Answer 22

An isomorphic graphs are graphs that show the same information but may be drawn differently.

Question 23

What is an adjacency matrix?

Answer 23

Each entry in an adjacency matrix describes the number of arcs joining the corresponding vertices.

Question 24

What is a distance matrix?

Answer 24

A matrix associated with a weighted graph, in a distance matrix, the entries represent the weight of each arc, not the number of arcs.

Question 25

What is a planar graph?

Answer 25

A planar graph is one that can be drawn in a plane such that no two edges meet except at vertices.

Question 26

What is the planarity algorithm?

Answer 26

The planarity algorithm can be applied to graphs that containing a Hamiltonian cycle.
The algorithm is as follows:
1) Identify a Hamiltonian cycle.
2) Draw a polygon with vertices labelled to match the ones in the Hamiltonian cycle.
3) Draw edges inside the polygon to match the edges of the original graph not already represented by the polygon itself.
4) Make a list of all edges inside the polygon, in any order.
5) Choose any unlabelled edge and label it ‘I’. If all edges are now labelled then the graph is planar.
6) Look at any unlabelled edges that cross the edge(s) just labelled:
•If there are none, then go back to step 5.
•If any of these edges cross each other, then the graph is non planar.
•If none of these edges cross each other, give them the opposite label to the edge(s) just labelled.
•If all edges are now labelled, the graph is planar. Otherwise, go back to the start of step 6.

Question 27

What is a minimum spanning tree?

Answer 27

Sometimes called a minimum connector, a minimum spanning tree is a spanning tree of a weighted graph such that the total length of its arcs (edges) is as small as possible.