Decision maths

Question 1

What is a bipartite Graph?

Answer 1

A graph whose vertices are divided into two distinct sets. All edges go from a vertex in one set to a vertex in the other set.

Question 2

How do you denote a bipartite graph?

Answer 2

with M vertices in one set, and N vertices in the other set:

Km,n

Question 3

What is a subgraph?

Answer 3

A graph whose graph vertices and graph edges form subsets of the graph vertices and graph edges of a given graph.

Question 4

What is a subdivision of a graph?

Answer 4

A subdivision occurs when a new vertex is added on an edge so that the edge becomes two edges.

Question 5

What is a loop?

Answer 5

An edge that starts and finishes and the same vertex

Question 6

When do vertices have multiple edges?

Answer 6

When there is more than one edge that connects them

Question 7

What type of graph has no loops and no multiple edges?

Answer 7

A SIMPLE graph

Question 8

What type of graph has one or more edges that have an arrow to indicate that you can only go in one direction?

Answer 8

A digraph

Question 9

What is a trail?

Answer 9

A trail is a sequence of edges in which the end of one edge ( except the last ) is the beginning of the next, and no edge is repeated

Question 10

What is a cycle?

Answer 10

A cycle is a closed trail in which no vertex is repeated.

Question 11

What is a hamiltonian cycle?

Answer 11

A cycle that visits every vertex only once

Question 12

What is a tree?

Answer 12

A simple connected graph with no cycles

Question 13

What is a graph that has numbers (weights) associated with the edges?

Answer 13

A network, (can also be presented as a graph)

Question 14

What is Euler’s formula for connected Planar graphs?

Answer 14

v - e + f = 2

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

Question 15

What makes a graph planar?

Answer 15

A graph is planar if it can be drawn in two dimensions without any edges crossing

Question 16

What’s Kruskal’s algorithm?

Answer 16

• Select the shortest edge

- At each stage, select the next shortest edge that is not connected to the vertices that are already connected

Question 17

What’s Prim’s algorithm?

Answer 17

• Select any vertex to start from
• Correct the nearest node that is not already connected
• Repeat until all nodes are connected

Question 18

What are methods of finding the minimum spanning tree?

Answer 18

Prim’s and Kruskal’s algorithm

Question 19

How do you find the lower bounds of a route ( Travelling Salesperson Problem)

Answer 19

• Remove a node
• Complete a minimum spanning tree for the remaining nodes
• Add the two shortest routes from the removed node back in

If this results in a tour, this is the optimal tour available

Question 20

How do you find the upper bound of a route?

Travelling Salesperson Problem

Answer 20

• Choose an arbitary starting node
• Add in the smallest arc to this node that is not yet in the tour
• Repeat until all nodes are in the tour
• Add an arc back to the start node ( shortest )

Question 21

How do you convert a classical problem to a practical problem?

Answer 21

Add on arcs between points that aren’t connected

Question 22

What is the route inspection algorithm?

Answer 22

• Find the total weight of the network
• Identify the odd vertices
• Pair the odd vertices, and add up the pairs to find the smallest selection
• Add this to the total weight of the network