D1

Question 1

Simple graph

Answer 1

No loops or multiple arcs

Question 2

Connected graph

Answer 2

All pairs of nodes are connected

Question 3

Complete graph

Answer 3

All nodes connected by one arc to every other node (Kn = complete with n nodes)

Question 4

Planar graph

Answer 4

Can be drawn in a plane, so that arcs only meet at nodes and don’t cross

Question 5

Isomorphic graphs

Answer 5

Same nodes and arcs but different shapes

Question 6

Trail

Answer 6

End node of an arc is the start node of the next

Question 7

Path

Answer 7

No node used more than once

Question 8

Cycle

Answer 8

Closed trail where only the first and last nodes are the same

Question 9

Tree

Answer 9

Simple graph without cycles

Question 10

Spanning tree equation for arcs

Answer 10

n nodes

= n-1 arcs

Question 11

Euclerian

Answer 11

Closed trail
Every arc once
Every node has even order

Question 12

Semi-Eulerian

Answer 12

Not closed
Every arc once
Only 2 nodes have odd order

Question 13

Hamiltonian cycle

Answer 13

Passes every node of the graph once and returns to its starting node

Question 14

Kruskal’s Algorithm

Answer 14

• Sort arcs into ascending order of weight
• Select least weight arc
• Select next lowest that doesn’t form cycle with anything
• Repeat until you have a spanning tree

Question 15

Prim’s Algorithm

Answer 15

• Choose starting node
• Attach to arc of least weight
• Look at other nodes that aren’t in the tree and connect with minimum arc length to a node that’s in the tree
• Repeat until all nodes in the tree

Question 16

Dijkstras Algorithm

Answer 16

Temporarily label each node with distances from starting node and choose lowest value
- start node labelled zero

Question 17

Chinese postman Algorithm

-assuming it’s not eulerian

Answer 17

1-find all odd nodes
2-for each pair of odd nodes, find the connecting path of minimum weight
3-Consider all ways of pairing odd nodes and select one with minimum total weight
4-duplicate paths selected in step 3
5-find closed trail containing every arc for the new network

Question 18

Chinese postman pairings

Answer 18

2 odd nodes = 1 pairing
4 odd nodes = 3 pairings
6 odd nodes = 15 pairings

Question 19

Nearest neighbour

Answer 19

• choose starting
• pick min weight arc attached to it
• repeat until all nodes chosen
• add arc that joins last chosen node to first

Question 20

Lower bound Algorithm

Answer 20

Choose a node and find total of two smallest weights incident

Ignore the node and selected arcs and find total weight of minimum connector for this network

Sum of both = estimate

Question 21

Upper bound

Answer 21

Nearest neighbor

Question 22

First fit

Answer 22

Each object put in first available place

Question 23

First fit decreasing

Answer 23

Arrange in decreasing size and then use first fit

Question 24

Shuttle sort

Answer 24

Look at 1/2
Look at 2/3
Look at 3/4…….
Swap when necessary

If you’re swapping 5/6 and it’s smaller than all the others, keep moving it down the line to correct place