D1 Decision Maths OCR - Everything you need sortened - with pictures to demonstrate
Teacher recommended
?- Created by: Alex
- Created on: 25-05-11 20:18
Simple Graph: Graph with no loops and at most one edge connecting any pair of verticies
Connected Graph: If allthe verticies are connected
Tree: A connected graph with no cycles
Complete Graph: One where every pair of verticies is connected by a single edge
Planar Graph: One that can me drawn so that no arcs cross
Hamiltonian cycle: One that visits every arc once and returns to the starting arc
Eularian Trail/Cycle: Covers every edge of the graph once and finished at the start vertex - This graph is Eularian
Semi-Eularian: If it is possible to cover every arc on the graph and finish at another vertex
Tracersable: If the graphs can be drawn without taking the pen of the paper or repeating any edges
Direct Graph/Diegraph: Graph with at least one arc with a direction associated with it - opposite in undirected
Biparte Graph: A graph whos verticies can be divided into two coloums such that every arc in U connects to an arc in V
Algorithms & such
Bubble Sort:
Compares numbers in a series of passes and swaps if necessary
Shuttle Sort
Compares the first two then adds third number and compares, then add the 4th and compares etc
First-Fit Algorithm
Taking items in the order listed and placing them in the first space available
First-Fit decreasing Algorithm
Rearrange items into descending order of size
Place each item in turn into the first bin space available
Kruskals Algorithm:
1. List edges in order with smallest first -(Put it in a table)
2. Choose are of least weight
3. Choose are of least weight (not already chosen one) which doesn't form a cycle from already chosen arcs
4. Repeat 3 untill all verticies have been included.
Prim's Algorithm
1. Choose start vertex
2. Connect start vertex to nearest vertex by adding shortest edge
3. From and vertex on tree so far add shortest edge that connects a new vertex
4. Repeat 3 untill all veritcies included
Prim's Algorithm - From a matrix
1. Choose a start Vertex & label the corresponding column aith 1. and delete the row
2. Look in all coloumns numbered so far & circle the smallest undeleted entry and read off vertex for this row
3. Label column corresponding to this vertex with the next…
Comments
Report
Report
Report
Report
Report