# Decision 1 Maths Revision Notes plus Key Definitions

Decision 1 Maths Revision Notes plus Key Definitions

- Created by: Thomas Fenton
- Created on: 23-03-13 19:07

First 331 words of the document:

D1 Revision

Prim's, Kruskal's and Dijkstra's Algorithm

Prim's Algorithm: Choose any vertex to start the tree, selecting an arc of least

weight that connects from a node currently in the tree, to a node not currently

in the tree.

Kruskal's Algorithm: Sort the arcs in to ascending order of weight, using the

arc of least weight to start the tree, adding arcs in order of ascending weight,

rejecting those that form cycles.

Prim's on a Matrix: Choose any vertex to start the tree, number the column of

the chosen vertex and delete that vertex's row. Circle the lowest undeleted

entry in that column which becomes the next vertex.

Dijkstra's Algorithm: The start vertex is given final value zero. Each vertex

directly connected to that vertex is a given a working value:

Final value of previous vertex + weight of arc

The smallest working value is chosen. This becomes that vertex's final value.

This is repeated until the final vertex has a final value.

The route is found where: final label B final label A = weight of arc AB

Graphs and Networks

Graph: A series of vertices connected by lines

Weighted Graph/Network: A graph where a number is associated with each

edge

Subgraph: A subgraph of G is, a graph whose vertices and edges belong to G

part of the original graph

Degree/Valency: The number of edges incident to a vertex

Path: A finite sequence of edges such that the end vertex of one edge is the

start vertex of another and no vertex appears more than once

Walk: A path where you can return to vertices more than once

Cycle: A closed path

Digraph: A graph where edges have direction associated with them

Tree: A connected graph with no cycles

## Comments

No comments have yet been made