Decision Maths

Monday Monday Monday! Monday nitro tan!

HideShow resource information

Valency

Number of connections inside a network.

1 of 10

Traversability

Whether you can traverse all paths and get back to the start point without retracing or removing pen from page.

Eulerian: Completely traversable from any point.

Semi Eulerian: Traversable from 1 specific point to another specific point.

Non Eulerian: Not Traversable.

2 of 10

Kruskals Algorithm

> List all path lenghts into ascending numerical (weight) order.

> Connect shortest paths in order but not if nodes are already connected.

> Add all path lenghts together and state the order you chose them in.
e.g A-C-D-B-E.

3 of 10

Prim's Algorithm

> Start from a source node (start point) connect shortest path from all available nodes.

> Add all path lenghts together and state the order you chose them in.

> This is different to Kruskal's as you don't have to order the path lengths into an ascending numerical list.

> Can also be completed done in a matrix.

4 of 10

Dijkstra's algorithm

> Finds the shortest path from a source node to a sink node by evaluating the minimum distance to each node.

> Each path is numbered in order of consideration, for example 1, 2, 3, 4 and so on 1 being the start point and the higher the number the further the node is from the start point.

> At each node the minimum distance from the start point must be shown.

> When the shortest route has been found it is neccesary to work back from the end point to the start point showing your working out.

e.g 36-17 = 19, 19 - 7 = 12, 12 - 8 = 4, 4 - 4 = 0

5 of 10

Quick sort

> Data is ordered into ascending or descending order.

> Midpoint of this data list is found and then it is decided whether the data value being found is above or below the midpoint.

> The whole process is completed again but with all the values above or below the midpoint; and again, and again until the data value is on its own.

6 of 10

Bubble sort

whatcho talkin' about you crazy fool!

7 of 10

Node/vertex (plural: Nodes/verticies)

A node/vertex is a point on a graph.

8 of 10

Graph

Graphs are a colection of nodes and paths.

9 of 10

Paths

Paths are connections between nodes.

10 of 10

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »