D1 Flashcards

(38 cards)

1
Q

Definition: Loop

A

When an edge has the same vertex at each end.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Definition: Degree of a vertex

A

The number of edges incident on the vertex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Definition: Walk

A

A sequence of edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Definition: Trial

A

A sequence of edges in which no edge is repeated.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Definition: Path

A

A sequence of edges in which no edges or vertices are repeated.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Definition: Cycle

A

A closed sequence of edges in which no edges or vertices are repeated.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Definition: Hamiltonian cycle

A

A cycle which visits every vertex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Definition: Simple graph

A

A graph with no loops where there is no more than one edge connecting any pair of vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Definition: Connected graph

A

When a path exists between every pair of vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Definition: Disconnected graph

A

When vertices are connected by different paths.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Definition: Tree

A

A simple connected graph with no cycles.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the features of a tree?

A

✔️ Path between every pair of vertices.
✖️ No loops.
✖️ No cycles.
✖️ No more than one edge connecting any two vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Definition: Digraph

A

Where at least one edge has a direction (shown by an arrow).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Definition: Complete graph

A

A simple graph where every pair of vertices are connected by an edge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Definition: Isomorphic

A

When one graph can be stretched or twisted into another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Definition: Planar graph

A

A graph which can be drawn without any edges crossing.

17
Q

Definition: Bipartide graph

A

Vertices fall into two sets, where an edge has a vertex from both sets.

18
Q

Definition: Eulerian

A

A graph which can be drawn continuously starting at any vertex and finishing at the same point.

19
Q

Definition: Semi-Eulerian

A

A graph that can be drawn continuously but only starting at certain vertices.

20
Q

Definition: Non-Eulerian

A

A graph which cannot be drawn continuously.

21
Q

Process: Linear programming

A

1) Define specific variables.
2) Write down all of the constraints.
3) Record points of intersection with axes for each constraint (to help draw graph).
4) Draw graph and shade out regions.
5) Label vertices of the feasible region .
6) Define objective function.

7) Test objective region for each vertex if feasible region. However:
• you may need to find integer co-ordinates for some questions.
• you may need to find the co-ordinates of some vertices by using simultaneous equations.

8) Write a conclusion stating the optimal function, which relates to the question.

22
Q

Process: Kruskal’s Algorithm

A

1) List all of the paths from shortest to longest.
2) Select the shortest path in a network and record in a second list (A -> B 25)
3) Select the next shortest edge which doesn’t create a cycle, but still make a note of any cycles in your second list (C -> D Cycle)
4) Repeat the process until all vertices have been connected.

23
Q

Process: Prim’s Algorithm

A

1) Select any vertex.
2) Select the shortest edge connected to that vertex and record in a list (A -> D 13)
3) Select the shortest edge connected to any of the connected vertices and record in the list (D -> G 12)
4) Repeat until all vertices are connected.

24
Q

Process: Prim’s Algorithm (tables)

A

1) Cross out the first row.
2) Select the smallest value from the first column and circle.
3) Cross out the row containing the value which you have just selected.
4) Select the smallest value from all columns which correspond to crossed out rows.
5) Return to step 3.

25
Process: Dijkstra’s Algorithm
1) Pick a starting vertex and set its order of sequence to 1, and it’s distance from starting vertex to 0. 2) Add temporary labels to all of the vertices which directly connect to this vertex. 3) Add a permanent label to the smallest distance and set the order of sequence to 2. 4) Add temporary labels to all of the vertices which connect to any of the connected vertices (and replace any previous temporary labels with shorter ones where possible). 5) Fill in the box accordingly, and then repeat step 4.
26
Why is Dijkstra’s Algorithm used?
To find the shortest path from one vertex to every other vertex in the network.
27
Process: (Drawing an activity-on-arc network) Critical Path Analysis
Connect all of the activities with preceding activities using nodes and arcs. Dummies can be used but should be limited where possible.
28
Process: (Finding the early and late times) Critical Path Analysis
Left hand box: The latest possible arrival time at the node (To be filled in from the start to the end) Right hand box: The latest time you can leave a node in order to reach all of the next connected nodes on time (To be filled in from end to start)
29
Process: (Cascade charts) Critical Path Analysis
1) Line up activities with their preceding activities. 2) Make sure activity duration is correct. 3) You may then be asked to produce a histogram (e.g. with number of workers)
30
Process: (Using floats to interpret data) Critical Path Analysis
``` 1) Set up a table with the following column headings: • Activity • Total • Independent • Interfering ``` 2) Fill out the ‘total’ column: (right of end node) - (left of start node) - (duration of activity) 3) Fill out the ‘independent’ column: (left of end node) - (right of start node) - (duration of activity) 4) Fill our the ‘interfering’ column: (total) - (independent)
31
What does the independent float tell us (critical path analysis)?
How long you can delay an activity without affecting others.
32
How do you improve the accuracy of a simulation?
Carry out more repeats/simulations.
33
How do you speed up a simulation?
Use more digits so that the percentage of values being rejected and redrawn are lower.
34
How do you create a rule for fractions containing different denominators?
1) Find a common denominator. | 2) Create the rule.
35
First fit Algorithm
In the order they appear, add the blocks to the first bin in which they fit.
36
First fit decreasing Algorithm
Order the blocks into descending order, before adding each block one-by-one to the first bin in which they fit.
37
Full bin Algorithm
Add blocks together which would fill a bin and insert the pair/triplet into the columns left-to-right.
38
Which bin packing Algorithm is most successful?
1) Full bin 2) First fit decreasing 3) First fit Full bin is generally the most successful as it uses up less bins.