D1

Question 1

graph

Answer 1

Consists of vertices (nodes) and edges.

Question 2

Connected graph.

Answer 2

Has no separate parts

Question 3

Simple graph

Answer 3

Has no loops and no more than one edge between any pair of nodes

Question 4

What is the degree (order) of a vertex

Answer 4

The no. of edges incident on it.

Question 5

Cycle

Answer 5

A closed path

Question 6

Tree

Answer 6

A simple connected graph with no cycles.

Question 7

Diagram.

Answer 7

Contains a directed edge

Question 8

How do you produce a compliment graph?

Answer 8

Take the original graph. If 2 nodes were connected, don’t connect them. If there weren’t connected, connect them

Question 9

How do you find the sum of the orders in a simple graph?

Answer 9

Multiply the no. of edges by 2 as each edge will have two ends.

Question 10

What is a network?

Answer 10

Any collection of vertices and edges.

Question 11

What is a weighted graph (network)?

Answer 11

Has edges will allocated values.

Question 12

Minimum connector.

Answer 12

Connection of all points with lowest weight.

Question 13

How does Kruskal’s algorithm work?

Answer 13

Select the shortest edge.
Next shortest that doesn’t give a circle. It doesn’t need to be next to it.
Repeat step 2 until all vertices have been connected

Question 14

How does Prim’s algorithm work?

Answer 14

Select any vertex.
Select the shortest edge connected to either vertex of the first edge.
Select the shortest edge connected.
Repeat step 3.

Question 15

When finding the shortest path, what do the sections of the box mean?

Answer 15

The square is split into 3 with 2 sections in the top. The bottom value is the working value. Top left is the order of labeling and the top right is the label.

Question 16

how could the reliability of a simulation get improved?

Answer 16

do more runs of it
have more, shorter arrival times
more service time to chose from
remove assumptions given in the context.

Question 17

what is a minimum connector?

Answer 17

Something that connects all the points to all the others with the smallest amount of connection. Use Prims and kruskals for this.

Question 18

what is a traversable graph?

Answer 18

One that can be drawn without taking pen off the paper, ending at the start and not going over the same line twice. Also called Eulerian

Question 19

SEMI-EULERIAN.

Answer 19

A graph that can be drawn continuously but only starting from
certain vertices is called SEMI-EULERIAN.

Question 20

conditions for a eulerian graph?

Answer 20

all the vertices have even degrees

Question 21

conditions for a semi eulerian graph?

Answer 21

exactly 2 vertices have odd degrees. You would have to start at one of the odd vertices and end at the other.

Question 22

conditions for a non eulerian graph?

Answer 22

more than 2 vertices have odd degrees.

Question 23

Why does Kruskal’s always give the same solution for a given graph?

Answer 23

No arbitrary choices are ever made.

Question 24

What does Dijkstra’s algorithm give you?

Answer 24

The shortest way to get from the starting point to all the other points.

Question 25

When drawing a graph to find an optimal solution, what must you always do?

Answer 25

Shade out the area that doesn't apply.

Question 26

If you find the no. of paths on a network( no. of ways round) and you have to find the no. of routes, (where direction doesn't matter) what is it?

Answer 26

Halve the no. of paths

Question 27

What is the complexity of prim's, kruskal's and dijkstra?

Answer 27

First 2 are cubic. Latter qudratic

Question 28

If asked why a graph isn't a tree or cycle, what do you say?

Answer 28

Name the nodes of the diagram that form the feature that makes it not what it says it isn't

Question 29

What is an heuristic algorithm?

Answer 29

One that may not lead to the best possible solution. The bin packing algorithms are examples of these.

Question 30

What is float?

Answer 30

Float is the amount of time by which an activity can be delayed or extended.

Question 31

What is independent float?

Answer 31

Float that doesn't affect other activities.

Question 32

What is interfering float?

Answer 32

Float shared between two or more activities.

Question 33

What are i and j?

Answer 33

i earliest starting time | j latest starting time.

Question 34

What is total float for activity (i,j) ?

Answer 34

Latest event time for event j- earliest event time for event i- duration of activity

Question 35

What is independent float for activity (i,j)

Answer 35

Earliest event time for event j - latest event time for event i- duration of activity (If it gives a negative answer, put 0) Doesen' affect anything else

Question 36

What is interfering float?

Answer 36

Total float - independent float. It is the float shared between two activities. If it was 2, you could spend an extra minute on both, 2 on the first or 2 on the last.

Question 37

With a linear programming question, what do you have to begin with?

Answer 37

Let X be the number of...of... | Let Y be the number of ...of

Question 38

What must you remember when using Prim's algorithm with a table?

Answer 38

Number of columns along the top to give the order you put a line through the corresponding row.